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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
( p! C5 H1 Z/ c1 ]. |/ d" C5 b- m
6 F) U$ H/ F2 ~( P* K0 R1: 求1-100之间的质数
4 @/ n% V7 s# p. J
    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
5 a, @! O. r' T
4 Y# j; e% `4 b$ i% _  m% n) v" T. Ivoid fun1()
{
  X( D6 Q: u  o    int i, j;
" z/ Y4 w2 L* b. L    bool flag[100];

+ W8 O' n+ T) \2 G7 x4 p    for ( i = 2; i < 100; i++ )
        flag = true;

    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
* Q* K9 D+ K' v" V% n$ E( N8 W9 G    }
; E; V: Q; n1 [2 r( _  Q- m$ Z
    //输出结果
5 K& x* b) d1 B- m' \    for ( i = 2; i < 100; i++ )
7 P$ e9 ]; T6 |3 J        if ( flag )
            cout << i << ' ';
}

% X& i+ l* L; J8 P5 ^2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
7 D/ s/ y" Z# U; S/ O+ d( W2 d
2 a  P( U8 L: n2 l5 R; |8 b# p5 {    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

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

void fun2()
{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
2 D& @# q6 S$ d) m
    for ( int i=0; i< 30; i++ )
        flag = true;
* u6 w$ w; V& y6 g- K* S7 M
    int n = 30;//还剩几个人
0 i* D" S% T: k# ]% @7 E    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
% |& r, l3 h& Z2 W' L- J    {
  A+ n! Y5 t8 D% _        cnt = 0;
        while ( cnt < 5 )
        {
            if ( ++pos == 30 )
                pos = 0;
- W0 t5 G  l( l5 N( F0 L            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
. I. w: k% b2 f) X        }
        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
% i0 `1 u0 B/ A0 r( C- c$ _    //最后一个被毙的就是幸存者
3 p$ N8 s5 q# c- P4 j! G. T& L    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
( r+ D6 d' O; P, ^! ~8 Q    cout << pos + 1 << ' ';
}

. c, X% p! E+ F9 X3: 一个数被5除余3，被7除余2，求此数最小为几。
+ T5 G* {$ J) S+ J" U
    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
" l4 j4 J- o1 |    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

8 X( n. s) I/ F; E3 Xvoid fun3()
  R7 o; c* L+ e1 x3 ~& ^% w{
    int a[105];//105 = 5 * 7
8 ^: X# l6 z6 i- N    int i;
    //计数清0
( U1 y: k! Y3 {+ e' D& z    for ( i = 0; i < 35; i++ )
        a = 0;
5 y! X' P. g$ |9 N    //开始筛选
9 ~0 ^2 z; H( q& B    for ( i = 3; i < 35; i += 5 )
5 t0 O& A+ r+ F        a ++;
    for ( i = 2; i < 35; i += 7 )
        a ++;

    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
1 e3 [+ v0 _4 o8 @/ p        {
# u; w6 z. V- h% {- E4 z" h$ V            cout << i << endl;
& G# y, d: C( R& p6 i( i: B1 A1 b            return;
4 z% \7 U. L. q        }
3 k9 ]/ j  o8 A9 H    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
. j& T8 i- `) d7 F+ w' I. a+ l}
  u* k# T, B# u! H! v, D

0 `2 w7 `' @- _; p# D9 n总结：
6 |; L" C' Z" o# H4 j    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

for ( int i = 0; i< n; i++ )
{
7 D  i7 b, S5 u# W0 s/ A. J+ o$ F    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
: G+ r+ j/ w( k; w4 a}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
4 {; r: ]* b& O% Q& n7 a9 |4 }5 K
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

1 W8 U* E8 R5 M4 ~# h    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的