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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
7 S5 w. ]& K0 i* }) q6 ]0 q
5 w. A1 `% J2 w  c1: 求1-100之间的质数
0 B+ l7 G7 j5 I
    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
/ v$ `" F9 J- Q8 s6 }5 A{
5 v: ^; L$ Z$ X$ b8 }! d6 @    int i, j;
    bool flag[100];

    for ( i = 2; i < 100; i++ )
/ D* e% n. J4 k: {+ L+ C        flag = true;
7 y* U$ Z7 p5 Y9 Y2 h) M
    //下面开始划掉合数
; ~  t0 E3 l# J7 G. T; U3 o. V0 Z    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
' i% W  b/ f  Y6 }5 g. k" d    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
    }
+ F6 A; ~+ A$ H  l( c
! }- b6 a" C% ~    //输出结果
    for ( i = 2; i < 100; i++ )
" c2 E1 l; [3 X( D% [        if ( flag )
            cout << i << ' ';
}
5 U7 `$ ?+ g" C
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

: P' T9 @! w$ p/ E/ \/ Y  b    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
& `8 x- Q% k  \. U" q
8 [) a0 {3 T1 v4 `# N    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

void fun2()
{
$ M% B6 q9 B  n' s    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
  D& Z3 s: p* ~! B$ @, e! p
2 [7 D6 a& X8 @4 ^4 ?1 ]    for ( int i=0; i< 30; i++ )
4 Q3 w: y5 c/ G& P1 ^& @8 V: l        flag = true;
8 s. K7 P3 h' h  C7 B
& i" h: s4 j5 G( c+ @% E1 j1 b    int n = 30;//还剩几个人
' m. `0 E) K( ]8 G( O* j    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
1 S7 D, a& Z5 Y2 a5 Z( x$ I- g3 f    {
        cnt = 0;
        while ( cnt < 5 )
" s1 Q7 Y7 N$ T3 y        {
7 R1 g# F1 Q' ]$ ~            if ( ++pos == 30 )
                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
! g1 p2 U' |  T9 `9 W                cnt ++;
  |' U9 B1 A1 r! l! ?        }
        //退出时cnt == 5，pos指向报5的人
0 u% G6 o3 l. W& h2 x2 U8 d        flag[pos] = false;//毙掉
( E' v. S. _" Q9 C/ l7 i- v        n --;//剩余人数减1
0 Z3 Z( O; }' E1 e2 G    }
    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
( B: ^. H! F6 ~! U# r" v8 T0 s4 s' A}

3: 一个数被5除余3，被7除余2，求此数最小为几。
1 F: m  K- \6 [* d4 U1 V
! L! r- q/ i) P  J# N! C    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
2 x6 I9 ?0 z: Y! i
void fun3()
; r& W: }8 _9 z: ]{
7 q* ]2 s8 y& {9 d; H/ n    int a[105];//105 = 5 * 7
    int i;
+ U* g, ?3 T7 W/ x9 u9 T6 w    //计数清0
    for ( i = 0; i < 35; i++ )
        a = 0;
    //开始筛选
    for ( i = 3; i < 35; i += 5 )
) Y' n9 j( V2 h5 I& a        a ++;
$ |3 f/ N! y9 o    for ( i = 2; i < 35; i += 7 )
        a ++;
4 ?$ f. h9 k( D
1 V- J6 s6 y+ v! z* `    for ( i = 0; i < 35; i++ )
7 }, `7 \! Y" I5 b2 E6 Q( W        if ( a == 3 )
2 K+ S+ D  L6 ~# Y/ V( o        {
/ H" Y3 i* {/ }5 T! q- d# \% ^            cout << i << endl;
" @- r& q) z6 J3 B            return;
! ]2 p3 T9 H4 m0 a: W        }
- n6 e1 s$ N; Z  j    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
8 n+ y& S, M  ?& R/ Z) ]}
! G5 |0 z' L4 T3 g; X
4 o, P$ ]3 R/ ~) a/ T0 l
6 p3 f' S& K/ o/ @4 I% B7 F总结：
. k5 \+ Q' i+ g    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
4 t" ^# @/ v) W( {' I: ~. g: W5 V# K
for ( int i = 0; i< n; i++ )
! E0 F: `3 h) k4 `2 Z- f{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
* X6 m. W* x! t* S}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

8 u! g0 D2 E& b! ?: v1 S    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
# w, N& k: f- m* @+ b; k
* d/ c4 i+ p7 @; K    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的