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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。

; T  b6 @, c" q/ y# n7 _1 d* n1: 求1-100之间的质数
* z% X6 S% \7 f
( T; s% Q, g& \4 r# b    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
7 h1 p! D  B$ F, X* O0 a{
0 j% h% `- }8 U7 _+ c# b    int i, j;
7 Q: e& o+ G& c$ j2 o& n    bool flag[100];
2 |6 n5 z! ]& N
    for ( i = 2; i < 100; i++ )
6 P0 G- F4 W# {: t        flag = true;

7 m# C: V7 _; }. x6 ~) k$ `; }    //下面开始划掉合数
1 G+ D5 Z1 X( Z/ ?+ G7 x  n    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
( @: ~/ v  Z; d6 o6 w' H        if ( flag == false )
9 f5 I& \. F' B6 X            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
7 l) ]3 X9 X0 {' e  Q            flag[i*j] = false;
/ b: t" R+ L& n* S* L    }
/ G  H1 ~5 Z9 ~9 o  b
! ]% r" \2 n8 f6 [4 S. ^    //输出结果
    for ( i = 2; i < 100; i++ )
        if ( flag )
            cout << i << ' ';
* J  s: [5 K. V% B0 p# u$ D}
( q- c+ k$ }$ p. v, x  \
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
- f" K+ y6 ^! F* l% r
# @0 W4 a& l1 {" A    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
& X; I1 o2 O- s' \8 z$ W; a
void fun2()
# F" X; @0 }; p: M: c$ \{
+ @. T* p0 s# d/ U7 P( T    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
" R0 Q2 k0 @  D, c; K, ^
    for ( int i=0; i< 30; i++ )
        flag = true;

1 F# ]8 q- b: B5 V' C    int n = 30;//还剩几个人
    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
# r1 ?1 U  @6 O3 U) G( M5 H" f    while ( n > 0 )
    {
        cnt = 0;
        while ( cnt < 5 )
        {
8 s* o8 i2 E$ X: A" U' w/ Q4 M3 u            if ( ++pos == 30 )
                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
/ f* W/ C" A5 f                cnt ++;
        }
        //退出时cnt == 5，pos指向报5的人
, h  m' m5 X: K        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
    //最后一个被毙的就是幸存者
" D$ A0 J% Q% x6 W1 t1 _    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
9 t2 q9 B3 j7 {" Y- Y}

7 ^( l8 R6 U/ R5 l3: 一个数被5除余3，被7除余2，求此数最小为几。
9 E. f' u  ]: G9 u, A
    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
6 i' Y" ^9 M: Q
! B2 r. Q( d- \" E/ P% k2 ovoid fun3()
{
" m. r" z: E1 T- [$ }4 \4 L    int a[105];//105 = 5 * 7
+ D4 R) N/ C, O    int i;
    //计数清0
    for ( i = 0; i < 35; i++ )
. |! y* y# m# U* e) t: f- r        a = 0;
- H7 K2 I6 C4 i; I8 h% i& w1 d    //开始筛选
1 D/ v- L9 \$ C  v& \4 w1 m( W    for ( i = 3; i < 35; i += 5 )
) N" G# H$ J/ L0 w- g        a ++;
, v/ s8 l3 R, O7 d9 i* d, @    for ( i = 2; i < 35; i += 7 )
        a ++;
- R# C/ @/ P; U0 c2 W: E& G, [4 Q  ?
. [+ {, T) h' o+ u9 a    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
        {
+ ]. r% w2 V3 V6 B4 q            cout << i << endl;
            return;
        }
    //如果执行到这里说明无解
4 e& _# W' {; W0 v0 h. Q    cout << "No Answer!" << endl;
}
9 T" [! _: D2 s0 [  F# f

# Y4 g7 ^' R. t6 m2 t( ~+ S总结：
* f4 ^/ G7 `' x    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

for ( int i = 0; i< n; i++ )
/ ?- _$ ]+ O9 R8 |7 Q) v{
, \8 f: R, L. W7 i9 y    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
}
5 @/ r4 v5 t# n1 j# Z    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

6 T# ~, A9 j9 `" @, A" C    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

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