- 在线时间
- 0 小时
- 最后登录
- 2004-7-22
- 注册时间
- 2004-5-28
- 听众数
- 1
- 收听数
- 0
- 能力
- 0 分
- 体力
- 124 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 43
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 4
- 主题
- 7
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   40% 该用户从未签到
 |
所谓筛选法就是从全集中将不合格的项全部删去,剩下的就是答案。 b, z6 f; z9 q- u4 i
b) U9 H0 P8 E7 a2 z
1: 求1-100之间的质数3 z6 q5 \! d; O) j
/ k1 b5 s/ u* U" [% P
原理:先将2的倍数全部划掉,再将3的倍数全部划掉……直到将10的倍数全部划掉(10^2 = 100 )。剩下的就是质数.# V2 Z, }) @3 ^4 C% d, K1 d
3 @8 D/ R X2 b8 E
void fun1()
* m7 H3 C8 U& U" t& o{4 z6 a/ w1 L6 c- n, Z. A! k! \
int i, j;
1 G9 n1 c6 O, d I# x( j0 B bool flag[100];
8 Q, P# d: {; h! c
[# G/ d; a8 Z8 W/ J& E for ( i = 2; i < 100; i++ )4 ]- O& X# U8 A% B
flag = true;6 S' b7 l& L1 g( h! B: {; y7 {
- G& ~: K6 l' }- j* F4 |
//下面开始划掉合数3 w$ X g! Y1 a/ T( g
for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
" g, `$ S; m& u; \9 t M {
* U6 x* C G+ q' T if ( flag == false )* N# T, C6 P2 ]* \
continue; //既然i已经是合数,它的倍数应该已经被划掉
; c* |- a3 M! U1 Q* P for ( j = 2; j * i < 100; j++ )//划掉i*j
# Z5 c' S' k }9 s2 o' ^2 W! v flag[i*j] = false;
; b5 }5 o+ [. d }
- }3 L& s2 U: |- s3 f
" K3 r( f7 O" y% R6 s, E7 e //输出结果, G! f6 N4 c, t& I; z: }
for ( i = 2; i < 100; i++ )
3 t$ E6 D- J4 a: Y if ( flag )9 e; W. d/ V: |" y( O; ~+ h, X! t
cout << i << ' ';
! v/ d9 ]$ G7 q- M% s/ p! H# E j, L}$ {) W( X6 S2 E6 Z2 S1 s1 \' d" T6 g' E
. P% f4 J. b# M- q
2: 30个人站成一圈,从第一个人开始报数,凡报到5的拉出去毙了,剩下的人接着从1开始报,直到只剩一人放掉。想活命该站哪?% l2 q2 { x; `* l2 s9 J) u6 P
( Q( f* ]* H; j7 q+ @$ X, b 这是个经典问题,解法就是模拟整个过程,有点类似于循环队列。
2 {7 G" w5 r0 x) q9 b6 t
. ?' F6 o- f8 h+ Q 另外,为了程序上处理方便,可以假定所有的人都拉去毙了,然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候,对问题的问法稍作变动,或者将初始值、加减变量的位置稍作调整,用程序处理起来会方便很多。, W* x6 \; B z3 X5 b6 g! X! V) |
9 L9 J- X1 f, q/ D. F6 N$ ^
void fun2()
8 U0 G' }/ M: I8 [4 y9 G3 ? x{
8 F: c4 ]! m: p! Y bool flag[30];//标记第i个人的状态,false已被毙掉,true还没被毙掉2 u7 @9 C, k+ K/ K. V3 \
: E$ ?- D4 D9 d& }3 S$ h
for ( int i=0; i< 30; i++ )
e' Y8 }8 G/ N# K& e; ~ flag = true;$ ?, q2 U/ ]2 J% f; J8 q% |
* q" c. x* v) K$ Z& I4 n0 W int n = 30;//还剩几个人- i+ p# B" m e/ g7 f
int cnt;9 l* N% k' C9 W# e( c
int pos = -1;//初始值不一定从0开始,设为-1处理起来较方便
5 O6 w9 r9 q$ r2 V9 l6 _ while ( n > 0 )' o* w S* @" g% L: N
{+ N3 X3 u2 |# c* ]; w" `
cnt = 0;* M* ~' _, \, H* r: l
while ( cnt < 5 )
/ r. n0 m; X9 I5 Y$ g0 u {+ o" C9 |1 S% k, {
if ( ++pos == 30 )/ w6 S8 ?+ l- l% t K
pos = 0;
& `& E7 e5 B/ U; U6 S, W if ( flag[pos] )//此人还没被毙掉! N0 H; T2 b2 o: m# ]2 s/ }* g
cnt ++;
4 \/ ] W2 B/ J/ \1 _# N" t0 f }; D8 C0 @; ]4 d- _0 h
//退出时cnt == 5,pos指向报5的人/ G+ h5 c! X- h) f: e1 E
flag[pos] = false;//毙掉% |' o6 I' U2 J, B
n --;//剩余人数减10 J$ |! H7 {! D5 k
}7 t t" d; y, i- _6 \2 W) K
//最后一个被毙的就是幸存者
( M- T9 c/ U/ C8 |1 c% x //之所以加1是因为程序中从0开始计数,输出却以1开始计数
" J% \' Y3 H/ C$ @- I9 l cout << pos + 1 << ' ';
% F3 q* D+ T% H9 ]# \% t, L}: C o9 \ a y2 D$ z% b" u) t3 e6 U
3 c+ i$ o$ h0 T3: 一个数被5除余3,被7除余2,求此数最小为几。! U7 l: U+ [! J' [* y" F& i
5 U2 Z( h: b- Z" e3 a$ j/ |% A 筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选,这个问题就是一例。
, r ]* v' W2 b+ F 首先,如果问题有解,则解必小于 5 * 7 = 35,只用在此范围内筛选即可。& O' ]3 V8 t4 ?3 c! ~* G( P
在程序处理上,如果一个数满足一个条件,就将计数值加1,最后计数值为3的即为所求。; G# I8 V* ?4 C; n& a0 I) A9 J4 p
, i/ e$ C% ~ R5 g9 K' w) j
void fun3()
+ W* ~, j! A( q3 x8 j& T( U) g# P% B{3 A6 J1 i( C* x& C1 Q$ q! m6 i
int a[105];//105 = 5 * 7( q3 }/ v9 H, P3 A
int i;) y2 _& J; [8 h+ i
//计数清0
; S: t/ f1 e# T- ^ for ( i = 0; i < 35; i++ )
% c$ w" n! |+ ]+ [ a = 0;
& Q' y4 f1 P# i" x$ V/ f6 _ //开始筛选
6 J z! y" u% h6 ^' Q. f% m for ( i = 3; i < 35; i += 5 ); Q1 G+ p( s) t
a ++;
# ?6 i# K* X8 ~" U, k for ( i = 2; i < 35; i += 7 )
- X) L& F# P' ? ^, b9 k# u* ` a ++;
$ f" m) m9 ]$ O, ]: m5 v$ A( L0 O% i) p( A- \+ c0 ^
for ( i = 0; i < 35; i++ )3 P& m F/ ^' B7 K2 m
if ( a == 3 )
# _1 Q- f' V6 [2 X% t {4 Y- J5 q5 f, {0 {9 x$ p1 B9 K) f
cout << i << endl;
9 G. ], p) f+ k% _1 U; H return;+ z- }1 w' e1 l) ?0 o- c, d
}* {2 D9 r( y" i+ W9 o
//如果执行到这里说明无解
# w1 R g2 E; \' b! X cout << "No Answer!" << endl;; S _, m; I4 U
}9 i% w) l; m$ `0 J ~. t
# g9 R& W3 n( Q! ^, m3 X6 u5 T
9 B4 T0 _) ]! N- W# A$ g/ m0 c, g' C; {
总结:; S% p$ j# D( {0 Q' m3 G- e3 g
筛选法的时间效率较高,但需要一个辅助数组,这就意味着对规模很大的问题不适用。例如第3个问题,条件多1个,需要的空间就翻几倍。解决的办法是:
+ ^/ i8 X$ `8 }: L! @9 j; \3 Z/ h! s
3 P& b" }, A5 T$ P& b, y" @for ( int i = 0; i< n; i++ )3 F6 m0 t2 V8 q
{1 Q- F9 L! i: _+ K5 q
if ( i % 5 == 3 && i % 7 == 2 && ... )# h) d5 g( w1 M% q
cout << i;& y. u8 T* F: f( ?% L2 ^/ D
}
1 M' @+ ^: S" l+ R' t# {0 p# c0 K 但相应的,这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
( p$ B4 J9 r; _+ | I8 K8 {+ V, ?# B/ o# F4 C1 h# k5 Z8 O7 o
总体来讲,对于可以条件判断较复杂,且根据前一个(不)符合条件的情况较简单的推出下一个(不)符合条件的情况,(不)符合条件的情况分布较稀疏的问题,用筛选法速度较快。如果第3题中加一个条件被2除余1,用筛选法就不太合算了。
/ c5 Y/ e* ~6 I7 V; J& F3 Z( w7 Z$ t7 }5 ~6 S
最后说明一下,此次给出的程序目的在于说明方法,在效率并不是最高的 |
zan
|