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

matrix_spaceman

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

1: 求1-100之间的质数

    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

. Y' k8 ~: q3 n2 z6 ivoid fun1()
! o- p1 _" b" l  S5 t{
    int i, j;
. g2 h4 l& `$ n; ~7 v2 Y5 H6 W1 w9 p    bool flag[100];

1 p; r3 C* ^& f3 M1 c5 C7 l    for ( i = 2; i < 100; i++ )
        flag = true;

6 V- D: k) O( N. f    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
4 B# x) R$ c7 q/ X. E1 T# C        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
+ R3 ~" |8 W) F* Y9 I            flag[i*j] = false;
' x5 B+ p# t- C/ t8 n# J0 M    }
) f' ^1 E6 c: U" k# ~- r
    //输出结果
    for ( i = 2; i < 100; i++ )
. ^3 O; h  O' l3 N' M        if ( flag )
; i) m- i' T6 y) B            cout << i << ' ';
}

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

6 `- a1 g% ~& s+ X$ z    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
& y/ f$ G$ z& f2 s: W/ Q0 @
" G0 v+ |4 x6 R4 C9 y+ f! E    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
' F6 i- n4 I& d# P/ K: n
' D7 t, x- _$ {0 z$ B* e! \3 Ovoid fun2()
{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
3 x& a0 i: n# p2 R7 ^( P* y
7 z( Z9 @" Y9 O# B" |: X; {; b    for ( int i=0; i< 30; i++ )
        flag = true;
) Z# z5 j9 M, @% c% c8 p$ v" d$ s
    int n = 30;//还剩几个人
9 @4 G: p! C0 K/ |' t# W    int cnt;
2 O) B3 \% P1 X+ f# k- M. b    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
( I4 _, m6 Q# F    while ( n > 0 )
    {
        cnt = 0;
/ P$ P' D( u! L% ?        while ( cnt < 5 )
4 D- }: f  X9 ]$ T1 `; Y        {
; @- x; k- n" w, P) f' c$ v( Q            if ( ++pos == 30 )
3 ~) t* W+ _( B/ j- F                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
" i# p+ Q" C" m: N, Y/ R; H6 Z0 l                cnt ++;
; }/ K3 N' s  C1 f0 M! }        }
2 A2 j) |) K! y! S. {        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
        n --;//剩余人数减1
" P4 `# X" @- k7 [- |    }
    //最后一个被毙的就是幸存者
, h! Y$ L: Z5 q    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
4 D5 R3 E7 ]+ T& d- x4 ?}

3: 一个数被5除余3，被7除余2，求此数最小为几。
% h7 j9 y2 P8 D/ R
2 Z1 _1 [% c+ q7 ~/ H! Z    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

6 Y2 n" h  b: n! Dvoid fun3()
{
8 f+ p- d& T6 t2 D    int a[105];//105 = 5 * 7
    int i;
) u% x4 M5 O, a# n8 O    //计数清0
0 K) Y: E0 _! m/ {5 z) z, }    for ( i = 0; i < 35; i++ )
" a& v2 j4 N, a6 }, _# e        a = 0;
* l+ ]. f: V* ^3 q    //开始筛选
    for ( i = 3; i < 35; i += 5 )
# `; J  W8 J& n" f        a ++;
1 o( Q# z! ?. b* B' l    for ( i = 2; i < 35; i += 7 )
/ j% u% I7 k! M7 F/ M0 L! _        a ++;

- q) d! H: ?9 l/ u& J/ U) j    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
        {
- _7 ~2 T9 g8 ^            cout << i << endl;
% X9 [# S  f3 V& G            return;
        }
7 k+ K7 l' F0 }6 `: Z    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
}


; N- q1 o8 J% a# I总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
4 C5 e% r4 D8 n. s+ D) X
6 b7 x& P. y7 k4 I4 {for ( int i = 0; i< n; i++ )
6 V- |) J- {. o  z. J* A{
) p/ B' A. ?: o& E3 f% e    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
- s3 @4 z$ I' n/ v, f2 Q0 U  Z}
. a8 y. D  J  w9 q8 z    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

$ ?5 C  _; _3 H2 s) [4 g* V7 n0 p$ w    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
( `- N7 o! O, K0 }- N8 \4 T, m
( I8 _! _* |& O4 n" I! \0 j    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的