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

matrix_spaceman

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

& v! ]" N1 c# Z9 ^1: 求1-100之间的质数

5 E, }7 @6 t* Q; D0 q    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
{
5 ~% \" M! Y% m$ T4 G    int i, j;
, K! ]; d3 H, I8 U# ?4 B    bool flag[100];
; S4 V( O7 |3 b& ^
7 K4 {& H# Z- A! M$ U5 \- l  C2 A, R    for ( i = 2; i < 100; i++ )
# f$ c- `: b8 X; p3 }! m( J) l        flag = true;

, |2 {) }0 |: t' {    //下面开始划掉合数
/ W+ _) i. w& h% P  S. E    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
+ _; P7 ~- a0 B8 g% @6 g# W    {
9 L* E* s% G, x: @        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
& _( u+ H9 `# x7 W! B1 j) m    }
1 c* d2 C* O3 l7 k
    //输出结果
    for ( i = 2; i < 100; i++ )
        if ( flag )
            cout << i << ' ';
}
* d* c3 _% R4 [4 E% _8 K! \5 A# C
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。

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

- K  g' x8 q0 {  p( K* cvoid fun2()
{
' M8 \6 L7 Z) x" |2 a    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉
( E/ y+ l% g6 K
; u( C: A5 l. ~4 J8 R    for ( int i=0; i< 30; i++ )
2 x7 @, x# D9 x- L2 o) P        flag = true;
7 Z/ }+ D+ e9 F( n0 w6 g
+ M% n: f. Y( p! B    int n = 30;//还剩几个人
' l1 h' k# Z6 J% P1 T' V    int cnt;
* w( Q( Y1 M" F+ ^/ a* S! P3 l    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
    {
        cnt = 0;
4 }2 X5 p. \' p) l9 A* k/ r4 z' w        while ( cnt < 5 )
; R& c0 w* D* @" T% i# @( S* E& O        {
            if ( ++pos == 30 )
% B: \7 ?  C! o- G2 ~/ W! \8 c                pos = 0;
5 B8 X9 O" K% t            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
" q/ S3 a8 q( n+ x8 {6 O        }
9 O9 C0 P3 O) h3 F) n& W+ F        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
        n --;//剩余人数减1
2 d9 b# q% d& X* _    }
$ A* E/ p! |0 R* N0 F. {; \    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
& U6 U- d# O' S4 L7 U7 B$ N    cout << pos + 1 << ' ';
& }3 C" b4 L( u/ S}
5 D6 V" p' t+ F' F1 G; i
1 x  Y$ P5 x% p; W0 @6 W7 C/ S8 _3: 一个数被5除余3，被7除余2，求此数最小为几。
  v( ~5 j6 y/ c( R( Z$ ]& C
    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
, i0 u8 m% d% d9 }/ i" p* Q( q    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
) H! H4 L! N4 g4 J" T    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

7 g7 `0 y7 c, c6 ?# P! _void fun3()
{
( @( U8 r+ c# i    int a[105];//105 = 5 * 7
    int i;
    //计数清0
1 m/ C+ E: A, N" l# V    for ( i = 0; i < 35; i++ )
        a = 0;
/ |2 S( T- V6 z( ~+ ~; g1 T/ @  T    //开始筛选
$ }' N4 Y- k. Q    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
        a ++;

8 P6 a8 C2 S& I! K    for ( i = 0; i < 35; i++ )
- r+ y' a2 }% O% v5 c1 W        if ( a == 3 )
/ n" `( Y% v7 y1 y        {
# [$ x* m4 h: `' [            cout << i << endl;
8 W* A0 S. B0 N- b, b            return;
% b0 k4 C5 ?8 ^) j        }
    //如果执行到这里说明无解
% t1 |4 X) r7 C. @  g    cout << "No Answer!" << endl;
}
1 J& B" g. h5 B8 p( a, E7 q" e

总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

# M8 L+ m; p/ \4 M, pfor ( int i = 0; i< n; i++ )
0 o* f* @: W2 `3 Y7 H: H{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
' b& |5 V! |$ k5 v        cout << i;
}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
2 U: `, o! e  X: P! G3 L
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
& D4 Y  h2 Y- B" y/ B
    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的