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

matrix_spaceman

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

1: 求1-100之间的质数

    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

; \0 ~+ i1 z1 [) b; X5 _void fun1()
{
    int i, j;
4 K7 m  A( S: w  c6 F8 F2 ~    bool flag[100];
# }% U: F  O( P& c  X
    for ( i = 2; i < 100; i++ )
2 O2 T* U# D8 Q% _  M4 q7 l        flag = true;
6 H) [& Q# O6 E5 t# p
    //下面开始划掉合数
1 @' K+ @3 K4 v5 ]- H    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
9 b: e5 D  H6 c# n) ]& ^    {
        if ( flag == false )
; g4 e  E: e5 O& L/ e  k- V8 \  t            continue; //既然i已经是合数，它的倍数应该已经被划掉
6 f* L4 u( d) y' Z8 {. s        for ( j = 2; j * i < 100; j++ )//划掉i*j
4 z; `" e4 U" [. E( b            flag[i*j] = false;
    }

    //输出结果
    for ( i = 2; i < 100; i++ )
' }% t% O; N# M9 [        if ( flag )
            cout << i << ' ';
}

, Y& Q5 P" R6 d. N- z# h, k2 }2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

/ V# N+ d) Z: X( A' T+ b    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

/ t5 x9 r3 W$ d+ K5 ~+ `$ q+ l    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

3 V9 d. A; D9 Jvoid fun2()
{
$ z% c9 D: W+ Y  w8 @    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
& M" B% ]7 c1 l( y" |
    for ( int i=0; i< 30; i++ )
        flag = true;
& m2 Z( }/ p2 E# z/ A+ W
    int n = 30;//还剩几个人
4 M9 `5 o: b" H9 s( q    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
; K/ ~  ~7 T* `( I4 u: c8 |: W    while ( n > 0 )
" D4 {3 V# n  ]% U% W& s5 P    {
  W2 O( o2 c3 ?) p8 q8 k2 N        cnt = 0;
3 Q# H* Q3 e& x" }  D" O# v5 q        while ( cnt < 5 )
. F( e! ~' w3 S2 v& s- X( n        {
! m2 X0 B) b; h1 y) d# ?2 c, ^5 L3 i            if ( ++pos == 30 )
                pos = 0;
$ u! A. E, x  @9 Q% n% m9 u            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
        }
        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
6 ]8 J( t# P1 D  R        n --;//剩余人数减1
3 R# V) W" {1 i5 U0 B    }
    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
}

- i) h( M% w- ~. l' a  K1 c8 d* `3: 一个数被5除余3，被7除余2，求此数最小为几。

; `+ r  J. v8 L  w+ X    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
. M* X3 \5 w' a- m- E' L  L' [    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
9 `/ z8 w& N. D( {5 e    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

7 _6 I: a2 Z& u- rvoid fun3()
{
9 j0 r3 `( x* B1 z5 ^2 I" t    int a[105];//105 = 5 * 7
- |) D2 O3 k4 {2 x) Q2 \    int i;
    //计数清0
' E) }7 ?  b2 n7 M    for ( i = 0; i < 35; i++ )
        a = 0;
    //开始筛选
    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
        a ++;
/ n+ {! `* G) g6 ^
    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
/ H1 T  F9 x2 ]1 p" c        {
5 q* C1 B! u. G1 j8 }            cout << i << endl;
) V9 h' c' L0 p- P% a( B" ^            return;
        }
) U" Q0 p: g/ ]" |; y    //如果执行到这里说明无解
7 t  F8 g7 V; Y6 C2 G    cout << "No Answer!" << endl;
}
" j$ f3 J% _2 U
. I: w7 w; V& u& Z
6 s) [  C! y0 R* G+ ^总结：
" d' D& y1 K( B$ t    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
/ X8 v2 [6 U% f0 J9 y
* j4 i0 n0 }; o! nfor ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
0 d. u+ M% I( p. [" H}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
0 b: Y$ r3 k9 n1 P  b
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

; T8 k+ u  `# @7 [( [: K7 s$ [    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的