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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
0 e% S6 h- V+ D; v
+ ^- c/ b0 N4 O. A: l/ o1: 求1-100之间的质数
/ U8 a3 i+ Q, Q, P
8 F* l9 t5 e& T0 F) {1 ?& J0 t    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
{
- z" E' H& H: [8 g+ S6 p, E    int i, j;
    bool flag[100];
+ Z; L3 M7 l; _0 u4 F% R) p  z
7 l4 e, m4 K" L2 d+ [: ?: G, q2 p    for ( i = 2; i < 100; i++ )
        flag = true;
  r2 B1 j4 G2 D0 n1 m2 J1 q
    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
2 P; ~7 V$ |. h0 h& Y& e        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
% e7 g. M, C) m! K* z; D        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
    }
2 y, u5 H* F) ]! g$ E# O  E; \
+ F  E, E" C, _5 O    //输出结果
- k" g" e5 K8 K6 F    for ( i = 2; i < 100; i++ )
        if ( flag )
            cout << i << ' ';
}

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

void fun2()
{
0 @/ G& V6 T% e- c$ k6 _    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

1 B3 j7 d2 ?$ [    for ( int i=0; i< 30; i++ )
        flag = true;

    int n = 30;//还剩几个人
, y9 P! Z; p( [    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
3 M+ g4 k5 t2 |; F- S  O    {
        cnt = 0;
        while ( cnt < 5 )
        {
            if ( ++pos == 30 )
                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
2 Q. A- G6 X! O                cnt ++;
) j" y+ Z' ~$ a- k& J! }3 x        }
# B7 X2 H0 g% L/ k/ k        //退出时cnt == 5，pos指向报5的人
9 `4 j+ q3 M* I; |( f        flag[pos] = false;//毙掉
+ i+ f& E  }! `3 z* q) @. B9 r  J        n --;//剩余人数减1
( r) }! t0 K: L/ a    }
% ?3 c& Y1 X. R( _    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
}
6 [2 k2 r; v- t! R$ H0 X
3: 一个数被5除余3，被7除余2，求此数最小为几。
  J. L8 i8 W$ t( G2 |& ?. B4 K& m
  L' ?- J8 q1 @8 k/ H    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
( d0 t$ \6 |. R. A. G3 K0 r    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
% I7 t8 [% y: W7 J' L    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
{
    int a[105];//105 = 5 * 7
    int i;
    //计数清0
! [% j# ^1 a6 B+ u7 o1 e& a    for ( i = 0; i < 35; i++ )
        a = 0;
$ _* R4 l2 l8 z+ s+ N8 B, o1 J    //开始筛选
    for ( i = 3; i < 35; i += 5 )
        a ++;
' c3 V% i1 H+ _# A% ]; G    for ( i = 2; i < 35; i += 7 )
8 O9 W( @' h2 B; z# ]+ t        a ++;

    for ( i = 0; i < 35; i++ )
; H4 P! l$ L+ |0 b* Y2 |        if ( a == 3 )
; S) h2 Y' q' {. {+ ~        {
            cout << i << endl;
            return;
3 S, N: j' L$ T- M% \4 ~5 H1 b        }
    //如果执行到这里说明无解
6 d3 l- u" `. A: @  [" K    cout << "No Answer!" << endl;
; `+ c- D$ b3 ~}
, g, C; r- v2 Q7 V
0 b7 s, Q' t6 G9 A- z
总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

& u/ H! _/ X7 N6 G3 Ofor ( int i = 0; i< n; i++ )
{
) `% f8 b9 h# \/ }0 ]    if ( i % 5 == 3 && i % 7 == 2 && ... )
" ?1 Z( e6 }' y9 q        cout << i;
}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
* R* O  N; _4 `; z* d3 J4 c
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

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