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

matrix_spaceman

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

1: 求1-100之间的质数
0 d7 `$ c8 B3 h$ u: a) e8 e
    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
. `. F  ~  u% A: `{
- `; `! M9 J( o% R1 p( {    int i, j;
* N& X  n* S% u$ w    bool flag[100];

    for ( i = 2; i < 100; i++ )
# [1 H! [, L7 p( M* V        flag = true;
8 T/ D: W' ]( m( x# y
    //下面开始划掉合数
8 I0 M, _* I" d5 P  O: ]" i- X    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
    }

) e: b1 p" _- ^" E* r  _- H' c; ^2 W' C    //输出结果
6 o+ g5 A9 o3 A# @    for ( i = 2; i < 100; i++ )
        if ( flag )
) N$ G' G7 c0 d            cout << i << ' ';
7 ]7 }* ~9 V7 s2 {}

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

. J" A5 o! Y; g; ~' m  y# W    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
' u$ y( Z4 t6 M- p0 f
8 L/ [) n5 I# I$ T' m0 \3 U    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
% ?7 Y' i, r7 Z0 I% t
& u! ^/ w4 T; J0 y  nvoid fun2()
+ _$ s2 g- h; V) E9 m) F  d{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
; C+ v$ |5 i; d
, H$ H& d$ H) O5 L6 x4 W  `    for ( int i=0; i< 30; i++ )
        flag = true;

    int n = 30;//还剩几个人
    int cnt;
0 t$ P" \# [& D' S4 u$ f, p    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
1 ?& B- r3 U3 @$ Q7 ~& X$ _4 f* ~! j    while ( n > 0 )
    {
        cnt = 0;
        while ( cnt < 5 )
        {
( k4 n! e7 M) Q            if ( ++pos == 30 )
2 n( v7 F' R, H9 T7 C( k5 x                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
        }
. {6 _8 h  i' c/ e, s% i0 [& [        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
3 p# Z5 O8 o8 s) l. f) o        n --;//剩余人数减1
* @7 s3 w2 v6 ]    }
    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
2 z) X8 R6 y$ {$ n    cout << pos + 1 << ' ';
9 K8 ]$ M3 g4 \( o- q/ A}

3: 一个数被5除余3，被7除余2，求此数最小为几。
1 E9 _- w* o3 B5 ]2 n  J3 t
    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

& ^# Q4 [9 N5 _0 ]& {) Qvoid fun3()
{
: f  i  J! k1 c; D) E; [3 _    int a[105];//105 = 5 * 7
" c1 i2 o. u; k2 _- Q0 x    int i;
4 E; p# E, W5 [) W+ b    //计数清0
1 q/ @! I2 v& P8 r; j5 X: D, o! R1 C    for ( i = 0; i < 35; i++ )
        a = 0;
    //开始筛选
    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
$ q" W; L3 B6 p9 y' @: O9 w        a ++;

    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
, G# N) F- y( {        {
: q7 V% j# p: v; a9 _1 z            cout << i << endl;
            return;
        }
' I6 I! j% K; y1 ], ]4 F    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
+ o: Z0 Y% O3 X) R}


+ ?' @  R- d4 a9 T6 n3 j总结：
% s5 R% R2 C) k5 }' P' P% H    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
2 @7 z3 o4 e8 V" n1 N% h2 f: W
for ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
  s- r/ I' G* Z; \' f' o        cout << i;
/ r* @! x0 C" m' b/ L( Y, {}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

9 T, s' g6 a, j7 m* a" \/ O$ p  s    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
5 t8 t3 g! G( S1 t7 E7 K* K
    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的