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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
; e8 m5 U3 g  r; l1 g
7 B/ h$ _) f$ m/ M" g4 l1: 求1-100之间的质数
4 V: x  P- x5 z3 \' ~! G
1 ^6 X; X8 I6 Y6 k    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
: D4 l7 A* K% `5 W3 @/ {
void fun1()
- e( V6 A( Y  v0 p# U4 g( y: `{
    int i, j;
    bool flag[100];

    for ( i = 2; i < 100; i++ )
1 s/ O9 w; w  a: n$ Z* p6 l/ c" q        flag = true;

    //下面开始划掉合数
3 i6 j- ^6 m  ]  X& E7 @/ x    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
2 J2 V; X4 H7 I9 F" R& _! D+ R        for ( j = 2; j * i < 100; j++ )//划掉i*j
. w) b6 v5 [6 K; d! Z            flag[i*j] = false;
    }
- d% ~6 C# s/ V- ]
$ i$ a8 A2 H* x) F2 F! c    //输出结果
    for ( i = 2; i < 100; i++ )
        if ( flag )
# L  i) {4 X+ C) Z% W; s' g            cout << i << ' ';
}
! u! }2 M, }6 g
: h3 s+ A0 K* `! O( A1 v' V2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

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

5 f1 h- {, K& V4 O- Rvoid fun2()
{
; R& s0 m2 e: _; Z( B8 E; Z    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

+ p$ }3 G7 i" {    for ( int i=0; i< 30; i++ )
, Y5 F' H8 C* ]* ^! b2 n0 Z        flag = true;
8 }+ n+ E& b6 J4 w% H" w5 e& r
& m+ ~8 w+ m+ p, @    int n = 30;//还剩几个人
% U# m& J1 n$ g& C; h    int cnt;
! d1 B/ v+ V  U* G" C5 g8 Q. j    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
8 o& f6 E0 H( ^5 b    {
        cnt = 0;
        while ( cnt < 5 )
: T, v9 S  C3 n        {
6 v6 j4 R0 D$ D( E0 d1 w            if ( ++pos == 30 )
                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
        }
        //退出时cnt == 5，pos指向报5的人
/ K, j( _0 O! r; j/ F7 l        flag[pos] = false;//毙掉
        n --;//剩余人数减1
( d3 n' F1 b+ a6 X# B    }
! [0 k, h5 z' z% j8 S) S4 \    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
/ q: z; w5 d8 H2 D' S* x) O    cout << pos + 1 << ' ';
}

3: 一个数被5除余3，被7除余2，求此数最小为几。
" \+ C& W8 T2 z- K# @
    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
6 K1 M* ]! [3 R- D
void fun3()
! o: Z6 o- n1 Z{
    int a[105];//105 = 5 * 7
# {8 Z5 B& M# d) {5 s    int i;
    //计数清0
    for ( i = 0; i < 35; i++ )
; b' O6 I3 ^5 M  [* A6 ^        a = 0;
    //开始筛选
, \5 E0 {% `+ C: m; d' B7 h$ ]    for ( i = 3; i < 35; i += 5 )
! G- h& T* J* N2 i9 C        a ++;
& S" ^) ~, I% i/ z' N- p# {0 ~; t    for ( i = 2; i < 35; i += 7 )
        a ++;

( R6 @$ d! R; ?8 _" \9 z) b9 \& c; i    for ( i = 0; i < 35; i++ )
, b% I! r4 l) l5 {        if ( a == 3 )
        {
            cout << i << endl;
            return;
+ e  _! R3 V$ |+ l  M, |        }
    //如果执行到这里说明无解
; o3 a6 f, O" y2 W4 Q* J    cout << "No Answer!" << endl;
. l5 \& p( R# B$ q}
4 t# q! W1 h. a$ t" m+ A7 Z# x
; z/ s9 n* ]# Z
总结：
0 Q7 Y$ g6 t. w+ t5 x, j/ G    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

for ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
}
6 ^$ c) W( M) }5 a6 x1 ~    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
/ l/ W' h+ |, ]+ R7 Y/ C
- h9 U4 B$ E) Z3 l    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的