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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
0 [9 ^. @. ], W' z6 l2 t7 l
1: 求1-100之间的质数

    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
. y2 M; m6 s- w5 _3 r0 n2 \
. |' {7 b4 T& U1 J7 _void fun1()
{
    int i, j;
* r6 S+ n) {3 F" m6 L    bool flag[100];

    for ( i = 2; i < 100; i++ )
0 {2 C- K6 I/ g4 p4 V) q2 m        flag = true;

    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
, R3 O2 R7 _! ~5 u    {
        if ( flag == false )
& P# M+ g7 c5 g            continue; //既然i已经是合数，它的倍数应该已经被划掉
6 L- H' A5 ?6 i8 e' X3 _7 z; I2 f: g        for ( j = 2; j * i < 100; j++ )//划掉i*j
8 x8 R+ v( L" \* {) |            flag[i*j] = false;
) s. l& H2 j* V/ v1 R: o    }

9 o5 @) z, ~% t3 H- n, N, ~    //输出结果
$ i0 L! n! p. I    for ( i = 2; i < 100; i++ )
        if ( flag )
            cout << i << ' ';
}
& D2 Z! ~$ ^' V% b! v1 {
( g% v' \( N! E0 f  i" t2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
1 y# Z0 G) `# P
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

4 e2 r3 V: t3 i9 J  I; `    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

3 A9 M' P; p" N5 t: P5 Ivoid fun2()
{
6 \6 Z0 d( q. Z; Q. |" W5 C" s8 E    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
* E0 z& m: y; w+ W/ s# {
" i8 e6 c+ u- k5 \  n+ H% g    for ( int i=0; i< 30; i++ )
        flag = true;
3 ], Y+ r$ E) U3 H6 S- h2 a! b( M
5 Z5 w& M$ J6 a1 y2 S5 c: A    int n = 30;//还剩几个人
    int cnt;
: O8 O7 k9 P* m' c    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
0 ]: j' \1 q/ e+ E) z    {
0 Z7 ~7 v% O7 n1 G0 h0 M        cnt = 0;
        while ( cnt < 5 )
        {
            if ( ++pos == 30 )
                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
, Z* w3 Y& Q- v# I( W8 g  n% w- j1 x3 q                cnt ++;
        }
0 S' b4 Q0 @2 o( i& D        //退出时cnt == 5，pos指向报5的人
8 j( C  ]! F$ I        flag[pos] = false;//毙掉
$ D( Q- o& Z3 ]/ p! R, F  N        n --;//剩余人数减1
* P: \& G3 A. d& f* u" A    }
, G) c4 ?! M, Y2 S) n    //最后一个被毙的就是幸存者
; m- X' m) \4 v3 s8 V    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
5 B# ^" W  @1 F  X7 i$ a    cout << pos + 1 << ' ';
}

3: 一个数被5除余3，被7除余2，求此数最小为几。

8 H! z2 ?5 n( v  G- ?    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
$ [" P: M- [1 B  k, K    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
4 a$ @+ i, O- ^) s; j- ?% A
" L: e1 u. ?0 E5 V# `void fun3()
4 `. X* h* x' I5 a: a7 p8 Y{
! Y# G2 Z5 l9 c: O. j    int a[105];//105 = 5 * 7
    int i;
    //计数清0
& |7 V7 e* ?5 b! y% }# B" H    for ( i = 0; i < 35; i++ )
- `5 u4 e+ E% m  @  b& p& V$ t/ g        a = 0;
) }! N# h/ g; O2 }; r! z    //开始筛选
    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
1 _2 f3 |' E9 s4 e        a ++;
8 i) c$ Y( n' S) j: A
    for ( i = 0; i < 35; i++ )
4 E8 g3 |- i2 `2 o9 B! R" W        if ( a == 3 )
+ V  Z4 h9 t  j$ I  E1 z" d        {
            cout << i << endl;
; ?8 P* {3 C" q2 E' s& l            return;
        }
6 }# r/ s# ?+ d5 S$ V    //如果执行到这里说明无解
6 v1 b6 t' l/ c% s, ]7 G  P    cout << "No Answer!" << endl;
}
+ f% `: ^" @7 r- _5 m: b4 [8 g# e) K" U9 q
( \) G% y- B# `* C1 O. G& u# Q3 _
6 @) d8 {0 l  w2 X. _总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
; h1 V  V' c9 j& S8 G
for ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

2 t: B0 _# U0 o& z/ c7 g/ Q    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

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