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

matrix_spaceman

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

2 b& {* H" }  l8 r4 G1: 求1-100之间的质数

- f: S2 t0 V6 @    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
- I7 |; u  u& s' P! }
  K$ K# |) S9 ovoid fun1()
{
    int i, j;
; P% J# S) I, N! P  \9 y( `    bool flag[100];
& u$ r5 z, z4 t" v9 E
    for ( i = 2; i < 100; i++ )
        flag = true;

    //下面开始划掉合数
* _5 S' r6 K( E- [1 [& M- j2 Z    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
8 O' Y# _! c* a9 R! @+ q7 b0 |    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
    }
( C& r. p# G$ l% m$ a8 y
# B2 g  u. N$ Q- B; [& T    //输出结果
    for ( i = 2; i < 100; i++ )
7 Q, u$ {- H# t5 T$ p  K) ^        if ( flag )
            cout << i << ' ';
}
7 }: S6 B  I  Z) P: j" W
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
! V9 ~) q! r( R. b& E# x
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
( r0 J% i5 s$ g# J* Z7 i- c$ ?
    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
' n* w! ]6 ?% j: D9 C. h  D  Q, [/ L
$ c* c- w5 b( g/ M8 gvoid fun2()
{
  Z4 g' S8 a5 j! j0 Z$ O& s+ W    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
; a) ?- N2 j  \' d6 {
7 x& r+ L8 }; e+ y# y6 W8 [8 j    for ( int i=0; i< 30; i++ )
" V# w; D  E0 L9 z$ `+ X; y        flag = true;
3 S- c+ A! g% T& z, H( k1 z" o
# ~- t! w* H7 I, `& W! {    int n = 30;//还剩几个人
! V, w# E* K9 C6 K% g3 ~/ k5 d; Y& w+ [    int cnt;
! U6 A  C: g, b    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
/ @7 o; B* C# o    while ( n > 0 )
0 Q  d$ D" S; V# ]! ~8 E    {
4 F+ S5 L. d0 _8 t4 G, E7 z. T0 q; Q. E        cnt = 0;
# ~6 }4 ?( v, H) a        while ( cnt < 5 )
        {
( f- e$ z5 Q% U! f            if ( ++pos == 30 )
                pos = 0;
" ^6 ?- C# p2 l  a4 n            if ( flag[pos] )//此人还没被毙掉
9 r2 ?$ a$ H# x- @8 h! I+ n1 A( @1 p                cnt ++;
        }
  }- w, M; h5 [1 j; m$ q" b/ e1 A        //退出时cnt == 5，pos指向报5的人
. t4 X4 J8 D% L- t) t& O- V* Z  E: t        flag[pos] = false;//毙掉
) g5 k3 c! \4 h        n --;//剩余人数减1
    }
    //最后一个被毙的就是幸存者
+ D- `# r" `% o    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
2 D% ~1 L. h  ]7 t5 m5 V}

. L, B! O% ^- Q7 S' A, K  w3: 一个数被5除余3，被7除余2，求此数最小为几。
: Z8 p9 u" o+ Q
5 B7 d0 b' |8 \    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
" z8 q2 t' r9 o0 {( s    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
{
6 J) |8 {, U; o8 o    int a[105];//105 = 5 * 7
6 B& a/ n) X- U1 C2 G& ]0 N    int i;
    //计数清0
# G4 q$ l& K" w1 f/ n; \  G    for ( i = 0; i < 35; i++ )
        a = 0;
    //开始筛选
- W9 j; O7 o5 p9 C" h8 J    for ( i = 3; i < 35; i += 5 )
: ^3 i% q) J  u( {4 A        a ++;
    for ( i = 2; i < 35; i += 7 )
        a ++;

    for ( i = 0; i < 35; i++ )
% U) [" G: e3 ]7 R( A* B: P$ R" B        if ( a == 3 )
  r3 x) h- N$ r8 ~& y  l. @        {
; g- n4 H4 D) z" e2 q) W( R/ g! c1 ~            cout << i << endl;
# u1 H: G8 O3 V5 R. _            return;
- h0 `8 s3 ~( M- U' l9 k        }
    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
. O; U, Z+ q, X& L# i/ P3 w}
' r7 g1 r  d& N9 U
) k7 I, N% L# N% P
1 @9 U7 r# ?- I/ S/ [总结：
6 o$ t, Z% h6 [+ m4 _    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

for ( int i = 0; i< n; i++ )
( _3 b5 v$ L. Y0 g/ e4 W{
% W- x: x$ [* I    if ( i % 5 == 3 && i % 7 == 2 && ... )
2 j+ H7 ?3 D/ _+ M, y. V3 M        cout << i;
}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。

    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。

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