算法入门系列之二 -- 筛选法

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
( n3 |0 n6 }# M6 a( t* A0 D& t) u
. D4 Q  x& j# ^4 ^) p0 ~( Q1: 求1-100之间的质数
! g0 _. o" k- U6 S+ a2 ~- e7 F
/ O2 k5 I. d. s# H( s0 H- s    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
) h/ u: K7 q$ r8 j6 d  N6 T: ^{
7 o- x& I) l3 g9 L    int i, j;
; M' \! `" u0 O+ }& E    bool flag[100];

# w' B" e" L$ a* z' M    for ( i = 2; i < 100; i++ )
' R. X! k5 I3 D: u( ~8 L/ r4 s) i        flag = true;
, b( z( I# {1 r1 \' q% R
0 x' j6 c! v* V. A* o4 n9 v    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
7 H. f8 Q! b: H! L9 e* D5 t5 F1 O    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
+ z: ^- W) a& \# T+ u    }

    //输出结果
+ w7 J$ G, Y! C; m1 ~6 R    for ( i = 2; i < 100; i++ )
. y( ^5 d2 \6 k( D9 l7 w        if ( flag )
            cout << i << ' ';
}

2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
& D* X) X3 ]* J2 t; M  V
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
+ ^9 u5 C$ w& s* U9 R
    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

9 N; l/ ~8 O$ j8 o) h: Xvoid fun2()
/ T0 e# I  |% a1 [; F{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
+ R% u& M; T7 ?  |
; a3 |# }6 s# N. h: R; a/ V- j    for ( int i=0; i< 30; i++ )
2 ^2 q- B/ x) k7 |) I* ~        flag = true;

    int n = 30;//还剩几个人
    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
  R# C; v$ X4 J, {    while ( n > 0 )
    {
        cnt = 0;
        while ( cnt < 5 )
        {
) x! q, T% Y% O9 C- `            if ( ++pos == 30 )
                pos = 0;
2 J, S! c2 p# P, s4 T' M" J5 e            if ( flag[pos] )//此人还没被毙掉
3 T, f! o7 M- b8 T9 m* F) N                cnt ++;
        }
        //退出时cnt == 5，pos指向报5的人
" b% y. K/ j6 J2 ]/ n( |        flag[pos] = false;//毙掉
        n --;//剩余人数减1
! `& t4 F5 B0 o) `. V: i. l9 c    }
    //最后一个被毙的就是幸存者
" O% ~& m9 k* J% @    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
- G) F4 G3 S1 B' I: D, h. r* H! [" t    cout << pos + 1 << ' ';
/ j, q' b! f% f* v}
* k9 M: ^# {6 ^( X
4 p; d! W: T/ }+ w& s3: 一个数被5除余3，被7除余2，求此数最小为几。
5 F' @+ ^% g- H6 g- S; O
    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
3 [& V5 E+ r5 [5 u( k    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

  K0 Y, [' N- e( L0 n- xvoid fun3()
* p  p$ g7 U/ U{
- I7 F9 A0 ]# Y    int a[105];//105 = 5 * 7
& L2 y$ S6 n1 d: M; O    int i;
    //计数清0
    for ( i = 0; i < 35; i++ )
        a = 0;
    //开始筛选
6 P" `$ \( z# R% F# W4 D    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
        a ++;

) F/ Q* R% F8 g# H* Z3 g& p    for ( i = 0; i < 35; i++ )
1 Z# r8 n) T) J% C1 e; t- J; z        if ( a == 3 )
& m1 B$ K: y4 m0 Q- k& T$ Z        {
            cout << i << endl;
            return;
        }
, b( P, d3 t+ W+ D9 p% H    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
: E+ r7 B1 B; M9 R3 i  X}
3 l" N/ A) \9 ]$ a& y" f
0 i1 S4 R8 v5 h, Q
0 @. k2 X5 S0 r2 {总结：
+ o) K4 O2 y- h. r; @" Z- y    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

for ( int i = 0; i< n; i++ )
9 y6 t( }8 |  R{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
2 Z+ ?: o; \0 z: ]# [* M0 V
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
: M. m3 u2 y8 F! S
    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的