数学建模社区-数学中国

标题: 算法入门系列之二 -- 筛选法 [打印本页]

---

作者: matrix_spaceman    时间: 2004-6-8 16:42
标题: 算法入门系列之二 -- 筛选法
所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
  y; w) ~. v5 l# A; j+ @9 L
- v) J/ a  y9 i" V( b" z( k9 Q* c+ W) T1: 求1-100之间的质数

2 ]# Q4 S/ s4 H" }+ G; k    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

void fun1()
! T6 ~& s, K1 u9 y/ C{
$ L% E5 X7 V* K1 m* x# j. P: o    int i, j;
    bool flag[100];

# U0 _/ h* f( x2 b3 `; i0 J6 t( v    for ( i = 2; i < 100; i++ )
( o# I* r, R' B/ \        flag = true;
9 M; q1 u) L, Z; ~8 I2 }7 U! x' F
( H1 o8 v" A/ H% L4 _+ k9 o    //下面开始划掉合数
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
* [8 r" |% p: N7 K    {
* ?, ~% {9 m7 W$ |; f        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
8 {6 E' G3 t8 g( ?        for ( j = 2; j * i < 100; j++ )//划掉i*j
. R; s8 g1 i6 ?) l2 b            flag[i*j] = false;
    }
# g" ^  S; f7 H
    //输出结果
: _2 u! P5 \( R: ^    for ( i = 2; i < 100; i++ )
        if ( flag )
            cout << i << ' ';
}

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

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

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

void fun2()
) \. ^# e/ _& A, W# E( P# M{
0 f8 ^$ y: D0 ?: o/ o    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

    for ( int i=0; i< 30; i++ )
. S5 M0 U8 z) m6 y        flag = true;

9 ^$ Q# L+ ~! U2 V3 U) G    int n = 30;//还剩几个人
( R& {9 v- ~; n* o6 r) @    int cnt;
+ y" p. ~! `' g/ w4 p) v2 {    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
    {
        cnt = 0;
        while ( cnt < 5 )
* G9 o9 J; K8 f5 Z1 {7 g9 w( T        {
9 r4 X" u9 h3 P; [0 f* r            if ( ++pos == 30 )
( N0 ~9 E2 F  Q9 X                pos = 0;
            if ( flag[pos] )//此人还没被毙掉
1 a) M, O. b& i# v                cnt ++;
        }
        //退出时cnt == 5，pos指向报5的人
        flag[pos] = false;//毙掉
' ~. o6 z* F9 }0 z        n --;//剩余人数减1
% t. H1 O5 y% t8 E) @) o$ M/ W6 R    }
0 A0 h% {3 |; o# I5 F) S5 w    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
    cout << pos + 1 << ' ';
2 x7 Y/ Y* D6 L2 Q* b( I}
9 v4 ~# x3 O6 C' d
3 E% V# B! L, {8 I3: 一个数被5除余3，被7除余2，求此数最小为几。

    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
, a" ~0 c* @8 \6 z( g6 Z, @) E4 o    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
9 ]4 U% N- A% z8 W2 D{
    int a[105];//105 = 5 * 7
( t/ _7 X# ?7 K. R0 Z    int i;
    //计数清0
    for ( i = 0; i < 35; i++ )
6 Z4 {* A6 A4 ]1 n        a = 0;
    //开始筛选
. J6 P# S5 {# F/ M    for ( i = 3; i < 35; i += 5 )
. v  p, B0 V# V5 G$ f$ V        a ++;
! l9 G  C$ F& D) \4 d+ ?# P    for ( i = 2; i < 35; i += 7 )
        a ++;
& c5 ^' z/ g3 C. o. C% |$ n2 j7 I
    for ( i = 0; i < 35; i++ )
+ M9 y: h  U- G0 ?9 K! K        if ( a == 3 )
        {
            cout << i << endl;
" W& L9 O2 B  T/ h3 J) x$ |            return;
        }
$ n% {' r5 b% M& x5 E' q& p    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
}
% c/ z, p; u! T6 v- g
! j; B1 k6 b9 S4 t% O+ j; I
0 u9 ?$ _2 d" f& T2 |; w6 P9 l+ d& s总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：

/ G: g1 v$ l9 O- ?) z5 v- Vfor ( int i = 0; i< n; i++ )
) f: h1 c2 _9 ^{
  B6 u7 g, z: r9 R% ~. H    if ( i % 5 == 3 && i % 7 == 2 && ... )
2 f# M, O( e* e( C1 d7 }        cout << i;
# f& w7 J  e8 h}
    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
$ @/ J- r* \- ?2 l- C
  G, k' P, D0 x7 J4 l' v0 z& W    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
0 }% p6 p+ J+ b1 c! A2 ]
    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5