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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
! o3 _9 c. A# T4 P8 N) t/ k# {# q7 E
1: 求1-100之间的质数

# [' N- T3 d- N3 [2 W4 \    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
# s1 W' j# ]8 a2 U
3 L' B. A* J5 [3 @3 i/ Cvoid fun1()
& x5 [0 K7 z7 N) G4 U8 J% `* `7 A{
    int i, j;
7 t* ]% u* [: O' g, f& |7 t    bool flag[100];

    for ( i = 2; i < 100; i++ )
- I3 {$ u0 S2 N0 K        flag = true;

    //下面开始划掉合数
+ ~  }, e, f9 c    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
4 W8 ]' E, L9 Q; U" q/ C/ j        if ( flag == false )
7 g. n1 i9 [( i6 v2 K0 u7 C            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
    }
2 _) f( A9 b( C; w% J2 z4 A
    //输出结果
    for ( i = 2; i < 100; i++ )
( l+ Z) q" G2 y0 f+ M, r        if ( flag )
  T( O$ ~) o4 X            cout << i << ' ';
& V! l7 N$ Y1 \. Z2 P/ z}

, m8 C/ E$ U1 W2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

9 O! A1 l8 _) k- _% ?4 J    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
  R5 v4 D7 g+ H. e9 G/ r4 ]
    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

, K8 h* K. |% f/ R- s6 kvoid fun2()
{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

    for ( int i=0; i< 30; i++ )
        flag = true;
& A- H2 A3 Y9 J* ~9 S( y1 Q
1 S: g7 n- P4 y( k" J4 @, Y    int n = 30;//还剩几个人
    int cnt;
. Z, A1 W  r% _/ y    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
    {
( l$ ]% v/ j; v# J! j2 n- l8 U+ S        cnt = 0;
) m8 \- m. L- G: J( `6 o        while ( cnt < 5 )
6 G9 G: p/ f( G/ R! ~& Q1 s        {
            if ( ++pos == 30 )
; x  h! j" ^$ N( i                pos = 0;
! V6 r' \( I6 I# z            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
        }
        //退出时cnt == 5，pos指向报5的人
+ R0 h+ Y& S) C7 T+ C        flag[pos] = false;//毙掉
1 O( `. I/ z- |$ i9 q) U3 A        n --;//剩余人数减1
    }
7 ]2 e- S3 t  |    //最后一个被毙的就是幸存者
) I- C. _/ ]5 H    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
" C" x) l3 b) n9 F}

1 v6 ^* L7 c9 K) v9 i! f! C3: 一个数被5除余3，被7除余2，求此数最小为几。
% u( @8 A! F- I/ V" r+ o$ x
    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
9 W% c3 Z# y$ `, p4 G% z    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
3 p! z3 y& @6 r8 Y1 n' Q- F; S6 X{
0 ~! ?* K/ N! B) x# o! h7 K    int a[105];//105 = 5 * 7
1 z& z' [  d2 i' L- ~4 H    int i;
' `5 F; C2 x" `  M" ?7 S: i    //计数清0
- }6 ?& r& L, |4 J    for ( i = 0; i < 35; i++ )
        a = 0;
    //开始筛选
    for ( i = 3; i < 35; i += 5 )
1 U. \1 ~" f5 r5 O7 D3 j* H        a ++;
    for ( i = 2; i < 35; i += 7 )
0 C" _' H* _6 H4 |7 k' Z        a ++;
" d3 k6 x" m% D
5 C* b/ i6 b% N9 A: P& D& G    for ( i = 0; i < 35; i++ )
1 t$ a. ^: ?9 u. M7 A( Z        if ( a == 3 )
- M% C4 q. S  X. T' y) S        {
            cout << i << endl;
            return;
& O+ r+ y5 U% j! P        }
    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
9 `% i; }) c0 G2 r4 w* k  w}

% q. m, D/ i6 u% ]( Y% Q1 `
总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

( v$ M) U& h3 A' V! Mfor ( int i = 0; i< n; i++ )
/ r6 E4 r; y7 T{
: ^" j  q, c, m' P( o. d: m0 {    if ( i % 5 == 3 && i % 7 == 2 && ... )
4 X2 ^* J& k- e, S( _- j* J" |        cout << i;
}
0 r6 V! G3 T) S: P% `. g    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
- H! S# l' y* |# H* ~% ?
    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的