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

matrix_spaceman

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

1: 求1-100之间的质数

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

6 ^2 r( R- T; w& |1 T" ^void fun1()
  b% [! b5 g% F$ ~0 [. u/ m; m4 n{
, n/ A: Q  ?$ n0 Z0 E) x6 H0 [/ H    int i, j;
& x* w9 F5 w4 f0 `2 ~    bool flag[100];

    for ( i = 2; i < 100; i++ )
/ Z" Z. P7 W* p" Q        flag = true;

& g/ h9 W+ [, @# {# O2 u    //下面开始划掉合数
+ M  _' |/ @+ }# T7 `5 W9 S    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
    {
1 y: r3 W0 J2 ^/ l, B        if ( flag == false )
( Q* `; ~% }  M& F            continue; //既然i已经是合数，它的倍数应该已经被划掉
4 ?1 N; l( l0 S, l        for ( j = 2; j * i < 100; j++ )//划掉i*j
) v5 C# Z: p# i0 n            flag[i*j] = false;
    }
% \7 w# @) h5 S% V0 ~
    //输出结果
    for ( i = 2; i < 100; i++ )
" U0 i( P# L2 t- c% a8 {% w+ f        if ( flag )
7 C. y* h( i; {  g3 m/ _            cout << i << ' ';
+ P1 ~( [8 c4 O- J9 T}
2 \) ]) M6 w/ O, @3 J
( \; u' N" y" j" r+ h2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
9 u# T4 j4 [* }* Z  v( N4 Y: f2 k
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

* @+ i( V. y% A+ {& V' ?$ K, N    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

void fun2()
{
+ N3 o0 P; I4 S# E    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
0 i2 l5 M9 l2 C. Y  |( E
    for ( int i=0; i< 30; i++ )
  T- U# L& |2 L- P, n8 |" c        flag = true;

    int n = 30;//还剩几个人
    int cnt;
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
- K2 _9 h9 n4 b9 m+ D    while ( n > 0 )
% D+ V1 v& q) g    {
6 r4 K6 d6 B; }        cnt = 0;
: r6 y  U% C# j0 R0 }( i        while ( cnt < 5 )
        {
            if ( ++pos == 30 )
- Z3 B- k3 n, F" f' B2 t+ J* Z' |                pos = 0;
3 n( Q. Y; O+ E            if ( flag[pos] )//此人还没被毙掉
9 R; b+ |3 z1 \7 c7 h                cnt ++;
        }
' l0 q  ^6 l* U# I0 y8 P5 f- ?9 o        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
        n --;//剩余人数减1
' d9 ]3 q" P" e' E. Q9 l8 k    }
/ g, f% c1 S, P6 C. x    //最后一个被毙的就是幸存者
/ r6 g4 K: s) o( {. z& O    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
5 e. c% ]# o' d2 ~- ?3 N    cout << pos + 1 << ' ';
$ ^5 U. v" j# e' i" z9 s* L8 e}

" V" y/ j4 Q3 Q" [' Y3: 一个数被5除余3，被7除余2，求此数最小为几。
) i* n. m- a2 H; S, A
3 z: n' D# G5 [# ?) A    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
6 T, [! U' q- v$ Z) J# F7 w3 W
void fun3()
{
    int a[105];//105 = 5 * 7
    int i;
    //计数清0
    for ( i = 0; i < 35; i++ )
. G; n9 Y) h' v        a = 0;
2 X: O) g& f: y% B; l    //开始筛选
/ [3 w. l* E8 [3 B& S9 ^    for ( i = 3; i < 35; i += 5 )
& v  B& J+ [) f" P- R        a ++;
    for ( i = 2; i < 35; i += 7 )
        a ++;

    for ( i = 0; i < 35; i++ )
        if ( a == 3 )
        {
            cout << i << endl;
/ j6 _1 \, a, A5 w; A            return;
        }
) G5 G. W0 N$ u5 c  V5 V    //如果执行到这里说明无解
& B( e$ p1 R: Z+ Q" o! l    cout << "No Answer!" << endl;
+ N+ ]# M6 a, j9 w' K}

# `" X- M4 C, {# t( E: w! l7 E6 ~
, x% X' ?; C5 i: K总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

, t1 D0 E1 o/ X, N+ _for ( int i = 0; i< n; i++ )
{
+ d8 |4 n5 r* U1 c6 ^: p* h1 @% H    if ( i % 5 == 3 && i % 7 == 2 && ... )
        cout << i;
0 L8 p! o7 h0 @' L}
9 ~/ v) ^3 G5 x0 J( D0 K" x4 Y. X9 v    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
( x, L% E! ^8 Z. a$ V4 w2 z6 Z
) K4 p; a+ E: g& n7 y1 j2 s    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
' m5 g5 n+ m' |% O
# A+ B9 p3 A4 u6 {' g/ ^    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的