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

matrix_spaceman

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

/ T8 a( L- \( P. P% c1: 求1-100之间的质数

( ^6 t9 D/ V0 L4 o! }. @6 ?    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
; g# q7 w4 k/ M2 Q4 M8 |& T
4 j( c# j' F$ r8 u2 Mvoid fun1()
5 L; a  |! N7 [0 R# j{
  c: T/ k; w# R/ T3 L* [    int i, j;
! k/ J8 v! S8 U& o; f2 ]    bool flag[100];
! Q. z3 \" A+ W
    for ( i = 2; i < 100; i++ )
        flag = true;
% ^* ^4 W/ ^6 C1 E
3 U# i6 z# M$ X3 p8 B9 B    //下面开始划掉合数
1 j$ L& L7 c9 I0 S7 \) S. }' q    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
        if ( flag == false )
1 `4 J, @- h( s            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
1 X- I' w! ^2 V; {( z            flag[i*j] = false;
    }
8 k/ l/ S* y0 \3 i
    //输出结果
    for ( i = 2; i < 100; i++ )
& n8 Z2 f9 Q2 E+ R9 g* z% ?5 o        if ( flag )
# P/ q/ R( J9 T+ a$ d/ `# ], ?            cout << i << ' ';
}
+ w( E& J3 q. n* ]# S
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

/ n3 ^4 w& A- |$ Q# ~; }- A$ d    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
) n6 e5 w/ @% s4 B, d' L- C, Z2 D
9 ^! d4 ?3 V  ?2 i) |% f1 x    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

/ s7 m( c, t. R" m7 z- pvoid fun2()
{
% J8 u- R" R# V; k6 |9 V. i    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
; V! ]# Y2 ^7 U- G7 q
  A' R: i/ C/ b4 X0 P    for ( int i=0; i< 30; i++ )
        flag = true;
, K  j4 }5 t: t) m, W
    int n = 30;//还剩几个人
    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
    {
) d: Y% h7 B) \2 B4 L& `        cnt = 0;
        while ( cnt < 5 )
/ H) i) d+ v) B0 w        {
            if ( ++pos == 30 )
                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
        }
        //退出时cnt == 5，pos指向报5的人
. ]) D+ d2 u8 Z, c0 `5 n        flag[pos] = false;//毙掉
        n --;//剩余人数减1
. |% |; ^" o7 [+ P    }
    //最后一个被毙的就是幸存者
9 h" F3 G( {7 a* C) z6 q1 x3 ^7 @    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
* \8 x" E# P; F    cout << pos + 1 << ' ';
}

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

/ M9 ~+ V1 r+ G* C    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
! }$ ]. P, h8 e5 Y8 [    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
! Q( E1 c0 s0 V/ v1 l0 t" Z" D$ v
2 J0 N5 z4 y, a$ n* T' Evoid fun3()
- ]" R0 c. l2 r8 n% o; `{
    int a[105];//105 = 5 * 7
7 x/ f3 P8 }: ?0 Z* h: y. J    int i;
/ G' l1 G2 @4 ~5 V& Q    //计数清0
    for ( i = 0; i < 35; i++ )
& `1 j7 P  R( e        a = 0;
    //开始筛选
    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
' A( o& Q, o) `8 d) y$ j        a ++;
$ _6 {; q" t9 c; H6 B& f: x
, k3 e( c- @# q' ?    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
        {
: k5 o. u1 m- c) \7 d! L7 U) v0 a            cout << i << endl;
            return;
' {7 P* D" p4 W9 u' O; n+ b        }
    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
}


5 [5 L4 p$ ^: I: l% y* P9 |' q总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
3 x4 b9 o" }, R; H- T' N/ |% L1 I
- v2 O- X7 b+ l! y" f9 {7 pfor ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
* f3 {4 c+ ~& Z; H* |; b}
. u* ^, K- E* h    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

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

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