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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
, U6 P8 D1 `/ s
1: 求1-100之间的质数
5 a( Q! b' ~+ z0 G- b2 Q
    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

. v) F& p' Q3 i* b+ u" J: hvoid fun1()
{
    int i, j;
    bool flag[100];

    for ( i = 2; i < 100; i++ )
        flag = true;

1 m$ ]& N$ Z( C/ Q; D    //下面开始划掉合数
& _- R& l9 K0 g5 ~    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
. R' N3 e0 Q: ^        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
1 q$ U& p/ T+ C7 W4 Q. k# x$ [4 x        for ( j = 2; j * i < 100; j++ )//划掉i*j
; Y3 H; d& |- Z1 \            flag[i*j] = false;
    }

    //输出结果
# E+ s! ~; j8 A* @& S    for ( i = 2; i < 100; i++ )
: s2 W6 s& z$ o( U' @8 z        if ( flag )
5 H' u! }# x$ k( W% b            cout << i << ' ';
}

  h' x; k, X, M% R8 p2 ?2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
5 f- ]% o8 i: E1 y+ L
    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

2 T1 D3 N/ F1 ^: L* B5 G. v9 o$ E6 gvoid fun2()
{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

    for ( int i=0; i< 30; i++ )
        flag = true;
1 j, t+ C' a7 E! D6 b
    int n = 30;//还剩几个人
    int cnt;
0 ?6 y/ m6 k& J* ]( D    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
. s8 V! p! D% R& R& Z, {. u( c1 z    while ( n > 0 )
+ e' W9 H- }$ U$ X7 J- `! Y  a8 H; E4 |- O    {
        cnt = 0;
3 {, w; k5 y5 W        while ( cnt < 5 )
        {
- U5 }" j/ s6 ~2 F            if ( ++pos == 30 )
                pos = 0;
$ V$ A3 I0 n7 D% U            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
! H- f0 D8 z4 j$ c3 t( E1 F6 m7 Z" J        }
4 @+ r( W; m* ~        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
) g* X$ L+ y, ]8 j2 m3 ^9 V        n --;//剩余人数减1
, F' S! V$ e% b* }/ V    }
    //最后一个被毙的就是幸存者
8 I* o5 ]2 c4 t: y4 v, n- g    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
8 t# E7 Y2 h1 v; T2 T/ V, T}
, h4 E8 S" e' x% M4 [
2 B* |" R. N5 c6 I+ s4 {9 K. u) Z3: 一个数被5除余3，被7除余2，求此数最小为几。

    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
+ ~/ N' O, m& n" s$ f; J    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
- i9 S8 S4 c2 q, a7 w/ U8 }/ h' ?    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

& I$ y- Q0 W2 b2 N' M/ cvoid fun3()
. p, F& u) n" S1 [5 ~+ s' ^6 w{
# E& d% D! Q/ D7 ~& z    int a[105];//105 = 5 * 7
    int i;
- e( c) u/ }: h# O! d, G1 \    //计数清0
    for ( i = 0; i < 35; i++ )
; B8 O( f+ z4 y; |: d        a = 0;
    //开始筛选
    for ( i = 3; i < 35; i += 5 )
6 e* x: r0 K0 a        a ++;
    for ( i = 2; i < 35; i += 7 )
1 I. d. M5 ?: H4 i: p+ d" v% M' }, [        a ++;

    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
        {
3 b  ?1 L9 D" U$ N            cout << i << endl;
            return;
        }
    //如果执行到这里说明无解
  \( n+ y1 }. q! k) X$ R, u5 K    cout << "No Answer!" << endl;
}
* i6 R7 m$ ~6 h9 {6 @4 `) y$ o
/ T! s& _3 G+ Q: k1 k5 s6 N
总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

% S  q3 Q5 N7 Dfor ( int i = 0; i< n; i++ )
{
3 a3 U+ C4 E5 Y' @# w( J+ ~2 L    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
) M( k/ L2 t' S) h% m% M& g; \}
# D3 f+ H, r7 E. a: D    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
5 z& y. H% Q* J
2 h; g! }6 N! ^: W, \    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
. H+ ?9 S3 R7 x9 E6 h* @
    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的