- 在线时间
- 0 小时
- 最后登录
- 2004-7-22
- 注册时间
- 2004-5-28
- 听众数
- 1
- 收听数
- 0
- 能力
- 0 分
- 体力
- 124 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 43
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 4
- 主题
- 7
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   40% 该用户从未签到
 |
所谓筛选法就是从全集中将不合格的项全部删去,剩下的就是答案。$ m0 V0 n" ?- V: N. H
' c+ l$ C1 {5 U* g/ ]$ B0 R" R1: 求1-100之间的质数; W' h4 p) ?8 u6 C4 b
+ D) K% J/ z7 }% G( k ]3 z. G
原理:先将2的倍数全部划掉,再将3的倍数全部划掉……直到将10的倍数全部划掉(10^2 = 100 )。剩下的就是质数.3 G# G7 t" y% C" I6 m( t! @! P+ w
2 a2 C$ E& r+ o3 x
void fun1()5 L! m- L' G: i( Y' M' O2 n! t
{
0 Y9 z( T4 q2 g: B+ a int i, j;# \1 p+ Y' b8 K8 W
bool flag[100];6 s6 @. | e- j4 j* P
) O) O! @* S' Z& G. {: o for ( i = 2; i < 100; i++ )
6 b/ W* x" N" P" N' P# H+ l flag = true;$ d& ?' p N' Z* y
4 m) [# M1 h* {5 W, r //下面开始划掉合数
- d, r9 _9 w/ m) n3 q* R5 R k for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根( X6 g; x- |* b2 @- l8 E
{8 q* I. w' y4 l/ c# }- t
if ( flag == false )/ u, F/ ?/ g/ w( W
continue; //既然i已经是合数,它的倍数应该已经被划掉. h" A; h8 S* J4 ~6 Q
for ( j = 2; j * i < 100; j++ )//划掉i*j
# ?* Q# l8 H, J# s( | flag[i*j] = false;- k0 e6 S: L8 `
}
0 a8 `# j7 }" p, ?
" B. G: e& F+ }9 N, V; _( F //输出结果
# ]# i6 E, x2 o( O( ?8 } for ( i = 2; i < 100; i++ )! d) p/ i+ c! ?6 _! z* }& z2 J0 d
if ( flag )
: r7 s' b" v+ a$ g! d+ @ cout << i << ' ';
0 m2 C& B! B1 p}
( I3 C9 V& s6 `& s8 `1 _# U' @9 i, K0 l. U
2: 30个人站成一圈,从第一个人开始报数,凡报到5的拉出去毙了,剩下的人接着从1开始报,直到只剩一人放掉。想活命该站哪?; l' [& T3 e3 ]! e, K6 s
" s1 R+ u* ~0 R4 U }2 d4 ~ 这是个经典问题,解法就是模拟整个过程,有点类似于循环队列。) B( _& w9 ~& @6 ^# V
: C7 q. B/ {8 k5 Z" I; |" b 另外,为了程序上处理方便,可以假定所有的人都拉去毙了,然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候,对问题的问法稍作变动,或者将初始值、加减变量的位置稍作调整,用程序处理起来会方便很多。7 h) e/ x& X$ u. U" H
2 `( l* V$ Q- y/ R# K7 q) q8 x2 f% wvoid fun2()0 }7 g+ r" a( W- e, }( v
{
9 ] \: I* H7 t; p. v7 q& w6 P. z bool flag[30];//标记第i个人的状态,false已被毙掉,true还没被毙掉" k9 h+ E# V: i1 R+ p' [& v
/ W2 W7 E+ N; z- K0 Y- R; g for ( int i=0; i< 30; i++ ), n4 {3 R- O+ }& W4 }" U
flag = true;
$ Y8 w# `, }( x2 o2 Z! a" Z0 u7 b9 v) W+ H/ L
int n = 30;//还剩几个人: l* k9 |, h& V9 Y0 z
int cnt;8 d; T+ q2 O4 x: ~: c/ Q! S
int pos = -1;//初始值不一定从0开始,设为-1处理起来较方便) S: b" a2 w) o) H- x8 o. W
while ( n > 0 )! g2 N3 X' g/ E
{
& N0 u6 v4 i" ~1 r cnt = 0;5 I& S. a5 p5 u5 h `/ }6 R: W
while ( cnt < 5 )2 v4 V' v, Q" e% c) s. m$ N9 J
{
e. w i! R& }& _ if ( ++pos == 30 )
/ W9 I0 _' I+ r0 p pos = 0;2 l4 x! h8 d- e" |# |
if ( flag[pos] )//此人还没被毙掉& }/ I6 B$ i1 x
cnt ++;' N6 c& q* k& h4 o6 [' w( ]
}
& M' v1 ]$ T6 F, c //退出时cnt == 5,pos指向报5的人
2 A5 I" E8 u, I; I flag[pos] = false;//毙掉
! U3 T; P- ~" j0 h/ d# l- Y n --;//剩余人数减1
5 c f* X" _0 v- Z }
& X5 Z6 I; G, P //最后一个被毙的就是幸存者
8 M8 b' h( W8 x* m6 h* e //之所以加1是因为程序中从0开始计数,输出却以1开始计数; Z# C3 }( W- Z$ a
cout << pos + 1 << ' ';
- c7 P) j# U3 f$ l}
; F9 I$ o* j1 g$ `4 A( p% R% e% f" P% _. p. k! j
3: 一个数被5除余3,被7除余2,求此数最小为几。" x& P9 h1 H8 F. s2 l
' k9 N2 G1 E. L8 a, @
筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选,这个问题就是一例。0 r% N( p l! Z9 D( f
首先,如果问题有解,则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
) N1 t+ s, x" ~: r' p0 H 在程序处理上,如果一个数满足一个条件,就将计数值加1,最后计数值为3的即为所求。 K* ^0 b5 c2 C! j6 h
& K; X: R; ^4 a
void fun3()
1 \* t! |7 x, b- ~9 r{* [: V! p; c, p8 g
int a[105];//105 = 5 * 7 L( T9 L% k/ g9 j- v
int i;
y$ p$ ] Q/ o+ [2 Y+ U; H- i //计数清0/ J' C. ^ t, u4 r; F7 d [
for ( i = 0; i < 35; i++ )
Z! A, H/ F" Z) T a = 0;2 M1 b( J7 |+ x! ?" {* ` Q
//开始筛选
1 ^- f g5 |+ G& z for ( i = 3; i < 35; i += 5 )6 h7 a$ g1 x, f& Z+ |
a ++;
, L V2 N' ?3 u0 n2 ]1 F5 b for ( i = 2; i < 35; i += 7 ). r6 e3 T2 c% G( X* F
a ++;' `* W1 ?2 Q" w. n
3 O- F+ V, A, f# w+ p for ( i = 0; i < 35; i++ )
[8 R1 m: H8 _0 z0 d if ( a == 3 )
w+ e& Y6 |, |+ v0 M {
0 y( e j. p: G; b1 ^& [ cout << i << endl;
5 k; H6 m# _ [) s5 B7 F return;3 z, \# L; B& @" u+ I- e( j: I- d
}" M& D9 q g5 h8 l; @+ e5 t3 [
//如果执行到这里说明无解2 ?; z: ^3 G& z. O
cout << "No Answer!" << endl;
/ O7 H5 P2 l1 f- {! j}
7 \1 \. S$ S9 t, A3 M+ O+ D/ J! D# q2 L8 ^( T5 D
: e0 {8 W/ a% C4 B7 d) Q总结:
( p: q. K! V" g7 p9 B 筛选法的时间效率较高,但需要一个辅助数组,这就意味着对规模很大的问题不适用。例如第3个问题,条件多1个,需要的空间就翻几倍。解决的办法是:
) I4 _( d* `' A2 d8 w W/ K1 y/ W' z" I0 x) O0 L2 m( H1 E6 k
for ( int i = 0; i< n; i++ )
2 d7 Y% n& `2 G: O2 ?/ E{
: m( X) F) b4 q1 n$ W' \ T0 @ if ( i % 5 == 3 && i % 7 == 2 && ... ). Q/ v' {: ~+ o! n* _) X. x
cout << i;
% w$ ^& _" k1 t" @/ d( N6 m}
/ w; z' x3 `3 X4 M2 c 但相应的,这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。2 ~' D% m) X, H1 f; r
8 S) z0 P. o7 ]$ u9 y; F
总体来讲,对于可以条件判断较复杂,且根据前一个(不)符合条件的情况较简单的推出下一个(不)符合条件的情况,(不)符合条件的情况分布较稀疏的问题,用筛选法速度较快。如果第3题中加一个条件被2除余1,用筛选法就不太合算了。
- `7 m' d0 Z/ n" [ ]9 c7 O8 _: P' s6 C7 R* [
最后说明一下,此次给出的程序目的在于说明方法,在效率并不是最高的 |
zan
|