数学建模社区-数学中国

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

作者: 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之间的质数  R3 d/ o/ s2 _. O' O

2 ]# Q4 S/ s4 H" }+ G; k    原理:先将2的倍数全部划掉,再将3的倍数全部划掉……直到将10的倍数全部划掉(10^2 = 100 )。剩下的就是质数.5 H' o  h' p1 m  ^0 O0 @
; T  x* v; u, K! n2 ^
void fun1()
! T6 ~& s, K1 u9 y/ C{
$ L% E5 X7 V* K1 m* x# j. P: o    int i, j;6 H; z6 G' O: U8 l: ^( M, X
    bool flag[100];5 m6 L) a2 g; I  }

# 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    //下面开始划掉合数" c, h+ R- u2 P3 C
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
* [8 r" |% p: N7 K    {
* ?, ~% {9 m7 W$ |; f        if ( flag == false )- M5 d! }! z9 \
            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;  V6 q) u: d1 K, z% p& A; C
    }
# g" ^  S; f7 H& N4 N5 l0 Q$ R9 l+ f
    //输出结果
: _2 u! P5 \( R: ^    for ( i = 2; i < 100; i++ )& ^. A+ y+ T) B$ ?  W
        if ( flag )# Y) ?3 j& D' j% \
            cout << i << ' ';* t8 S2 x0 }+ ?$ l4 [5 q
}# E. Z" q3 w% C" h' p: Y
4 F5 P( I8 i3 l( m5 Z% U
2: 30个人站成一圈,从第一个人开始报数,凡报到5的拉出去毙了,剩下的人接着从1开始报,直到只剩一人放掉。想活命该站哪?5 w. @5 w+ A; {' T9 r4 i* R: k  C
2 Q  K* T/ l8 E" {6 v/ g* Z3 d
    这是个经典问题,解法就是模拟整个过程,有点类似于循环队列。! f& f; z8 i) z% Y# B
/ ^. b. a. M: F2 w# s
    另外,为了程序上处理方便,可以假定所有的人都拉去毙了,然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候,对问题的问法稍作变动,或者将初始值、加减变量的位置稍作调整,用程序处理起来会方便很多。5 |/ w2 ?' k4 T- u* s" t4 ~
5 y. K7 y0 `4 K9 Q1 ?: G) N3 w
void fun2()
) \. ^# e/ _& A, W# E( P# M{
0 f8 ^$ y: D0 ?: o/ o    bool flag[30];//标记第i个人的状态,false已被毙掉,true还没被毙掉2 O/ g$ T4 \) a  M) G! x8 O
6 [. M" i! U. J8 l  C, V0 w
    for ( int i=0; i< 30; i++ )
. S5 M0 U8 z) m6 y        flag = true;# M- a7 C. l( Z

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处理起来较方便4 _& g) }4 a) T* F  s- a
    while ( n > 0 )0 o" H  q0 p& S
    {; m3 r3 m: a' e6 r5 s
        cnt = 0;) n. @1 [4 h2 O
        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;( ]/ a: Y( g' g! d: w
            if ( flag[pos] )//此人还没被毙掉
1 a) M, O. b& i# v                cnt ++;1 _1 r( z) T# h8 X/ R
        }: _9 ]* X& r! `6 X8 u4 D, W5 r* B
        //退出时cnt == 5,pos指向报5的人$ E2 @- F  ^4 }' Y8 S
        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    //最后一个被毙的就是幸存者2 y0 d7 P/ K' H$ [
    //之所以加1是因为程序中从0开始计数,输出却以1开始计数' Z7 V  e! u0 w  u
    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,求此数最小为几。* {, a) B$ r4 ^7 s% Y: t: v' M" ]
! R+ m! T1 w% ?! a
    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选,这个问题就是一例。: C9 G# a. i. F" A# B% q
    首先,如果问题有解,则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
, a" ~0 c* @8 \6 z( g6 Z, @) E4 o    在程序处理上,如果一个数满足一个条件,就将计数值加1,最后计数值为3的即为所求。; G  |1 U2 x+ a5 O
6 i( [% v  r* e. R( C4 k$ ~
void fun3()
9 ]4 U% N- A% z8 W2 D{" h1 Y6 S. g4 Y# j5 w/ x+ N5 J: |3 w
    int a[105];//105 = 5 * 7
( t/ _7 X# ?7 K. R0 Z    int i;( e) C1 q$ U7 J1 ^( J' @; x
    //计数清05 @: H9 V  X9 Q8 S: y4 z
    for ( i = 0; i < 35; i++ )
6 Z4 {* A6 A4 ]1 n        a = 0;: d" C/ O* T0 I8 W' ~
    //开始筛选
. 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 )& E7 Y- J- _9 S/ h' p; s
        a ++;
& c5 ^' z/ g3 C. o. C% |$ n2 j7 I- h% \+ H# x; F( b2 \+ V# a8 x
    for ( i = 0; i < 35; i++ )
+ M9 y: h  U- G0 ?9 K! K        if ( a == 3 )7 k! x$ Y( c, a& J
        {6 r" Y& o/ }" Y$ [; L
            cout << i << endl;
" W& L9 O2 B  T/ h3 J) x$ |            return;# o" ~9 g+ i8 [2 B% T$ ]: s
        }
$ n% {' r5 b% M& x5 E' q& p    //如果执行到这里说明无解/ t6 Y( X4 A# S9 S# ]& M
    cout << "No Answer!" << endl;: o$ i* v6 h- o: B8 V7 T, B! f6 V
}
% 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总结:/ a4 T6 r# F1 v- V
    筛选法的时间效率较高,但需要一个辅助数组,这就意味着对规模很大的问题不适用。例如第3个问题,条件多1个,需要的空间就翻几倍。解决的办法是:- P& N/ b% ?* r& D  v7 D- @

/ 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}7 x9 ?# x0 u/ w" D8 n
    但相应的,这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
$ @/ 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 ]& u0 m! A* v% X6 g5 Y: B
    最后说明一下,此次给出的程序目的在于说明方法,在效率并不是最高的




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5