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

matrix_spaceman

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

' u7 q, Z. c1 n1: 求1-100之间的质数
) i  s( E9 f5 n5 B% E6 t1 ]
    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

! ~  }/ @6 p' @2 ovoid fun1()
: g: P& a) }, X; [4 E% l{
    int i, j;
$ x# C0 C" X: h7 `1 q  Y5 p5 \    bool flag[100];
+ _" E7 A$ y0 a& [7 P6 f
0 q/ P  f' Y2 B7 m% l! r! i( S    for ( i = 2; i < 100; i++ )
        flag = true;

    //下面开始划掉合数
2 }1 [0 m! |7 d& Z6 P9 Y    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
$ h7 F" |8 |, T# k    {
; E2 D. O- B$ }, i: s        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
8 {# I7 V% Y, N- w' l  m/ I            flag[i*j] = false;
. U6 V" K. m: L# q, H- t. }    }

1 k0 a4 ^6 L6 J, D2 c( n    //输出结果
    for ( i = 2; i < 100; i++ )
# J) _/ d2 w/ J) {: w5 z" e        if ( flag )
            cout << i << ' ';
}
+ \, M6 {" z. Q' U( Q9 Z$ y0 Q: l# Y! Z
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

; Z5 l# W% K1 \) I0 |+ s    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
5 R1 z$ |8 D, D) c8 E; o
void fun2()
{
9 k& n2 W# u( z/ p4 C: C    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

    for ( int i=0; i< 30; i++ )
. N  J7 r& N% W1 \  J( U        flag = true;

8 i& z$ a; y- o( o    int n = 30;//还剩几个人
9 w4 U- Y0 c5 i) R1 y3 N    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
& Q* G% }! G( {) V3 ^    while ( n > 0 )
& i& y! T$ V4 @' w9 e8 O    {
' I* y4 y3 U/ Y& W        cnt = 0;
0 E) w7 q) l1 G7 Y        while ( cnt < 5 )
        {
% A3 a: P' {: X) k( r, V* i( L            if ( ++pos == 30 )
                pos = 0;
' {: K* R, p6 A! a# R1 S, B            if ( flag[pos] )//此人还没被毙掉
3 s) }. Y0 a/ {4 c5 D* K                cnt ++;
        }
; d3 F8 R# j+ p4 `" F7 f* K0 m$ J        //退出时cnt == 5，pos指向报5的人
( P$ m) u! B- r$ J5 L/ \        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
- G% q. O, {: p& G  x& c: E) L    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
1 `4 ~0 W3 |% X; F+ i    cout << pos + 1 << ' ';
}
  u8 K& {7 b4 d! V( o
1 s! P# T; ]: K  N1 n4 k: q3: 一个数被5除余3，被7除余2，求此数最小为几。
$ U& {7 p% s7 G2 q
5 I+ z: }6 w# h- r+ K) Y" N6 e    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
1 ~( U+ |% A3 j    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
4 }6 U# v8 v2 V
void fun3()
{
    int a[105];//105 = 5 * 7
& @: K$ d+ W8 K/ _/ ?  j    int i;
    //计数清0
    for ( i = 0; i < 35; i++ )
4 x( ]4 Y$ m. `# r% U        a = 0;
    //开始筛选
  h: u. {0 u/ e/ _: _    for ( i = 3; i < 35; i += 5 )
9 {" P1 V1 Z2 I3 ~        a ++;
2 m7 v, @; d% z* M# @9 q  J    for ( i = 2; i < 35; i += 7 )
        a ++;
* ?6 l  f& O' c9 y' r* ?
    for ( i = 0; i < 35; i++ )
4 q: P, `6 H% H& o        if ( a == 3 )
        {
$ u- U1 X7 u! x' X1 z0 u            cout << i << endl;
            return;
" P' a% {+ K0 m; A6 r; S* p        }
    //如果执行到这里说明无解
: V% ~' C5 d3 m. Q) a7 O+ B* X    cout << "No Answer!" << endl;
1 b+ Q. ?! v2 M1 N2 S}
; M& ?0 w. o1 z+ H

/ p2 R3 C. e0 P: ~# Q" U+ ~+ |总结：
4 i2 R% J% T0 Q5 \0 X+ S    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
7 u% M4 F- G- D. d+ k
+ Q8 ~: Z* U; z5 pfor ( int i = 0; i< n; i++ )
: C) R) t8 w2 g  U$ t{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
$ g: B' w/ j) A3 R        cout << i;
}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
8 e' t: p( B( g5 h6 H% [8 S; y
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
* Q1 X5 N( A. o  w' R, h% g  `
8 L8 p  }3 Y* O" F7 K: n* y9 z' v    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的