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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
/ K. b7 R9 K/ u5 T1 t1 T+ w& v9 }; I- V
1: 求1-100之间的质数
5 H  r" j& ?, D* l$ z6 D
1 c2 r! v: H3 s' j0 m    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
7 u: |+ P6 y" \" f{
2 K4 j" H; [0 q% H: e    int i, j;
! y$ g0 L8 Y1 H$ w: P. t    bool flag[100];

( h0 U, D( A5 ?* G4 \  k    for ( i = 2; i < 100; i++ )
( O( }, l6 T9 w        flag = true;
  O( h( O6 V5 @8 D1 g
) e& G# w7 X8 O, b4 D7 Y- i5 b/ p9 R    //下面开始划掉合数
# q- J5 B+ F+ o! D    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
        if ( flag == false )
- Q$ }5 V, l2 I6 `* ?            continue; //既然i已经是合数，它的倍数应该已经被划掉
+ f6 Y& l) ?: g' @8 k        for ( j = 2; j * i < 100; j++ )//划掉i*j
: I. i* B. j  Q; j# S            flag[i*j] = false;
    }

7 e1 ^. r1 W$ {- E4 d3 z    //输出结果
    for ( i = 2; i < 100; i++ )
4 b, V+ ]2 F1 ?, @1 ]        if ( flag )
            cout << i << ' ';
5 C. d! \" b+ X1 X) a}

2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

) K- a, K* A* ]# V$ l# x    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

5 u, O! j7 J* A7 N0 e' ^: v4 qvoid fun2()
{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

& c! s4 I, \- s* r5 o, l    for ( int i=0; i< 30; i++ )
        flag = true;
; v: T; T+ I+ {
    int n = 30;//还剩几个人
  G% I5 [4 s- T) m" v7 ]    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
3 S6 i6 U3 T9 P2 {! ~    while ( n > 0 )
, x; t: C* l) p, }, h" R% X8 n    {
( d* _  Y+ v5 z( ~% S3 D5 E        cnt = 0;
        while ( cnt < 5 )
        {
            if ( ++pos == 30 )
                pos = 0;
7 k, l( s6 b. {, K- L1 l" j            if ( flag[pos] )//此人还没被毙掉
4 b) d; A7 O) @) a# X                cnt ++;
8 ]+ M6 \5 j; E! r( n. v7 S9 I        }
        //退出时cnt == 5，pos指向报5的人
2 g8 i7 `: k+ X  J1 i2 y        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
- \9 |" D) W, `3 `0 _' M    //最后一个被毙的就是幸存者
( `. C+ ?3 h3 W    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
) b$ M$ g; n- D& W$ D    cout << pos + 1 << ' ';
2 f$ ?+ l- k% i0 l. A3 Q6 M}
. k0 s% C9 M: T
3: 一个数被5除余3，被7除余2，求此数最小为几。
2 ^5 o0 |; e+ Z0 \
( w6 k& ~- r/ g! l8 R    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
3 N" m2 B2 [6 P. L5 I5 U- u- h    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
' X" q" N$ c) m& H. t{
* Z  G$ X5 j. e    int a[105];//105 = 5 * 7
8 q' Y! L4 f8 ]8 t# A    int i;
    //计数清0
3 ~6 X/ S+ t- o# Z    for ( i = 0; i < 35; i++ )
        a = 0;
    //开始筛选
5 T4 v% b9 Z6 E$ q3 O4 h  i    for ( i = 3; i < 35; i += 5 )
        a ++;
4 Q6 w; o( q; v8 w# k5 M    for ( i = 2; i < 35; i += 7 )
4 K! _' L' j% O: e4 g0 t        a ++;
7 y) \' y7 Y( k
    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
        {
% O! L6 l  W  T# j" ~( y/ @4 f' [            cout << i << endl;
            return;
4 D% w3 h2 |3 f4 D        }
    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
}

) \, @' e& U9 N. \
) @5 z" R2 Y+ w. {3 H5 j: q! @; i总结：
  ]0 K! h; T1 }9 Y& }2 v/ O    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
; c$ f. C; a1 E$ b  F3 g; z
! O# f* ?9 v/ H' ^! t1 R5 Q: x7 bfor ( int i = 0; i< n; i++ )
{
- `- |6 P: I: K6 @    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
6 o2 D  p- \: Q}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

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

/ \$ l& r% o1 }) F3 h    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的