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

matrix_spaceman

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

1: 求1-100之间的质数
' F" a. v$ O% r
    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
. Y$ ?2 i. A; @& G6 D0 f
1 p% ?& ^" S. G- Ivoid fun1()
{
5 A& W( S6 H) Q: S3 T. @' Z' B    int i, j;
' \" [- e: c/ V8 j    bool flag[100];

& g& w5 v' o7 a0 [+ L    for ( i = 2; i < 100; i++ )
: w7 B0 _& x& f4 H1 I+ }; h        flag = true;
( a5 `+ @  ~0 S  a- z# b0 @
    //下面开始划掉合数
6 k% f" B6 D( \" P( Q8 h    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
1 Z3 Q% s# `/ G' b    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
    }
5 _8 o9 M* r7 j5 E7 g& n  q. X
# M/ j/ t0 c2 u8 u3 {    //输出结果
: |7 P2 g) E+ R# I" h; ~    for ( i = 2; i < 100; i++ )
        if ( flag )
+ V) [7 N: t3 p" T: M# t0 B0 N+ N            cout << i << ' ';
3 g: x- Z+ X7 O  o/ p}
9 e/ y, v0 f5 J
' E& _+ v* _' S6 _1 W1 \: \2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
  I0 K, G* ^% S4 }& s2 m
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
4 K" E% h0 e' w' |+ d+ \* v
, m/ o* {! ]; R& P) w) T% |void fun2()
& U. P% c+ {! G2 z/ K{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
3 f2 r' T; b/ T: X! I
0 D1 c1 r1 X: Q* F; p6 K    for ( int i=0; i< 30; i++ )
        flag = true;

    int n = 30;//还剩几个人
$ g6 A% a% E$ k/ e/ M% r$ G    int cnt;
0 Z( l' X/ L% C! Q% [# x9 T! _5 |% x6 k0 E    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
  d1 |: i! l: \, E! s; o# l0 K    while ( n > 0 )
1 C2 r. q) C+ X0 \# l    {
        cnt = 0;
        while ( cnt < 5 )
$ r9 ^; R! D3 v: {        {
2 Q' q- g0 A8 \. d            if ( ++pos == 30 )
                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
/ H. K2 i2 W  a5 l                cnt ++;
        }
        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
. s# C( T8 N5 X+ q2 ~        n --;//剩余人数减1
9 t6 P( Z6 d3 |# `    }
    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
' j6 {8 u7 A  @: g& z}

0 _' b1 W6 O4 {3 v' w0 E3: 一个数被5除余3，被7除余2，求此数最小为几。
# W" d2 I: ~% t
; S. M, @' A& b! w. A& k5 m    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
8 k6 v. K# a: r8 m8 y4 R4 x{
/ d" B) W; s1 i    int a[105];//105 = 5 * 7
3 J3 o1 l* J% v8 ]    int i;
: P# ]1 I' \* P+ `; I    //计数清0
' g, ]+ r% W+ h2 T0 d    for ( i = 0; i < 35; i++ )
        a = 0;
" X8 v9 n" a- C% r    //开始筛选
    for ( i = 3; i < 35; i += 5 )
6 c7 t/ l% Q5 p. B% F8 t, t# `6 S        a ++;
' s9 T+ b4 @: `2 m# k8 g    for ( i = 2; i < 35; i += 7 )
        a ++;
8 T' w3 w) G1 _. I" Q6 _& D/ |
; e( e1 U  X  h6 }    for ( i = 0; i < 35; i++ )
. T' Z$ ]  R2 H% T        if ( a == 3 )
1 ?& f  ~! o' U2 t        {
2 }7 i$ g0 J6 K            cout << i << endl;
            return;
        }
    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
}


6 F& |2 k1 L, q0 Q5 _" c# U5 f总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
; M' M5 _( r, h5 u0 d. J* y
2 Y- x# ^# @+ q2 E. X" T) C* }$ Zfor ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
# Y5 _# T- b/ S6 L}
' b7 h& d+ J8 S+ E: `/ l3 F    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
+ w( n  I. p$ h1 _' a6 ?3 a: o2 h
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
8 R1 D$ n! a- k- o8 L0 p" U
    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的