数学建模社区-数学中国

标题: 算法入门系列之二 -- 筛选法 [打印本页]
作者: matrix_spaceman    时间: 2004-6-8 16:42
标题: 算法入门系列之二 -- 筛选法
所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。* W( P" {) B2 m% s

5 S7 a8 [- I/ u1: 求1-100之间的质数4 Q3 w0 E# ~4 B

% R* L: A) k" C' l8 \    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.# x; a: I: Q+ [1 k! t% F9 n) A4 ~& ^
0 F; l3 X0 }9 Y4 j
void fun1()# G0 A# g* u/ U" m& b
{
& y: V6 `6 L+ X9 y) q! Y    int i, j;
/ O! I+ I5 t+ G# @7 z# ~: i    bool flag[100];
, u& _; r' }8 z$ b
; E. g% G6 n! ]) [: E8 ^    for ( i = 2; i < 100; i++ )3 X: n. s" s" C3 N+ G  `6 b
        flag = true;3 T2 ?6 Q! N! `% ?5 f0 k' f

/ ?& Y1 N/ [' g4 c$ Z    //下面开始划掉合数
7 @( p5 q- ?8 M9 |# a' L, Z( y    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
& w, h/ ~/ Z8 y; F    {
9 a2 Y& o( l- j/ A- L& Z: S' I7 e! C        if ( flag == false )% i* s* ]- W) Z4 N
            continue; //既然i已经是合数，它的倍数应该已经被划掉+ z( H" ~) T( m+ M% a- P  i
        for ( j = 2; j * i < 100; j++ )//划掉i*j- U7 |4 y9 V! i, {1 C# d; `% @
            flag[i*j] = false;
1 }- F+ t& V3 P& q' G+ W) @3 V* D2 n    }
/ A5 |$ B$ R3 T: k" X* `% ]1 S6 d8 O
    //输出结果
9 j/ A2 [* X" m    for ( i = 2; i < 100; i++ )
- E% Q" }; A7 X8 i0 ~( X. n0 a        if ( flag )9 Y# I4 E; m0 x/ p
            cout << i << ' ';
; \% @( o- Y. L, U* w5 W, X}
  ]; J% S; w7 c( @( u( s* `3 a$ c! o5 D, `3 K7 B2 Q3 q' U
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？/ d5 ?! Z0 L) _5 s, }7 P
- H% z8 g/ T& q
    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。  B! A( f" u7 }- u9 j1 v

* K2 t5 V  C& @, t    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。  E" W7 B4 _9 k& q+ ~% C& j

7 u9 y; i9 Z. A" p# f4 d# A  Pvoid fun2()4 `6 y8 g0 I9 d6 v9 H, k
{9 {6 h3 A; r. D0 c/ x
    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉# @& n, I8 f4 k2 C( Q9 L; ]7 k7 N
3 A  @/ y8 t0 n0 n
    for ( int i=0; i< 30; i++ )! x- P+ q& B7 t
        flag = true;% _% a" O/ l8 g3 M5 j$ g+ a

3 H' ?0 |% U+ L' S7 [    int n = 30;//还剩几个人
0 P* ~  k3 y: X/ [9 s8 z. ~& f  ]    int cnt;3 y7 H" E/ h0 P9 `, m
    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便. p8 w( m% e1 O9 s: s
    while ( n > 0 )$ x1 E: c7 b& K. j5 k" y
    {
8 Q8 N4 Z1 R  `: w8 D+ @$ r        cnt = 0;$ u% P7 ]8 I9 R- p0 m( w4 w" k0 H
        while ( cnt < 5 )
& u, [( H" |$ }6 t1 {% x' @        {# t5 k7 S. E# V  L- m: g6 Y  u
            if ( ++pos == 30 )
. F; b4 J$ L; L) K+ K                pos = 0;
5 [) x+ L: B2 n: s" F+ s" A+ x, ^* o            if ( flag[pos] )//此人还没被毙掉
! g; F% y8 b* C! F* F3 {                cnt ++;- x, E' s3 `+ c& K) W1 l
        }, h: ?+ M9 N* z4 h. v
        //退出时cnt == 5，pos指向报5的人5 o4 R' z) j( [# L
        flag[pos] = false;//毙掉
, c& _; [( Z5 Z2 K+ S        n --;//剩余人数减1/ U1 L! A$ N, w
    }
# t4 i% Z) |, M) _# h6 F    //最后一个被毙的就是幸存者
9 p# ]) D' q( D5 P9 ^    //之所以加1是因为程序中从0开始计数，输出却以1开始计数5 v" `0 A. y# u+ c# m+ V
    cout << pos + 1 << ' ';2 d! q  N. p- i0 t5 }" I) A
}
8 s! X; \; S- a3 `. _
: [. E% B9 K# I9 C; q2 Z$ ~; O2 \3: 一个数被5除余3，被7除余2，求此数最小为几。+ v& F" r$ s! t

5 c# @/ `- R% i: K    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。) {, {, @! x6 h4 @
    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。# d9 f, Q/ T7 n. j
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
! n: p, y) W3 d2 W/ ]5 O+ {4 |! q2 K/ ^1 C
void fun3()! F5 N, G7 Y0 R1 T
{0 o4 @0 ?: H8 m& o. [" }$ ]
    int a[105];//105 = 5 * 7
0 j  z# ?( A" t    int i;# K! R: o/ G# d  c' J
    //计数清0- y3 ?: d* y  b6 q2 {
    for ( i = 0; i < 35; i++ )
( Z. E" V% \) @* m3 E5 g* Q- ?; O        a = 0;
6 }7 j/ i9 }- w' d/ r    //开始筛选# G5 Z& M/ U9 I7 W6 U+ j5 M
    for ( i = 3; i < 35; i += 5 )9 i/ [/ {" C: o
        a ++;
4 S8 G. Q# c0 B) ?" v0 j# q- K    for ( i = 2; i < 35; i += 7 )# E3 s/ ~* F( v, Y
        a ++;
& `+ j: A& H! |1 u$ S; k3 J4 B, A& k) b
    for ( i = 0; i < 35; i++ )* {, v4 @7 @. Y+ x* ^
        if ( a == 3 )2 K4 o7 x8 J( f4 O& C
        {
1 m% N, Q) {/ o5 L6 W2 c; X            cout << i << endl;% _9 n1 J- o) @) t
            return;
  D8 M8 d( f# W5 f: v% l        }& e/ Y- b2 o) k- e8 c( ?) i* ^
    //如果执行到这里说明无解
" B3 E+ l+ r! h) T0 Z    cout << "No Answer!" << endl;1 @2 t& d$ `7 m& {; M: ~) s% ~$ p
}1 X  V5 B% D1 K  q! ?
6 @0 C) ~4 s( k$ Q
) n" @% E2 \" M
总结：8 g2 I1 l" {- Z- {" T
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
* W0 k/ |  I% d- n$ u
! h: t: l! Y: h2 ~" Ufor ( int i = 0; i< n; i++ )' n3 J2 c8 ^7 ^2 o2 Y
{3 Q3 N9 W5 @" r8 {
    if ( i % 5 == 3 && i % 7 == 2 && ... )
  p% o, {' z. C6 k$ t        cout << i;& `, R0 p4 h+ p$ z- [+ D: r" L  w
}
2 {$ O+ x5 B4 X6 e" j: }5 z; p    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
* ~( W; E7 l- c; p# u$ E. Y) R& G' {5 w# a  j
    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
- e; A- T, [9 e+ x: {& p
  x: E2 I- E$ r1 g! i  @    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的



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