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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
1 i7 m" ]9 g+ J" {
. w2 N3 L4 Y/ q$ G1: 求1-100之间的质数

6 Y& `8 g, Z9 h    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
$ V$ A! W7 {( V. T9 Q6 X  @
void fun1()
2 b; c4 \6 u% x1 s% A5 L{
% j, B1 O) R$ g, f4 R. C0 \+ g9 p    int i, j;
  ?2 h/ `$ R# z    bool flag[100];

7 U6 V) D- q8 c9 b    for ( i = 2; i < 100; i++ )
        flag = true;

    //下面开始划掉合数
5 f) y. u0 E, w8 p$ x8 ]    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
        if ( flag == false )
( W5 h) w9 h) Z            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
    }
: j( f! l3 U( x' x8 s2 {# E
    //输出结果
    for ( i = 2; i < 100; i++ )
        if ( flag )
6 ?, w8 e$ y5 b1 s1 ]/ H            cout << i << ' ';
' E$ I4 f# l0 D5 D, k5 E3 i}

2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
# G; G! c2 N3 s! i0 z. q7 m8 w! a
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

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

& e2 ^/ G( p3 p" ^% yvoid fun2()
{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
. ^5 g4 s* ?0 e3 N- a
    for ( int i=0; i< 30; i++ )
" w6 N: Z! m7 G) o  \% U, M8 r        flag = true;
. v5 T5 G' y- k# C0 i
8 ?( I6 n4 ~; w$ F" ^7 x! L/ c/ \+ z    int n = 30;//还剩几个人
# M- S9 a% Z0 k/ G% Z    int cnt;
- F4 x6 _7 ]7 X3 b# U    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
6 q" R. L. i7 R    while ( n > 0 )
    {
        cnt = 0;
0 j& A2 d7 D! u2 s8 L. ^. S        while ( cnt < 5 )
8 o7 h$ R4 p! |# s' _        {
6 u' T! y) @  J& Z4 ^4 Y0 Z            if ( ++pos == 30 )
                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
2 U3 u7 ]. H, r3 E                cnt ++;
2 W2 O" N& [" M% x5 F! k6 \+ [        }
) ?# ^: I0 l0 |3 }: M        //退出时cnt == 5，pos指向报5的人
+ v* f2 W1 Z+ Q- l        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
6 r* D0 g3 H& G) g6 Y: g2 C( X2 N    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
* R0 C) v0 J6 d& Y5 G}

- s/ _6 ?* {" P- o) H3: 一个数被5除余3，被7除余2，求此数最小为几。
6 c$ M8 O1 Y! M6 E9 S8 ^0 Y. h
' u, K! c# r% Y4 {8 O) w1 N& @    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

3 ^" `" e+ L0 k" Z4 l% W) g9 _void fun3()
{
5 Z, D9 f* \% a" F    int a[105];//105 = 5 * 7
* Q) h- P" _# N. P5 C- o6 s. X    int i;
    //计数清0
$ W5 Z' D' P9 C( i, W, l    for ( i = 0; i < 35; i++ )
6 U6 o% ^5 k) O        a = 0;
, r8 P0 n1 p7 F. P9 D    //开始筛选
! a2 g/ L+ ~, F  _    for ( i = 3; i < 35; i += 5 )
        a ++;
2 `5 ]! K4 @, K  X% S    for ( i = 2; i < 35; i += 7 )
        a ++;
9 b' s4 g- V* l, n
) a; Z/ [  [9 ?, v    for ( i = 0; i < 35; i++ )
7 K# D% x5 l  H2 y" K$ {3 f  w! t" G        if ( a == 3 )
        {
            cout << i << endl;
: ^7 a* l* j: e4 K0 _" ?5 D5 ]            return;
+ \* A) b2 f5 x3 e/ d8 a- m; Y        }
    //如果执行到这里说明无解
& ?3 f6 X' C% w8 ]4 Z# x. e    cout << "No Answer!" << endl;
}
0 w& N  [" f/ y2 `! C$ C% ?1 {1 x

总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
0 D  p4 A) k0 Y& _2 E
1 i# V% L, y  N- nfor ( int i = 0; i< n; i++ )
{
6 `$ b6 c/ ^, O! k    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
  B" ^5 T! s6 v# I. `9 {}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
7 [6 p% G* k1 k
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
$ O9 G  ^7 a) U- I: P, o
( ^/ ~, t# F, g1 i8 ~    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的