标题: 算法入门系列之二 -- 筛选法 [打印本页] 作者: matrix_spaceman 时间: 2004-6-8 16:42 标题: 算法入门系列之二 -- 筛选法 所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。/ r" c2 U( q" p- J: U
+ n {8 |' g7 W" N
1: 求1-100之间的质数 - Y0 ?: I( N l6 H7 a$ K1 z, I 7 b) \3 [4 u4 z m! m( M 原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数. ) K" G7 l3 N9 p/ I& G+ g; C& ~6 s+ o; {* r
void fun1()( Y0 P- u% T3 W" T# B' l; I
{ : J! ]: \1 I- i" y% _% w6 U- I$ H1 h int i, j;4 V3 L. l. Z. t8 Q+ n D- p
bool flag[100];% U8 X; J2 O) x8 D
$ y; w( q/ U' U* N
for ( i = 2; i < 100; i++ )3 k0 `5 i/ J6 [
flag = true; ; t2 k& m/ T: u. x$ o/ b1 R5 s( n3 w4 w, o
//下面开始划掉合数 , }" j- d7 G; @1 n. B2 h0 w8 t for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根 " s% j9 U- `0 }. ^; q8 w& |( b( r {. S) U: v1 J/ w Q! F2 i1 E
if ( flag == false )$ Q( A1 ^% T# S9 v! p! B; y+ Y
continue; //既然i已经是合数，它的倍数应该已经被划掉 & S. T9 K/ m/ Q0 p4 x for ( j = 2; j * i < 100; j++ )//划掉i*j: B8 P7 H$ X' J/ y. T" U6 |$ X: |
flag[i*j] = false; . Q* o; Y3 b6 I' p9 i4 P9 v }2 \0 b g$ W! c$ c
) ]0 N4 S0 b/ `4 l
//输出结果 6 c6 A3 Z$ B# Q8 _ for ( i = 2; i < 100; i++ )3 O% x) [8 z9 Q
if ( flag ) 4 L: H/ Z- G2 c7 t- O3 B9 D cout << i << ' '; r" k3 r1 f: R, ?" |4 r" P
} ( Z G% c( J# ?$ H" h* M0 L7 r3 C6 w# h6 d
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？- _- K; W9 c! I- x5 u
Q( h- H. ]+ i 这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。6 F% [' x5 I: I. q
& `3 S( Y2 E, M. [" g; x2 _& @
另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。8 Y+ w9 q* M. Q9 }3 o/ E
# j& E7 i* q; _7 Cvoid fun2()) Y* t+ I% z/ o- v4 Q D
{ ; i9 A' u, m% m6 B- n: u' h9 \ bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉2 j) u$ k w/ u4 }8 y4 s6 e4 T
3 H; i6 ]" W* z3 O. V( W5 ^ b for ( int i=0; i< 30; i++ )! n& r9 m: C: |2 N3 G
flag = true;: n4 F8 ]2 W3 _0 @0 s. t) b w
# B# `( \9 O1 e& _5 Y) \ int n = 30;//还剩几个人 a2 Y) U8 ~2 \: m5 _' R5 M int cnt;6 k8 R7 q ` |
int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便 $ b% y* ?' B- I. }2 ~+ V8 J while ( n > 0 )! t( i, P, N3 o2 n* w+ ]* h
{! a: B4 }2 L) {
cnt = 0;. ~+ V: W8 `: s2 r/ D
while ( cnt < 5 ), J: _, m3 l. O- E) h
{ / C7 X& ?) _: p) X7 M( g if ( ++pos == 30 ) * x, v; t- h. v d- m pos = 0; - l% |4 ^1 i) ^ if ( flag[pos] )//此人还没被毙掉 5 F! R4 ?3 o) a1 [2 W/ U' ]4 B cnt ++; 9 i ^' \( k1 H. a4 R+ ` z }* ^6 ~" Q/ \3 X# U* i
//退出时cnt == 5，pos指向报5的人; {7 o$ ^: O- [
flag[pos] = false;//毙掉6 m, N2 Y7 P! S" f: U9 w" l
n --;//剩余人数减1 G) I( D+ v& L6 c }1 X9 h; Z( c( L4 @2 M8 f" s
//最后一个被毙的就是幸存者 9 `! k( T, [1 B9 | //之所以加1是因为程序中从0开始计数，输出却以1开始计数' K- H2 f, @7 ?8 T
cout << pos + 1 << ' '; - K( |: E9 K- o: {( A} ; N% Q7 |" ^+ j7 [3 p3 q3 `4 I4 h% n% e1 F
3: 一个数被5除余3，被7除余2，求此数最小为几。 ( ^# ~" h2 s; c" ~' A M2 A+ Q4 }/ i 筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。/ X: @0 Y! Y+ F# m" o& s* [
首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。; w, D$ I+ E$ q" y0 M
在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。2 d! |% Z4 }0 B: ^. [- c w, X
7 r' Z4 L* D9 H" D5 A
void fun3() * D7 v' F9 @, f6 O4 q; s+ A/ e, c{ 5 j4 P/ {% e) z; W5 F; p! ?% h int a[105];//105 = 5 * 7, Y+ L" c+ v0 B% l- V
int i; 4 W8 Z f! S" `1 N3 S' a l //计数清0 W ]. C# q {* I$ m% m) m' O1 F0 `
for ( i = 0; i < 35; i++ )1 |: V% U5 p: q- f( ]
a = 0; $ l! v9 T# D" y* e6 u' g& n //开始筛选 ; S* L3 ?! g5 I for ( i = 3; i < 35; i += 5 ) 8 L4 ]7 h3 |" K6 O$ b0 Y: j a ++;; m- q! v. u# P* v' v
for ( i = 2; i < 35; i += 7 ) * j# ]/ U4 C! t' {) \ a ++;9 W/ Q% M: E. i4 G0 m. T
/ w( x6 f1 W* E( {" I
for ( i = 0; i < 35; i++ )' D2 T' B0 j; C6 _: i
if ( a == 3 )0 b4 i" P7 F D; h) C: Y4 Y @% R
{6 ~: C7 }+ s4 {+ u
cout << i << endl; * @7 A* |3 X( P' a o4 D3 R8 | return; 3 T/ T) C5 a% {. p. D- V" A* Q+ m; O }# t! x3 U, C4 f# V
//如果执行到这里说明无解 ' r- s) k0 A5 h1 h0 _/ q9 s cout << "No Answer!" << endl; . v' [+ D5 K( l$ F5 n. u) }}% V0 s: R0 X7 E5 C
; m, h" y \$ T3 u6 l9 C6 U+ {4 n! V7 \1 h4 U4 t' c8 j' N( i
总结： 4 W: L0 M( {( Z7 h0 }+ N0 n 筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是： $ ^2 J% I6 Y* j, X8 M, c& S9 C V& l* G0 |
for ( int i = 0; i< n; i++ ) / D, t# @5 n6 w9 O{ / K1 v. G4 x/ i# R9 o if ( i % 5 == 3 && i % 7 == 2 && ... )" s3 a5 D1 ` ^4 M! Y5 g/ q
cout << i;4 Q/ d0 n& ^0 d0 t8 I
} / S( Q" R/ \2 D: b9 t0 o 但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。3 ]' k- u& Z" c. m
6 {7 {; ]' f# y; t7 E" d# n 总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。6 H7 }+ Q( @+ J+ f8 s4 Y( K' j1 n