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

matrix_spaceman

所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
1 d/ K" X  Q2 d5 G8 R
, x$ @1 D- R9 s" X1: 求1-100之间的质数

    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
& o$ l6 z3 v* ?$ Y; V5 C) b: ?
void fun1()
{
    int i, j;
: F- }' E3 Q! o* Z0 [0 V    bool flag[100];
8 @% o  U4 o3 o1 }( u
# G. P3 i1 k2 d/ u0 M. g' W    for ( i = 2; i < 100; i++ )
6 Y! K1 C9 j( T/ i0 s, ^2 n        flag = true;
8 r1 A2 U" v1 h+ N7 o
2 P' A8 I+ x8 y. E* }    //下面开始划掉合数
% n$ G2 [: Z4 g2 _$ t2 t, h3 {    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
' G8 V8 G# @% l0 l' `    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
0 p& v( {- B4 T( U            flag[i*j] = false;
9 X, O7 k2 a4 b3 E( m  q6 T    }

/ ?$ T$ y9 J1 H; A3 A& }    //输出结果
    for ( i = 2; i < 100; i++ )
. Y% \  ]4 \! S/ ^        if ( flag )
4 I6 F) @& W+ s% c& s+ A            cout << i << ' ';
}
. A/ K& J/ q* C# J3 r
, W' a7 b- s; k8 M  ~. A2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
. |  V* I3 R6 Y0 p; @& O* q
9 d; g* [5 I& \  t1 S9 N/ o# C    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
2 G" \/ ~9 N) c' w) o
    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
5 K$ `- K0 e+ b& i8 h2 b
void fun2()
% S7 l6 m" P% v{
$ Q+ |6 s  e0 Z7 |. {. o; S3 b- ^    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
2 u* [. s, X$ e
4 H9 e/ i" x0 L6 F+ U) _1 c; r    for ( int i=0; i< 30; i++ )
        flag = true;

    int n = 30;//还剩几个人
5 O2 v3 x% S, O- }% n    int cnt;
; @: @( }4 F8 R3 ~9 }: M7 ?1 L4 M! `    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
0 w/ m0 g$ `2 ]" Q    while ( n > 0 )
  L) i9 W" l, `4 v2 l. _2 c$ F    {
        cnt = 0;
7 `( \# L' j) y) X        while ( cnt < 5 )
3 g8 _& W1 l- a2 M" d2 K        {
4 D7 k2 L/ X" J+ @- d$ _            if ( ++pos == 30 )
1 K' w1 E: L) H. W9 L( G                pos = 0;
4 M/ p" _2 U5 A( O/ V            if ( flag[pos] )//此人还没被毙掉
2 r& r& V, D  f$ ?                cnt ++;
+ i9 W% W. T0 l$ {2 m& W        }
$ k; T& u; |  P. r5 ]        //退出时cnt == 5，pos指向报5的人
8 {3 R, b' D0 w: w        flag[pos] = false;//毙掉
        n --;//剩余人数减1
, F4 _4 @- Q& ~; {: k    }
    //最后一个被毙的就是幸存者
4 D0 G6 f5 H% h  e0 L2 A( h9 b' U; z    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
- k/ c9 x2 o- k+ x1 U3 r    cout << pos + 1 << ' ';
- x/ K" w+ ]' H7 ~: }8 y) K" k( U}
# G. H( m  y0 |, p" N: i
3: 一个数被5除余3，被7除余2，求此数最小为几。
- J+ r+ G7 k6 ]0 ~
$ f) y' u! s3 i/ ?4 R( ^( X3 G    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
7 O; z( p6 q1 I0 \9 d    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

9 G% @3 V7 h- g" Mvoid fun3()
* g* c  n- u6 M7 e3 H{
/ z8 ^8 M6 d4 b4 G    int a[105];//105 = 5 * 7
9 o* {( r- i# k    int i;
/ d* d4 i4 p  {6 X    //计数清0
5 r% T+ N( O9 r  g  W' {+ u0 L    for ( i = 0; i < 35; i++ )
1 \% B4 H' D4 c$ W# q0 A- m! r        a = 0;
. F% T* m! W8 @! I( y) C    //开始筛选
    for ( i = 3; i < 35; i += 5 )
" ]+ ]4 Y% t* e# ]! d        a ++;
    for ( i = 2; i < 35; i += 7 )
        a ++;

    for ( i = 0; i < 35; i++ )
5 @; J- p7 D8 Y4 Z9 U        if ( a == 3 )
        {
            cout << i << endl;
# B+ L1 e# Z9 |/ v- U: q  H            return;
6 D% U2 u# b: v# E" q        }
. _( O+ b* i, P) G; c    //如果执行到这里说明无解
9 }6 A, b$ u% \+ |% Y    cout << "No Answer!" << endl;
* a- H  L: l/ w& L9 D4 N2 X' T}
1 W: [7 c) h3 X/ X1 C' ]4 a

总结：
; A1 O6 {1 m6 V    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
# ]- L: ]+ A! i- E& a
: g7 Q: Q  J+ q" M! W# p- ffor ( int i = 0; i< n; i++ )
9 c9 U) \) o, Z) C' h' ~$ G{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
9 A2 K, N3 j5 S0 |6 h% Y6 k$ t
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的