- 在线时间
- 0 小时
- 最后登录
- 2004-7-22
- 注册时间
- 2004-5-28
- 听众数
- 1
- 收听数
- 0
- 能力
- 0 分
- 体力
- 124 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 43
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 4
- 主题
- 7
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   40% 该用户从未签到
 |
所谓筛选法就是从全集中将不合格的项全部删去,剩下的就是答案。
1 d/ K" X Q2 d5 G8 R
, x$ @1 D- R9 s" X1: 求1-100之间的质数/ y* M1 x) g- D' X# }8 d+ F
& T& e/ C# M, @' n7 a
原理:先将2的倍数全部划掉,再将3的倍数全部划掉……直到将10的倍数全部划掉(10^2 = 100 )。剩下的就是质数.
& o$ l6 z3 v* ?$ Y; V5 C) b: ?/ A# s( s, v* y4 [1 C/ @; I8 o6 a
void fun1(); S+ {& m4 O% [6 N$ e3 d
{4 Z* w1 ^1 ^( f2 D2 m" h
int i, j;
: F- }' E3 Q! o* Z0 [0 V bool flag[100];
8 @% o U4 o3 o1 }( u
# G. P3 i1 k2 d/ u0 M. g' W for ( i = 2; i < 100; i++ )
6 Y! K1 C9 j( T/ i0 s, ^2 n flag = true;
8 r1 A2 U" v1 h+ N7 o
2 P' A8 I+ x8 y. E* } //下面开始划掉合数
% n$ G2 [: Z4 g2 _$ t2 t, h3 { for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
' G8 V8 G# @% l0 l' ` {0 {9 n% f1 f: j9 Z3 l" ^; L0 A' W
if ( flag == false )( `! ^7 w& L* r1 W1 Z$ q
continue; //既然i已经是合数,它的倍数应该已经被划掉3 ~# @6 q! |5 r+ l
for ( j = 2; j * i < 100; j++ )//划掉i*j
0 p& v( {- B4 T( U flag[i*j] = false;
9 X, O7 k2 a4 b3 E( m q6 T }% o& M; _/ e8 ^+ B" N, Y# r
/ ?$ T$ y9 J1 H; A3 A& } //输出结果# d0 U5 o2 L, f, G# f* K" M8 }) r
for ( i = 2; i < 100; i++ )
. Y% \ ]4 \! S/ ^ if ( flag )
4 I6 F) @& W+ s% c& s+ A cout << i << ' ';; \5 O- {; H( q4 J
}
. A/ K& J/ q* C# J3 r
, W' a7 b- s; k8 M ~. A2: 30个人站成一圈,从第一个人开始报数,凡报到5的拉出去毙了,剩下的人接着从1开始报,直到只剩一人放掉。想活命该站哪?
. | V* I3 R6 Y0 p; @& O* q
9 d; g* [5 I& \ t1 S9 N/ o# C 这是个经典问题,解法就是模拟整个过程,有点类似于循环队列。
2 G" \/ ~9 N) c' w) o0 O& X0 s0 g& f0 X( z [: j0 D
另外,为了程序上处理方便,可以假定所有的人都拉去毙了,然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候,对问题的问法稍作变动,或者将初始值、加减变量的位置稍作调整,用程序处理起来会方便很多。
5 K$ `- K0 e+ b& i8 h2 b+ V) g( ?! S6 ^- i/ }" i8 q
void fun2()
% S7 l6 m" P% v{
$ Q+ |6 s e0 Z7 |. {. o; S3 b- ^ bool flag[30];//标记第i个人的状态,false已被毙掉,true还没被毙掉
2 u* [. s, X$ e
4 H9 e/ i" x0 L6 F+ U) _1 c; r for ( int i=0; i< 30; i++ )+ b3 g' j# @3 k" U/ l5 F7 ~
flag = true;. g7 Y$ j6 S# b7 H9 u
; b1 j) u! g1 J7 u1 r
int n = 30;//还剩几个人
5 O2 v3 x% S, O- }% n int cnt;
; @: @( }4 F8 R3 ~9 }: M7 ?1 L4 M! ` int pos = -1;//初始值不一定从0开始,设为-1处理起来较方便
0 w/ m0 g$ `2 ]" Q while ( n > 0 )
L) i9 W" l, `4 v2 l. _2 c$ F {6 i- O5 X# K4 L0 q8 y# E
cnt = 0;
7 `( \# L' j) y) X while ( cnt < 5 )
3 g8 _& W1 l- a2 M" d2 K {
4 D7 k2 L/ X" J+ @- d$ _ if ( ++pos == 30 )
1 K' w1 E: L) H. W9 L( G pos = 0;
4 M/ p" _2 U5 A( O/ V if ( flag[pos] )//此人还没被毙掉
2 r& r& V, D f$ ? cnt ++;
+ i9 W% W. T0 l$ {2 m& W }
$ k; T& u; | P. r5 ] //退出时cnt == 5,pos指向报5的人
8 {3 R, b' D0 w: w flag[pos] = false;//毙掉3 ~+ ^! o% Z7 h3 U# o. E1 N
n --;//剩余人数减1
, F4 _4 @- Q& ~; {: k }. M; t9 w1 o7 T3 t
//最后一个被毙的就是幸存者
4 D0 G6 f5 H% h e0 L2 A( h9 b' U; z //之所以加1是因为程序中从0开始计数,输出却以1开始计数
- k/ c9 x2 o- k+ x1 U3 r cout << pos + 1 << ' ';
- x/ K" w+ ]' H7 ~: }8 y) K" k( U}
# G. H( m y0 |, p" N: i( [8 { H7 e, f1 w. }& b2 c
3: 一个数被5除余3,被7除余2,求此数最小为几。
- J+ r+ G7 k6 ]0 ~
$ f) y' u! s3 i/ ?4 R( ^( X3 G 筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选,这个问题就是一例。$ ?8 m8 ~9 o2 q4 ]; p9 w
首先,如果问题有解,则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
7 O; z( p6 q1 I0 \9 d 在程序处理上,如果一个数满足一个条件,就将计数值加1,最后计数值为3的即为所求。- b6 W' P) O: |( P
9 G% @3 V7 h- g" Mvoid fun3()
* g* c n- u6 M7 e3 H{
/ z8 ^8 M6 d4 b4 G int a[105];//105 = 5 * 7
9 o* {( r- i# k int i;
/ d* d4 i4 p {6 X //计数清0
5 r% T+ N( O9 r g W' {+ u0 L for ( i = 0; i < 35; i++ )
1 \% B4 H' D4 c$ W# q0 A- m! r a = 0;
. F% T* m! W8 @! I( y) C //开始筛选( a8 O, K4 R" \4 D! h9 V2 d" m1 D
for ( i = 3; i < 35; i += 5 )
" ]+ ]4 Y% t* e# ]! d a ++;$ T1 a! v2 p+ U0 o5 n6 J: v
for ( i = 2; i < 35; i += 7 )& q; F' C8 h, c
a ++;, M1 l/ u! R" H" a( l9 P7 j
% k, D7 `- w; M. G- Q" N; d* B
for ( i = 0; i < 35; i++ )
5 @; J- p7 D8 Y4 Z9 U if ( a == 3 )/ A' f J& m& h. W2 ]6 O3 R
{7 F5 D& v E# @- `+ }: H
cout << i << endl;
# B+ L1 e# Z9 |/ v- U: q H return;
6 D% U2 u# b: v# E" q }
. _( O+ b* i, P) G; c //如果执行到这里说明无解
9 }6 A, b$ u% \+ |% Y cout << "No Answer!" << endl;
* a- H L: l/ w& L9 D4 N2 X' T}
1 W: [7 c) h3 X/ X1 C' ]4 a7 b2 a3 K2 |8 J& u* w
9 m1 ?8 `/ L. P# L1 `( J4 h$ P
总结:
; A1 O6 {1 m6 V 筛选法的时间效率较高,但需要一个辅助数组,这就意味着对规模很大的问题不适用。例如第3个问题,条件多1个,需要的空间就翻几倍。解决的办法是:
# ]- L: ]+ A! i- E& a
: g7 Q: Q J+ q" M! W# p- ffor ( int i = 0; i< n; i++ )
9 c9 U) \) o, Z) C' h' ~$ G{/ h5 b* m9 R0 T9 j8 R5 ^
if ( i % 5 == 3 && i % 7 == 2 && ... )( s0 \( f; k" G p" D
cout << i;9 H+ X8 R: u, j/ G6 Z
}' m( X* D+ _5 d
但相应的,这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
9 A2 K, N3 j5 S0 |6 h% Y6 k$ t* q) u8 }. R7 f: y( V. }% n. W
总体来讲,对于可以条件判断较复杂,且根据前一个(不)符合条件的情况较简单的推出下一个(不)符合条件的情况,(不)符合条件的情况分布较稀疏的问题,用筛选法速度较快。如果第3题中加一个条件被2除余1,用筛选法就不太合算了。; d* Q) f+ `- `6 W$ P
9 {2 P! v4 f1 @$ K1 y
最后说明一下,此次给出的程序目的在于说明方法,在效率并不是最高的 |
zan
|