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

matrix_spaceman

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

* C3 H1 s; e9 V+ Y7 h2 O& P1: 求1-100之间的质数

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

void fun1()
{
    int i, j;
0 a$ m# f: _' P' Y    bool flag[100];
- n0 o6 m% }. O2 B& e: z' b) p8 G
% D* ~- X0 |& x* h' j( s    for ( i = 2; i < 100; i++ )
# i. A! A" T" L) }        flag = true;

! }/ N7 e3 ]; [$ n    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
, G' ]1 K& q; A- n) `# N- {- k8 P    {
2 t8 H- g7 a  ]9 _        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
; l3 m) x. t3 s+ M4 J* L        for ( j = 2; j * i < 100; j++ )//划掉i*j
8 l) }( P1 b6 B2 T7 T            flag[i*j] = false;
    }

    //输出结果
    for ( i = 2; i < 100; i++ )
        if ( flag )
9 R) \+ U. n# g8 G3 b5 x            cout << i << ' ';
; t/ x) g+ b7 \4 p' E: I1 V" d( k9 H}

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

8 U& o% c- n8 X: \! ^    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

" C* v, c+ N( I# M) \2 d    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
" \5 o; O7 C+ L; y+ k+ q
; A. z( T& _3 ^8 l) V; avoid fun2()
3 \5 `/ l& H: C# G0 `4 W+ J" V/ z{
) w% s, v: s- ^% n    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
! ^9 q* B0 Z) ~" n0 h% i
/ C6 L* n' O6 S! x2 y    for ( int i=0; i< 30; i++ )
        flag = true;
; ^, t# A) ], Y
/ y1 b9 V' Y- f    int n = 30;//还剩几个人
    int cnt;
/ m: @/ p; j: F, A/ B    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
: D/ t' l7 s1 }7 [# @    while ( n > 0 )
+ t8 p2 u* v, M5 n4 B6 k( C4 G2 n    {
        cnt = 0;
8 ?, b+ u7 a# F3 c! j+ }/ M6 [0 d        while ( cnt < 5 )
: K- {# s4 v( c3 [% f6 N, }  [        {
$ a  J  h% L9 O, s, W5 s  o' a            if ( ++pos == 30 )
                pos = 0;
7 m% [" a% \: F: J) L            if ( flag[pos] )//此人还没被毙掉
+ `; N, Y" o7 D' E9 l+ u9 ~! q0 D1 K                cnt ++;
        }
) e  M9 o! k& P9 M+ b* ?$ \: H' @; X        //退出时cnt == 5，pos指向报5的人
. S2 M& l/ I$ ^        flag[pos] = false;//毙掉
        n --;//剩余人数减1
: m6 y9 @* Y  `% l# G: ?2 j    }
# `# }) F' c9 z* z. M: y    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
}

3: 一个数被5除余3，被7除余2，求此数最小为几。
! c/ y* O3 J- [
/ ^! y; D$ ]; F' i2 O( @* f: I3 ]    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
, \. i  Y7 _. m- E: k    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
4 W4 w/ G) ]- f4 Q  d& E7 c
& ], }, i6 R& y; u- x- Qvoid fun3()
{
* D0 V3 ~9 n. K6 f0 Y6 W" q    int a[105];//105 = 5 * 7
- k2 [7 |% s2 x2 R& `. i2 j2 _    int i;
( l% w. M9 k0 M    //计数清0
: b% k/ _& S$ ?. U% w    for ( i = 0; i < 35; i++ )
" z& S8 H: x: M8 R% c) l        a = 0;
3 P3 Z; L' Y  j7 X9 R. {; ]    //开始筛选
    for ( i = 3; i < 35; i += 5 )
" g2 W- ^0 ?" i% V" R3 X# l) ?        a ++;
% g% z: T2 h0 o' M1 ]7 M8 Y  ]    for ( i = 2; i < 35; i += 7 )
        a ++;
" Q5 H5 t; f. R  a% ]
7 m  [# o  q! i, r. q    for ( i = 0; i < 35; i++ )
9 n+ ^% O& H1 E5 s& K        if ( a == 3 )
; h' x1 S9 U/ A/ T; \9 F: T, F        {
9 a; q. ?) K9 f4 H* C/ U            cout << i << endl;
            return;
        }
1 |- W2 v5 r, q    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
}


4 c7 e0 U: A8 C) ?总结：
0 j( ~  G0 H' k( O7 d5 J" |    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
. ], F- m$ _& l( Z9 f
( g( [5 Y# r& x3 Q' p& Bfor ( int i = 0; i< n; i++ )
{
/ r) w3 S8 D1 Q; t    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
, J$ n' `9 k0 C5 ~( o! x}
. W$ f: I' r7 y' ^- B# _    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

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

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