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

matrix_spaceman

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

1: 求1-100之间的质数

    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
; R" K' F; E  L2 Q0 u
0 P3 q% X- H0 i- o- r! w% Kvoid fun1()
* L3 }$ N3 _# Z, G. p. ~9 ]{
3 F! |8 e7 D' j% X    int i, j;
) ?5 L& j& S/ G: w5 n2 D    bool flag[100];

    for ( i = 2; i < 100; i++ )
        flag = true;
6 }7 }2 M, ^+ g9 `( z8 n
    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
3 w/ D+ o) ^# |9 K1 |! l; A3 ~0 }        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
2 v# r: M8 {7 Q) N- g    }
  o$ n. Y, }) {' K
    //输出结果
. T, X: T7 R# R- z: J7 r    for ( i = 2; i < 100; i++ )
        if ( flag )
+ C" k5 n6 i- g5 R& X8 g0 T; P) Z            cout << i << ' ';
}

2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
4 T9 e9 l, [, P( I" W, E1 ?
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
% q9 b, M6 p  j- r1 h2 ?
7 ?, ^, o. z" D+ @" m" x2 z    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
; A$ x* P; w1 P/ \! d" @9 Q
- g# Q5 r( |( m2 zvoid fun2()
{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
# z$ T3 X1 Z* {" `
( Y- |' D+ y; X" e    for ( int i=0; i< 30; i++ )
        flag = true;
0 c6 x8 X' d) S6 x- t9 T* |
9 z& M7 Z& M; i* ^4 N    int n = 30;//还剩几个人
4 J9 @$ X: F- ?9 S    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
, @3 J; R  Q0 G    {
5 X2 E4 x1 g4 X7 q$ O& N' B) s        cnt = 0;
; f+ o0 M) ?2 j0 E        while ( cnt < 5 )
. Z  I. K. u+ d: d5 @7 N        {
8 Y) e5 ]" {0 Z3 ?3 q9 Z; [            if ( ++pos == 30 )
0 v% |8 j7 z1 c, Z0 F% E0 O% |                pos = 0;
. j- C4 T, q2 B6 C* I            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
        }
, T0 U& w1 Q9 x6 p: w; h+ l        //退出时cnt == 5，pos指向报5的人
/ p+ q, I/ x& C        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
1 j7 W0 h. z( g' \/ \% u    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
8 E9 @, v0 z& [7 a  J& Q}
4 b; A! }, Y7 g: V
& F0 n6 ?8 D2 ]3: 一个数被5除余3，被7除余2，求此数最小为几。
8 D- Q8 V0 l* J$ d; I" y* n
# b+ I* N/ P9 \, Q0 |    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
& h( Y- X; R; ~+ d; f  v2 Q4 h  h7 n
void fun3()
! L7 b0 M( r, R0 S, ~{
& o: f3 V& X* |3 O    int a[105];//105 = 5 * 7
) M) ^! D- O% _1 j" g    int i;
+ P# \3 l; Q/ b. T* `    //计数清0
    for ( i = 0; i < 35; i++ )
) r% O; ]/ o# H# P4 Y$ r8 |        a = 0;
' ?/ a$ r  b5 X- T    //开始筛选
    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
  C1 Z" E" q- c" {3 Z' G        a ++;
$ f$ f, |6 }; H0 w; k2 ^- Y
    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
        {
& ~, v" }6 t0 f            cout << i << endl;
& C! ~3 X1 m% b! {4 o            return;
        }
    //如果执行到这里说明无解
& E4 \/ J, a# j/ z5 `    cout << "No Answer!" << endl;
/ M0 u# y& N, \# b) v) c' I% _}
& e4 Q- x/ W, R" I3 i0 V+ e  K4 f
( c* j, Y1 s0 `' L! h
( e7 z  ?  R, X* c总结：
; d% q" w9 m) Y6 p' ]5 \9 N    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

for ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
; U. u& {" M2 \- ^3 ^+ o        cout << i;
}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
0 d2 ~0 W" M2 Q! @/ ]9 ?' c
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

6 _( d) t' U* z; D. P    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的