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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
$ q& W- C2 r, }, V; n6 n" ]- n
6 ], F4 G% Z8 f1: 求1-100之间的质数
, D% V: g# n4 g, H6 `
    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
{
    int i, j;
    bool flag[100];

- o3 P! N* [' b! X) P    for ( i = 2; i < 100; i++ )
        flag = true;
+ |, K; g8 }3 @$ v0 _: W' J$ f
, Q4 t8 g4 ?9 G0 |6 c4 ]    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
" a: V: j8 |( {7 r        if ( flag == false )
; O6 S9 E2 r5 V! B            continue; //既然i已经是合数，它的倍数应该已经被划掉
( y" M- Z4 t; ^: P- A        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
' {9 l  X3 X/ c9 q    }

    //输出结果
    for ( i = 2; i < 100; i++ )
        if ( flag )
3 X9 h" L/ B8 o, g6 ~4 O, B            cout << i << ' ';
}

- i, L# E- s* C2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
/ v/ `7 T5 Z& Q' n8 S2 n% K0 u
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

3 l, t6 N3 G; {1 @* T    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
$ f6 \/ Q. ^4 W; R( {+ [' l: U
void fun2()
{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
  z0 I. }7 N% l; Z; i
) Z, M" x) |/ E& w4 |8 |# ^* \    for ( int i=0; i< 30; i++ )
        flag = true;

    int n = 30;//还剩几个人
+ n$ S4 g( B2 [9 E$ C( T+ F- h8 r    int cnt;
+ T: z2 t' \8 u5 S. m    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
2 P2 y! w; d1 Y6 c8 s    {
        cnt = 0;
        while ( cnt < 5 )
' p: e- |% @: d; v' Y# p        {
7 I! N$ J$ c* W" [" l            if ( ++pos == 30 )
                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
        }
) r6 X3 v5 ]/ y' v9 N6 B        //退出时cnt == 5，pos指向报5的人
1 J/ S# f8 U8 g2 \        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
( y5 N0 _( x8 ^    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
}

3: 一个数被5除余3，被7除余2，求此数最小为几。

2 Z- L- T& H0 A' C; B/ |; a    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
* m1 E& p! T3 j2 o9 d% J, _    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
- k7 i9 I9 }7 p0 Q# x% W5 X1 u{
6 I& W8 |3 u. Z% @0 d    int a[105];//105 = 5 * 7
    int i;
  W9 S# I0 A) O% W+ g    //计数清0
" T1 w1 P, {, s  C+ ]: K    for ( i = 0; i < 35; i++ )
        a = 0;
    //开始筛选
5 k5 E$ t5 K; S7 M) L8 Q4 ^    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
0 w3 m; Y9 J, c  w- S1 v        a ++;
6 t" n1 z9 _( k( |, D
    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
% B+ L0 b7 w! y* K+ I        {
6 L- j2 M' c% E: j0 X            cout << i << endl;
            return;
& N2 e0 P, y( K" j7 O        }
    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
/ r3 x- R3 ^# J0 J}


总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
3 B, C3 f3 Q( X! X/ F( J
; h' R5 ~6 g5 i& Z1 Yfor ( int i = 0; i< n; i++ )
& I6 \- G4 a# O/ E& _- D0 Q{
5 g- s, \/ D" j: E    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
}
) S) w5 g: T+ Z+ r1 I    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
$ F, Y. a% g5 I0 x: S1 \# L
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的