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

matrix_spaceman

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

1: 求1-100之间的质数

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

void fun1()
* m7 H3 C8 U& U" t& o{
    int i, j;
1 G9 n1 c6 O, d  I# x( j0 B    bool flag[100];
8 Q, P# d: {; h! c
  [# G/ d; a8 Z8 W/ J& E    for ( i = 2; i < 100; i++ )
        flag = true;

    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
" g, `$ S; m& u; \9 t  M    {
* U6 x* C  G+ q' T        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
; c* |- a3 M! U1 Q* P        for ( j = 2; j * i < 100; j++ )//划掉i*j
# Z5 c' S' k  }9 s2 o' ^2 W! v            flag[i*j] = false;
; b5 }5 o+ [. d    }
- }3 L& s2 U: |- s3 f
" K3 r( f7 O" y% R6 s, E7 e    //输出结果
    for ( i = 2; i < 100; i++ )
3 t$ E6 D- J4 a: Y        if ( flag )
            cout << i << ' ';
! v/ d9 ]$ G7 q- M% s/ p! H# E  j, L}

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

( Q( f* ]* H; j7 q+ @$ X, b    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
2 {7 G" w5 r0 x) q9 b6 t
. ?' F6 o- f8 h+ Q    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

void fun2()
8 U0 G' }/ M: I8 [4 y9 G3 ?  x{
8 F: c4 ]! m: p! Y    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

    for ( int i=0; i< 30; i++ )
  e' Y8 }8 G/ N# K& e; ~        flag = true;

* q" c. x* v) K$ Z& I4 n0 W    int n = 30;//还剩几个人
    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
5 O6 w9 r9 q$ r2 V9 l6 _    while ( n > 0 )
    {
        cnt = 0;
        while ( cnt < 5 )
/ r. n0 m; X9 I5 Y$ g0 u        {
            if ( ++pos == 30 )
                pos = 0;
& `& E7 e5 B/ U; U6 S, W            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
4 \/ ]  W2 B/ J/ \1 _# N" t0 f        }
        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
    //最后一个被毙的就是幸存者
( M- T9 c/ U/ C8 |1 c% x    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
" J% \' Y3 H/ C$ @- I9 l    cout << pos + 1 << ' ';
% F3 q* D+ T% H9 ]# \% t, L}

3 c+ i$ o$ h0 T3: 一个数被5除余3，被7除余2，求此数最小为几。

5 U2 Z( h: b- Z" e3 a$ j/ |% A    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
, r  ]* v' W2 b+ F    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
+ W* ~, j! A( q3 x8 j& T( U) g# P% B{
    int a[105];//105 = 5 * 7
    int i;
    //计数清0
; S: t/ f1 e# T- ^    for ( i = 0; i < 35; i++ )
% c$ w" n! |+ ]+ [        a = 0;
& Q' y4 f1 P# i" x$ V/ f6 _    //开始筛选
6 J  z! y" u% h6 ^' Q. f% m    for ( i = 3; i < 35; i += 5 )
        a ++;
# ?6 i# K* X8 ~" U, k    for ( i = 2; i < 35; i += 7 )
- X) L& F# P' ?  ^, b9 k# u* `        a ++;
$ f" m) m9 ]$ O, ]: m
    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
# _1 Q- f' V6 [2 X% t        {
            cout << i << endl;
9 G. ], p) f+ k% _1 U; H            return;
        }
    //如果执行到这里说明无解
# w1 R  g2 E; \' b! X    cout << "No Answer!" << endl;
}


总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
+ ^/ i8 X$ `8 }: L! @9 j; \3 Z/ h! s
3 P& b" }, A5 T$ P& b, y" @for ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
}
1 M' @+ ^: S" l+ R' t# {0 p# c0 K    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
( p$ B4 J9 r; _+ |  I8 K8 {+ V
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
/ c5 Y/ e* ~6 I7 V; J& F
    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的