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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
0 n! n6 }4 w' q# P! h) {4 l
& [3 Q1 ~- E  c1: 求1-100之间的质数

: x7 k& X: m' F- Q! ?- v  m% \    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
' S8 i8 z; v; y8 U. Z{
2 n: e7 R- I2 o+ y    int i, j;
    bool flag[100];
6 j  w! ^* e* r2 P
0 T# u" P# N6 u- h0 C    for ( i = 2; i < 100; i++ )
" @' d! t! Y  z6 I3 G, y- Z        flag = true;
/ H& A$ @; I4 ^. S5 |  F4 j4 H0 ^
! G6 R, Y2 @: e/ h    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
0 v4 w: S, R6 c$ H* S' G. `        if ( flag == false )
. F( h7 \- P: A& o$ C* ]: G            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
    }
/ q1 H5 R; s- U# o" D$ h: ^1 G
    //输出结果
% I! u. V; `: Y, o; x0 j    for ( i = 2; i < 100; i++ )
        if ( flag )
            cout << i << ' ';
9 G: D, D2 Z3 k}
7 E1 v5 U" s1 c# B- u, Y- X  A
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
. A/ w- S. ^/ E' ]% O- z5 e; r2 z7 s. h
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
; P" S) O. F$ _1 R& T- I2 n
    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
: @5 D! G( s, Z9 y3 g+ A% ]
$ B' V  g- ?  L! Q. F6 G$ C" @void fun2()
{
' j6 e1 ]* k- Z    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

% \; {  j2 n9 L" o- K    for ( int i=0; i< 30; i++ )
! M, ]; \8 k/ O# v) y1 ?$ \5 h$ i( C        flag = true;

    int n = 30;//还剩几个人
4 _* r( [/ }: d# I9 }% V9 f+ f) Q8 T    int cnt;
' B) ?, a2 D# v) x    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
0 `; ?7 c  n) I$ c" a    {
        cnt = 0;
9 y& O9 i# T/ F0 W        while ( cnt < 5 )
) z, b) l2 s, p        {
% b: o  \' F8 k" f0 u            if ( ++pos == 30 )
4 @) @& T. O0 i3 M                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
4 f5 P7 t; `/ i4 T4 g4 V                cnt ++;
        }
        //退出时cnt == 5，pos指向报5的人
2 A: Q$ ?& B$ l' _4 x2 z, v' @        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
: R& A# _* R; u; V) B+ {! H}

8 U5 V! B! ]. B1 L; H8 b3 c" v3: 一个数被5除余3，被7除余2，求此数最小为几。
4 C% m( ^" p; C; h% N" T7 g
    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
& S, M4 Z, R3 }5 M) T- |    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
4 g+ w8 v+ z- b( T
void fun3()
* }& z- M4 I( U+ {{
    int a[105];//105 = 5 * 7
) K0 f# A2 K: h( p    int i;
    //计数清0
  U. m2 o% k; o6 c9 q# ^    for ( i = 0; i < 35; i++ )
        a = 0;
9 s/ \7 |9 {' T4 o    //开始筛选
    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
        a ++;

    for ( i = 0; i < 35; i++ )
- t1 O  V! w6 ^        if ( a == 3 )
        {
            cout << i << endl;
0 |0 B; y7 i, h0 k: g8 ?1 G# ?            return;
/ l6 z8 m- \: {1 E8 C        }
( G& K7 m. E4 G4 E    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
}
' s0 c1 I# r, s# \  f, ^7 U

总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
, b, T9 m0 y  J+ w% ~/ C
$ r0 V0 \8 F7 _5 Qfor ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
; S0 l8 g! S( V}
1 G! h. I: k' ^    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

$ r+ S- |3 g* r& k# X    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
- `) h8 x7 N* O  a% z7 O
$ X. L/ n, E2 q5 O4 t    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的