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

matrix_spaceman

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

# _) _7 b0 m# [% M3 f1: 求1-100之间的质数
+ ]& d% Z1 E$ @- R6 w* E; ?
    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
& Y  r5 W; L1 R{
% |9 @5 f' A4 d$ t' a    int i, j;
    bool flag[100];
* D9 W3 D- }7 I5 D" {' A, g
    for ( i = 2; i < 100; i++ )
        flag = true;
: D* i: e, G7 `$ l; ?
    //下面开始划掉合数
) Y: P( x. |: c/ e* V$ g. q    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
0 q0 ]* {& o- u- k  a# z4 i1 H. D    {
- `6 E$ l7 R  K1 A. P        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
& D2 k; i0 x% a+ t! \) `3 }. o        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
    }
: i+ y: R& P+ c0 f: _4 L
( U5 j# M) t7 h1 ~    //输出结果
& z+ c7 G/ y+ }- @" }: @    for ( i = 2; i < 100; i++ )
        if ( flag )
' N! v- \  u9 m- v: L            cout << i << ' ';
5 k2 s* H3 c* C$ d7 s}

2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

" w( w1 Y$ Z) D: }    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

% O* s0 o& p8 t9 ?" P    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
6 r. d4 Z! K' H7 [
. f1 y- a$ Z( b2 v, {0 qvoid fun2()
{
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
, R6 E+ Z% D' T0 Z9 D
    for ( int i=0; i< 30; i++ )
        flag = true;
1 @" ]5 |4 {: b6 |. K. U. Y
    int n = 30;//还剩几个人
    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
# G( z2 G) a/ U, t! H# F/ c    {
9 ]3 n7 q2 @( R6 Z, e0 @        cnt = 0;
& {. T6 {0 z: S* f4 f+ e        while ( cnt < 5 )
        {
& [# Q/ W, h8 W            if ( ++pos == 30 )
6 b' A' {1 f3 e0 @2 E. e1 k- b! c                pos = 0;
, Q3 d* I! N+ X8 J            if ( flag[pos] )//此人还没被毙掉
3 B  ~& o; a+ l# L5 V. P/ T' A  ~                cnt ++;
$ d' F# Z3 g$ l2 J        }
        //退出时cnt == 5，pos指向报5的人
: A7 t( B& d/ ]- z% I        flag[pos] = false;//毙掉
8 J0 j. e6 [4 J0 K2 P. w" M/ e        n --;//剩余人数减1
    }
    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
& E( s  B$ U1 Y% \9 q    cout << pos + 1 << ' ';
& Y# \' n; u  n# Z6 R9 P}

3: 一个数被5除余3，被7除余2，求此数最小为几。

    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
  l/ h" @  I1 u2 u! m# b    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
2 |) Q5 ^) T, [7 a3 _/ P6 K- O    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
" e7 n1 D/ M4 V{
& p! q8 J# j, W& I! E2 j) E    int a[105];//105 = 5 * 7
    int i;
    //计数清0
5 {, E" X0 @. l' ]6 r- G6 `8 A1 N    for ( i = 0; i < 35; i++ )
        a = 0;
    //开始筛选
8 Q; Q" _& \/ L4 n) |    for ( i = 3; i < 35; i += 5 )
4 C9 i3 {9 z' |; |        a ++;
    for ( i = 2; i < 35; i += 7 )
, Q4 m& `* F5 G/ N- d        a ++;

8 Q0 ?0 m$ _) F7 F6 l& s1 i. q    for ( i = 0; i < 35; i++ )
6 \8 k9 V% z- ]* }3 {* x' f2 L2 V        if ( a == 3 )
        {
            cout << i << endl;
0 t* D" {9 w# h. k4 b  T            return;
; A1 O6 |/ j9 ]9 n        }
5 z3 P' j. i! E4 P6 p+ @    //如果执行到这里说明无解
6 N- ?& ]: t* O) c- f' Q7 y    cout << "No Answer!" << endl;
}

' V8 B1 }* t' b6 g$ z
0 ~7 q; S* ]; l& e, G% T( m总结：
* U8 ^3 G; C& A    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
6 u& R& d3 \6 b0 I
( S, O' L1 O; y+ gfor ( int i = 0; i< n; i++ )
( W8 i* r1 Z. d8 C+ G{
5 U+ F6 T$ @; K  a    if ( i % 5 == 3 && i % 7 == 2 && ... )
0 v0 {0 t8 h; u4 }6 c        cout << i;
8 n2 h4 w& A1 p  ^4 E}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
  V; L3 D) @  g6 D) i$ u
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

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