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

matrix_spaceman

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

' c+ l$ C1 {5 U* g/ ]$ B0 R" R1: 求1-100之间的质数

    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
{
0 Y9 z( T4 q2 g: B+ a    int i, j;
    bool flag[100];

) O) O! @* S' Z& G. {: o    for ( i = 2; i < 100; i++ )
6 b/ W* x" N" P" N' P# H+ l        flag = true;

4 m) [# M1 h* {5 W, r    //下面开始划掉合数
- d, r9 _9 w/ m) n3 q* R5 R  k    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
# ?* Q# l8 H, J# s( |            flag[i*j] = false;
    }
0 a8 `# j7 }" p, ?
" B. G: e& F+ }9 N, V; _( F    //输出结果
# ]# i6 E, x2 o( O( ?8 }    for ( i = 2; i < 100; i++ )
        if ( flag )
: r7 s' b" v+ a$ g! d+ @            cout << i << ' ';
0 m2 C& B! B1 p}
( I3 C9 V& s6 `& s8 `1 _
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

" s1 R+ u* ~0 R4 U  }2 d4 ~    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

: C7 q. B/ {8 k5 Z" I; |" b    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

2 `( l* V$ Q- y/ R# K7 q) q8 x2 f% wvoid fun2()
{
9 ]  \: I* H7 t; p. v7 q& w6 P. z    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

/ W2 W7 E+ N; z- K0 Y- R; g    for ( int i=0; i< 30; i++ )
        flag = true;
$ Y8 w# `, }( x2 o2 Z! a
    int n = 30;//还剩几个人
    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
    {
& N0 u6 v4 i" ~1 r        cnt = 0;
        while ( cnt < 5 )
        {
  e. w  i! R& }& _            if ( ++pos == 30 )
/ W9 I0 _' I+ r0 p                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
        }
& M' v1 ]$ T6 F, c        //退出时cnt == 5，pos指向报5的人
2 A5 I" E8 u, I; I        flag[pos] = false;//毙掉
! U3 T; P- ~" j0 h/ d# l- Y        n --;//剩余人数减1
5 c  f* X" _0 v- Z    }
& X5 Z6 I; G, P    //最后一个被毙的就是幸存者
8 M8 b' h( W8 x* m6 h* e    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
- c7 P) j# U3 f$ l}
; F9 I$ o* j1 g$ `4 A( p% R% e
3: 一个数被5除余3，被7除余2，求此数最小为几。

    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
) N1 t+ s, x" ~: r' p0 H    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
1 \* t! |7 x, b- ~9 r{
    int a[105];//105 = 5 * 7
    int i;
  y$ p$ ]  Q/ o+ [2 Y+ U; H- i    //计数清0
    for ( i = 0; i < 35; i++ )
  Z! A, H/ F" Z) T        a = 0;
    //开始筛选
1 ^- f  g5 |+ G& z    for ( i = 3; i < 35; i += 5 )
        a ++;
, L  V2 N' ?3 u0 n2 ]1 F5 b    for ( i = 2; i < 35; i += 7 )
        a ++;

3 O- F+ V, A, f# w+ p    for ( i = 0; i < 35; i++ )
  [8 R1 m: H8 _0 z0 d        if ( a == 3 )
  w+ e& Y6 |, |+ v0 M        {
0 y( e  j. p: G; b1 ^& [            cout << i << endl;
5 k; H6 m# _  [) s5 B7 F            return;
        }
    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
/ O7 H5 P2 l1 f- {! j}
7 \1 \. S$ S9 t, A3 M+ O+ D

: e0 {8 W/ a% C4 B7 d) Q总结：
( p: q. K! V" g7 p9 B    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
) I4 _( d* `' A2 d8 w  W/ K1 y
for ( int i = 0; i< n; i++ )
2 d7 Y% n& `2 G: O2 ?/ E{
: m( X) F) b4 q1 n$ W' \  T0 @    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
% w$ ^& _" k1 t" @/ d( N6 m}
/ w; z' x3 `3 X4 M2 c    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
- `7 m' d0 Z/ n" [  ]9 c
    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的