: E6 m% J! x! C) Y, Z$ M1: 求1-100之间的质数8 s9 s- v$ d7 u
- i8 y! H& x5 y1 Q2 E7 a
原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数./ w0 }+ q9 U5 P: d
# n+ b7 S3 Q, X8 e. ~2 s1 q' ivoid fun1()) |' g" g. T6 w; y9 ~
{/ u" T5 w3 x M; K3 H4 y
int i, j; ) J' `. |- ~3 d a2 _! ^ bool flag[100];+ _/ H9 \& V) N3 h% o1 u
& {) i4 ^; ~% g( X' a for ( i = 2; i < 100; i++ ) 6 i# O& {$ T; \" _( s flag = true; 3 @+ I8 {8 l7 |6 J; x3 H% g; p 7 x+ z! O9 K1 v4 K/ C) _8 z //下面开始划掉合数2 p1 r4 g8 \2 r/ l( W5 L
for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根; d9 z7 i7 ?- N! ~, G
{9 f; v( W, s/ m5 z) V
if ( flag == false ) 3 o% G, j" H1 a' M$ l; g# j: ? continue; //既然i已经是合数，它的倍数应该已经被划掉 # Q4 f, C5 N; q$ Z for ( j = 2; j * i < 100; j++ )//划掉i*j- A% z( C$ w7 f
flag[i*j] = false;6 f7 {& u. V. L, U
} 2 d: }" `% c6 }) b) n ' E( Y' Y, Q5 j# z5 f& { //输出结果 8 r' b9 ~. d2 Q1 M; D" p( e' c for ( i = 2; i < 100; i++ )& G3 A! ?. s( u# p t' N* f3 H. @
if ( flag ) 9 R2 Z& Z; B2 Q' s cout << i << ' ';! L3 U, s$ h. H
} " f" V7 D2 I5 H+ f 0 r/ u8 c+ w- C- l: Y2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？ " o! p6 W6 A' |/ H# R % J7 ~% Y; n. v0 y 这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。+ ]0 Q# c' J+ Y9 B2 C: F
5 O0 J- q i2 e* H 另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。0 F6 W- N2 j6 _; P: S, l. K
; u6 `- f2 t* Y* |% ?$ u% {, M
void fun2() 1 w0 b, r9 l) V! L* `{ 0 a% M; _. X' [0 G* B bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉! K7 M: \( w8 x7 K) ~# C+ M# W6 { H
' a4 p2 t5 f4 C1 e( \0 T, z for ( int i=0; i< 30; i++ ) 8 p; k9 h8 K4 X' I3 N9 i flag = true; " I4 q' f# l' ^# K# U7 l, ?+ i2 v3 ]) ~% ]5 O7 Z5 g
int n = 30;//还剩几个人% G' M, w8 L" I& ~% x6 S4 H' ?
int cnt; * h2 g- d" C* K0 Q9 V' b3 M: c6 L int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便+ j" A# ~% ]& n8 g
while ( n > 0 ) . U$ g C/ v: L" C { ) w; A5 Q" l! k" Z( f cnt = 0; 5 j7 t- D! x3 L* A while ( cnt < 5 ) ( i; a" p" n9 `' m% D {4 _) {8 x- G& G5 Q
if ( ++pos == 30 )4 \" P2 x- F: C3 a7 w) M- s
pos = 0;9 y% ~' f3 u6 M5 F
if ( flag[pos] )//此人还没被毙掉 $ ]7 ~% K- S% W1 y cnt ++; : T9 _, \" i1 w* s } ; j5 I2 C) f: m //退出时cnt == 5，pos指向报5的人) Q0 G( R( L! x
flag[pos] = false;//毙掉* X4 g% q# w3 @+ a
n --;//剩余人数减1 , q Z1 v# ]. _ } 9 D6 y# A2 v2 n% O! v$ N //最后一个被毙的就是幸存者' z+ L$ F* J+ u- Z; c; P1 O5 j0 h) ^
//之所以加1是因为程序中从0开始计数，输出却以1开始计数+ N: r. [, O7 ?$ Y( Q
cout << pos + 1 << ' '; 3 ~, H' J' N7 T: [1 k}2 Z) ~1 j( o& J" w' ^$ y; ]. |
5 w$ Q2 K" ^* v1 K7 `! B3: 一个数被5除余3，被7除余2，求此数最小为几。 ! ^: E- b6 A1 L2 z# d 5 H3 r; U# n; f' U3 P, _' W! S 筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。 , f1 Y: O4 w1 C- c% d; t/ h6 O d 首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。 $ y5 z+ v) _4 a; q# T 在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。# Y' g; |& s6 a; M: Z/ `
% d/ m( ~% f( L# g. k3 z6 Y) g
void fun3() ! V5 r4 j( L1 P5 Q$ _) s, W0 ]{ % ~: P- o3 a# U+ I2 \ int a[105];//105 = 5 * 7' d! ~: Q7 E! t; |* i
int i;0 d8 o1 k: i/ h) q% Z( z# p
//计数清0 ( n# p- Y j; b6 I0 |; O8 t for ( i = 0; i < 35; i++ ) 5 [& W" h9 V- j4 A& a& Z' @- m a = 0; - C: X/ c% |: T# z3 B7 g$ [ //开始筛选5 K! ^; m- B! L B. ~0 e
for ( i = 3; i < 35; i += 5 ): Q5 h- w9 {2 u# A
a ++; . i7 |, t& u3 C- R for ( i = 2; i < 35; i += 7 ) ; u8 S' H2 ` n* |- s9 R @ a ++; * q0 |' h' W7 C& ?" [ * b0 W; \7 Z3 ?' H" w/ h for ( i = 0; i < 35; i++ ) + V5 w" _5 m3 e if ( a == 3 ) ' k+ P0 ]1 M2 z" M4 r4 l { 8 G, k: N( X( p) d9 R cout << i << endl; $ m, S% s3 b- b1 b! q6 ?% f% d* j return;& N* w7 U; y0 T3 p/ ~3 c
}8 c. I( @0 E& a& Q& e( k
//如果执行到这里说明无解 / z/ q T' s: G. ~) Q( P3 } cout << "No Answer!" << endl; - V0 Q7 a/ F$ M& V* P: t" t) J}7 W5 ?, P2 K* [3 T
( v3 K! r. ~& c% m0 g) U8 y, ?
; @( p! t/ {5 U' ]' c. U
总结： r- y/ }! _: y$ J 筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：* B3 x$ w+ t' p$ q: {9 i
7 t4 `: ?) B- i0 |9 i" Qfor ( int i = 0; i< n; i++ )4 ^9 v6 X- Z) b3 ]; A2 Z3 G+ k
{- Z6 ~ E7 y, l
if ( i % 5 == 3 && i % 7 == 2 && ... ) 5 F/ R) L9 E+ r4 X5 k( ^ k# \ cout << i; * j5 i* U( c. \8 b, T1 Z m8 G, [; p}5 x I2 |- W5 O/ Y# {! H- A
但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。' d6 o8 W2 f0 U
" D. h+ s+ D; @) W 总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。4 B1 D: }( {# f, R/ N
; k, j2 ]* a. Y% P7 i( n9 ~! y, ? 最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的