数学建模社区-数学中国

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

作者: matrix_spaceman    时间: 2004-6-8 16:42
标题: 算法入门系列之二 -- 筛选法
所谓筛选法就是从全集中将不合格的项全部删去,剩下的就是答案。* ~3 ~9 k# |# J: z- c

: E6 m% J! x! C) Y, Z$ M1: 求1-100之间的质数8 s9 s- v$ d7 u
- i8 y! H& x5 y1 Q2 E7 a
    原理:先将2的倍数全部划掉,再将3的倍数全部划掉……直到将10的倍数全部划掉(10^2 = 100 )。剩下的就是质数./ w0 }+ q9 U5 P: d

# n+ b7 S3 Q, X8 e. ~2 s1 q' ivoid fun1()) |' g" g. T6 w; y9 ~
{/ u" T5 w3 x  M; K3 H4 y
    int i, j;
) J' `. |- ~3 d  a2 _! ^    bool flag[100];+ _/ H9 \& V) N3 h% o1 u

& {) i4 ^; ~% g( X' a    for ( i = 2; i < 100; i++ )
6 i# O& {$ T; \" _( s        flag = true;
3 @+ I8 {8 l7 |6 J; x3 H% g; p
7 x+ z! O9 K1 v4 K/ C) _8 z    //下面开始划掉合数2 p1 r4 g8 \2 r/ l( W5 L
    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根; d9 z7 i7 ?- N! ~, G
    {9 f; v( W, s/ m5 z) V
        if ( flag == false )
3 o% G, j" H1 a' M$ l; g# j: ?            continue; //既然i已经是合数,它的倍数应该已经被划掉
# Q4 f, C5 N; q$ Z        for ( j = 2; j * i < 100; j++ )//划掉i*j- A% z( C$ w7 f
            flag[i*j] = false;6 f7 {& u. V. L, U
    }
2 d: }" `% c6 }) b) n
' E( Y' Y, Q5 j# z5 f& {    //输出结果
8 r' b9 ~. d2 Q1 M; D" p( e' c    for ( i = 2; i < 100; i++ )& G3 A! ?. s( u# p  t' N* f3 H. @
        if ( flag )
9 R2 Z& Z; B2 Q' s            cout << i << ' ';! L3 U, s$ h. H
}
" f" V7 D2 I5 H+ f
0 r/ u8 c+ w- C- l: Y2: 30个人站成一圈,从第一个人开始报数,凡报到5的拉出去毙了,剩下的人接着从1开始报,直到只剩一人放掉。想活命该站哪?
" o! p6 W6 A' |/ H# R
% J7 ~% Y; n. v0 y    这是个经典问题,解法就是模拟整个过程,有点类似于循环队列。+ ]0 Q# c' J+ Y9 B2 C: F

5 O0 J- q  i2 e* H    另外,为了程序上处理方便,可以假定所有的人都拉去毙了,然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候,对问题的问法稍作变动,或者将初始值、加减变量的位置稍作调整,用程序处理起来会方便很多。0 F6 W- N2 j6 _; P: S, l. K
; u6 `- f2 t* Y* |% ?$ u% {, M
void fun2()
1 w0 b, r9 l) V! L* `{
0 a% M; _. X' [0 G* B    bool flag[30];//标记第i个人的状态,false已被毙掉,true还没被毙掉! K7 M: \( w8 x7 K) ~# C+ M# W6 {  H

' a4 p2 t5 f4 C1 e( \0 T, z    for ( int i=0; i< 30; i++ )
8 p; k9 h8 K4 X' I3 N9 i        flag = true;
" I4 q' f# l' ^# K# U7 l, ?+ i2 v3 ]) ~% ]5 O7 Z5 g
    int n = 30;//还剩几个人% G' M, w8 L" I& ~% x6 S4 H' ?
    int cnt;
* h2 g- d" C* K0 Q9 V' b3 M: c6 L    int pos = -1;//初始值不一定从0开始,设为-1处理起来较方便+ j" A# ~% ]& n8 g
    while ( n > 0 )
. U$ g  C/ v: L" C    {
) w; A5 Q" l! k" Z( f        cnt = 0;
5 j7 t- D! x3 L* A        while ( cnt < 5 )
( i; a" p" n9 `' m% D        {4 _) {8 x- G& G5 Q
            if ( ++pos == 30 )4 \" P2 x- F: C3 a7 w) M- s
                pos = 0;9 y% ~' f3 u6 M5 F
            if ( flag[pos] )//此人还没被毙掉
$ ]7 ~% K- S% W1 y                cnt ++;
: T9 _, \" i1 w* s        }
; j5 I2 C) f: m        //退出时cnt == 5,pos指向报5的人) Q0 G( R( L! x
        flag[pos] = false;//毙掉* X4 g% q# w3 @+ a
        n --;//剩余人数减1
, q  Z1 v# ]. _    }
9 D6 y# A2 v2 n% O! v$ N    //最后一个被毙的就是幸存者' z+ L$ F* J+ u- Z; c; P1 O5 j0 h) ^
    //之所以加1是因为程序中从0开始计数,输出却以1开始计数+ N: r. [, O7 ?$ Y( Q
    cout << pos + 1 << ' ';
3 ~, H' J' N7 T: [1 k}2 Z) ~1 j( o& J" w' ^$ y; ]. |

5 w$ Q2 K" ^* v1 K7 `! B3: 一个数被5除余3,被7除余2,求此数最小为几。
! ^: E- b6 A1 L2 z# d
5 H3 r; U# n; f' U3 P, _' W! S    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选,这个问题就是一例。
, f1 Y: O4 w1 C- c% d; t/ h6 O  d    首先,如果问题有解,则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
$ y5 z+ v) _4 a; q# T    在程序处理上,如果一个数满足一个条件,就将计数值加1,最后计数值为3的即为所求。# Y' g; |& s6 a; M: Z/ `
% d/ m( ~% f( L# g. k3 z6 Y) g
void fun3()
! V5 r4 j( L1 P5 Q$ _) s, W0 ]{
% ~: P- o3 a# U+ I2 \    int a[105];//105 = 5 * 7' d! ~: Q7 E! t; |* i
    int i;0 d8 o1 k: i/ h) q% Z( z# p
    //计数清0
( n# p- Y  j; b6 I0 |; O8 t    for ( i = 0; i < 35; i++ )
5 [& W" h9 V- j4 A& a& Z' @- m        a = 0;
- C: X/ c% |: T# z3 B7 g$ [    //开始筛选5 K! ^; m- B! L  B. ~0 e
    for ( i = 3; i < 35; i += 5 ): Q5 h- w9 {2 u# A
        a ++;
. i7 |, t& u3 C- R    for ( i = 2; i < 35; i += 7 )
; u8 S' H2 `  n* |- s9 R  @        a ++;
* q0 |' h' W7 C& ?" [
* b0 W; \7 Z3 ?' H" w/ h    for ( i = 0; i < 35; i++ )
+ V5 w" _5 m3 e        if ( a == 3 )
' k+ P0 ]1 M2 z" M4 r4 l        {
8 G, k: N( X( p) d9 R            cout << i << endl;
$ m, S% s3 b- b1 b! q6 ?% f% d* j            return;& N* w7 U; y0 T3 p/ ~3 c
        }8 c. I( @0 E& a& Q& e( k
    //如果执行到这里说明无解
/ z/ q  T' s: G. ~) Q( P3 }    cout << "No Answer!" << endl;
- V0 Q7 a/ F$ M& V* P: t" t) J}7 W5 ?, P2 K* [3 T
( v3 K! r. ~& c% m0 g) U8 y, ?
; @( p! t/ {5 U' ]' c. U
总结:
  r- y/ }! _: y$ J    筛选法的时间效率较高,但需要一个辅助数组,这就意味着对规模很大的问题不适用。例如第3个问题,条件多1个,需要的空间就翻几倍。解决的办法是:* B3 x$ w+ t' p$ q: {9 i

7 t4 `: ?) B- i0 |9 i" Qfor ( int i = 0; i< n; i++ )4 ^9 v6 X- Z) b3 ]; A2 Z3 G+ k
{- Z6 ~  E7 y, l
    if ( i % 5 == 3 && i % 7 == 2 && ... )
5 F/ R) L9 E+ r4 X5 k( ^  k# \        cout << i;
* j5 i* U( c. \8 b, T1 Z  m8 G, [; p}5 x  I2 |- W5 O/ Y# {! H- A
    但相应的,这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。' d6 o8 W2 f0 U

" D. h+ s+ D; @) W    总体来讲,对于可以条件判断较复杂,且根据前一个(不)符合条件的情况较简单的推出下一个(不)符合条件的情况,(不)符合条件的情况分布较稀疏的问题,用筛选法速度较快。如果第3题中加一个条件被2除余1,用筛选法就不太合算了。4 B1 D: }( {# f, R/ N

; k, j2 ]* a. Y% P7 i( n9 ~! y, ?    最后说明一下,此次给出的程序目的在于说明方法,在效率并不是最高的




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