1 R- N N9 G. T' ~# |+ f9 \ n=n*3+1 $ x% R$ `4 `; Q7 C
7 ~ m7 [7 n7 G k
end if 8 {' |" X* m7 B) }" c1 D; X
- Q' I' P1 m6 l* y( s3 H' J 这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下: 6 S) w. y" Y8 P7 y
1 c, i% k. k7 m. t; D. N3 m6 h3 ?7 c
cls 8 l4 B% Z% m9 @ 7 E, S( K4 I" T input "Please input n=";n 6 v( N& |2 ` m8 }$ c5 r8 y U
" X9 l) C. Q7 p& X6 x1 f' { do until n=1 . h* h4 W1 E1 k: R& ~, |# `0 p ( G0 U! G2 f) @" D- I+ b4 } if n mod 2=0 then - }. J- p0 p3 N. X9 O9 _' D+ y& d$ l$ k& D5 p1 i0 F5 `+ e$ v
rem 如果 n 为偶数,则调用迭代公式 n=n/2 # F$ b3 S& L5 _+ R' a+ T4 c 2 m0 T8 ^% R: ~9 k1 R X n=n/2 + o" s2 E3 ~9 G9 m6 M" D/ j# S& t1 x5 T: j0 y
print "—";n; ( X3 q! g- ]) m" D ; \- m% V# q* e/ ~+ I else 2 r' D! |# R8 w | a& \ J0 m3 c
n=n*3+1 % G( w# F( s! c; i1 h 7 p( _1 _% ]" E* y! j# o print "—";n; 4 t; \1 }9 i8 j/ @) b
3 \) w5 o' C: A' ?* R end if # o- ~% N& o+ X' a4 F
: \& s7 _" W; y7 E m' ` k
loop 7 Z2 a1 g; z% d; z, i, @3 r, h 8 `2 g" H- T- u# v/ \* q end ' H( W" ?# V {1 R) l' z- k
% I S; a9 e, n/ z; x) c4 e: [ 迭代法 , R' @; B% O* w) _, S ) t/ x8 Y/ m; u) M; j, N3 k 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: . d2 F. E1 U! c* N# B' y+ H' _4 E7 ]. I3 \5 X0 R: C6 N' w
(1) 选一个方程的近似根,赋给变量x0; 2 j# D3 F% V/ e6 j3 c" J' h6 y/ p+ f
(2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; ; R* l, O, k+ A% u. | 9 a% k" q; W2 s+ h6 Q (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。 6 j3 d* \# W; p" x
% u4 U: u! d* U. w+ ?2 ]
若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: 3 B2 L! K9 o2 W! Q. c
: c6 A. [ Z* c0 A1 R% ^* {7 g7 e 【算法】迭代法求方程的根 0 z5 E& C) L" e! T- K2 ~ # y3 u0 i5 N { { x0=初始近似根; $ z6 Y2 ~; J ]( Y+ b9 T
/ ]: T$ F: z% v$ V
do { : k s& B; x2 e. J5 t! Z, A+ L
x1=x0; % Q3 C/ `7 P( u8 i1 W9 Z3 | 6 `' W0 |! \2 J2 W- H x0=g(x1); /*按特定的方程计算新的近似根*/ 6 g" o5 x- w6 ]* ^) A
$ M1 ]0 l% |) }5 G/ F } while ( fabs(x0-x1)>Epsilon); l4 }/ d, g( y! O
1 {# y) o6 s8 d3 p printf(“方程的近似根是%f\n”,x0); & q# @. k1 m$ h2 w' k. w) E
$ r9 S) M; J# R0 N! M 在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 % {/ y+ R1 _. m
( {* a: {" B& Q5 D9 J D 在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 8 y2 k9 h7 X* s * p" p! t) c0 E7 [0 d v! a1 Z" L# t 由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 # ~" D; t; _5 ^" m5 K& { & |$ q* M( w* v( T 【问题】 组合问题 % K n! ]& i+ ^) F) F: Q: B/ z3 z( I3 p) a2 X. C
问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1 , t' |! b* {, U' `2 S+ i) c( q) l " ^" L% {8 C0 G6 o# Q g (4)5、3、2 (5)5、3、1 (6)5、2、1 : `: C- T! l$ K+ c+ w/ } w, J) H8 x. U1 F4 F1 ]2 l4 I% }
(7)4、3、2 (8)4、3、1 (9)4、2、1 f8 q# o. u/ U
$ [2 `$ |7 R) b$ V7 O
(10)3、2、1 5 V p1 n9 h* W+ g# r8 h
) S; o" l; b4 q2 G 分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。 p' p3 V! E+ H2 ~
) H( Z* r, l; W- Q4 o; C4 K
【程序】 : V, U- j9 d- y ]0 y8 l F$ r 5 K% _+ F( M5 J; j: R2 e # include 4 h# L+ W* _, n, ?3 F, S/ U/ w( X# B" \) f X1 d
# define MAXN 100 * ^( Q- d1 Y N' k* X( V# W- k8 h
2 K" r( n3 }# x
int a[MAXN]; + Z' M% T' S5 J# n3 p$ [4 ^' _, _" H5 k% _- B# O
void comb(int m,int k) & O4 p! Z% ]6 P5 k
. j; b7 s( }6 B* q { int i,j; ; f, f% n& H) z9 z4 [! s! N: k, u
for (i=m;i>=k;i--) - ^. Z, x& h- v6 F5 g0 p, |9 k) F% _2 k! u
{ a[k]=i; % i3 Y3 f$ m2 [- V: P2 Z
+ ~! B, ?+ Q! a, M) l
if (k>1) : t' n4 ]- T# N; l8 F ; R+ P" Y" h. c4 u0 d* p' g& a7 e comb(i-1,k-1); 7 B8 D) L1 X9 e& ?7 q4 Z, w! s$ x, j" J7 v: A1 @
else - Y+ Z+ X; C0 n
, r$ W k: q/ N$ l! V { for (j=a[0];j>0;j--) # l% n- w% z5 v1 k$ s ' I) L$ F! L# h; D0 S printf(“%4d”,a[j]); 0 p& X' M0 c6 w- }. |6 h) }
+ G' `/ a. i# ]' [3 v# h( f printf(“\n”); 3 C9 @; O M. E
6 I1 m" l* |/ t0 N6 k' _ } ) d# M: g% v6 d' V+ p: ?: K7 v5 w- O( g/ V& x
} 3 p K. \) w% ^! U- Z
' L' P: E" B6 P) E3 ?! I4 F1 U2 d } % h/ Q1 g8 I% H; J0 v9 Z 4 x6 T7 I, K8 h1 g' o void main() 1 { g5 b4 s' M' Q$ m" u+ i* v- |5 Z
{ a[0]=3; 0 @ u C8 J, F+ q t
# C! A8 f: K, v& t( P$ K) J9 A comb(5,3); + a6 x J# s$ h' C
0 P3 T& N# l, I# B/ |
} / \! @5 |& ^! D8 z3 [ a
' t2 j5 ]& k" d0 T0 b 恢复物品i不包含状态; ' }& t1 D+ s% Z0 R( w# ]& [ $ Q5 z9 K3 M% B: d$ h } 9 V1 S8 M V8 H& Q4 Y) P3 k: p* R
! ^; z) L% n2 h. a8 x. R /*考虑物品i不包含在当前方案中的可能性*/ : I4 ]9 L* p% T4 f7 F* N
5 f, `4 N* ^- U% Z0 z; P
if (不包含物品i仅是可男考虑的) ' k8 r1 c* x8 U' K0 U' o 2 [/ ]" C4 ~+ H5 d" _2 a, i' J if (i . T1 A, y/ y- y g+ Z
; k) e" C, j( T ?- t0 k" i try(i+1,tw,tv-物品i的价值); 3 N2 J3 P, x* x
" }& |- [( s$ l1 ~7 A- g- G else ' Y5 |4 L) b7 y) k+ [+ p
3 ?. P' ~0 U2 ]' D
/*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ . }" A- k: Q! y! E; r- ?- G. ~
- n+ W$ z2 I, U0 ~
以当前方案作为临时最佳方案保存; ; J' R% @+ J" @0 L# I! O
Y0 b' F8 N: j' K3 y" K
} 8 r% F% N# M7 h, Z9 f" L# H" ]8 v4 M
为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: " E/ r1 [6 j* \. J' c 9 t6 \4 |2 [, K$ h 物品 0 1 2 3 4 |; ?7 a% v9 X3 ~7 { 2 D# X' s, \: Q) N) M- c 重量 5 3 2 1 5 J7 h) t5 E3 r) ~; x% T
: G! F! E1 ?7 ]' @$ o, p 价值 4 4 3 1 . \3 s8 `+ I; c* P
) z2 n' {! F# B# b 并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 0 s; L* B: o' j
# n/ k3 E6 V% ^4 i: D: z5 I 按上述算法编写函数和程序如下: # K* p' G& t! ?. g+ X. g
( n6 k$ `; [. S
【程序】 1 @' ?7 f# ]8 a# Y, J4 x& L0 h
9 z: V* a- d4 f9 u8 L
# include % ^6 \8 t+ m) ~ ^2 U 8 Z, X6 i2 y5 s+ y, t # define N 100 , q$ b w9 U; \2 d [" j0 c7 V! i
! _! j: [- ?8 i/ ^+ P/ Z' o+ O
double limitW,totV,maxV; 1 G7 R0 _+ M; N5 ^2 D ) Y) {+ q' e b8 P# k% u/ l) P int option[N],cop[N]; 1 D) N: h( `$ k/ n5 H1 `
5 `4 H% E, Z/ [1 S9 k1 ]
struct { double weight; % S& D; h) K6 m9 l# H* \$ u7 _) W% g+ Z. Q( ?# |: }7 F
double value; $ P2 s/ k% I6 _
0 v) D, m$ |4 F: }, x8 t/ U }a[N]; / k3 ^8 [$ |' G) l' p5 @
N6 N( H+ X1 \( j! P% J H+ F
int n; + K/ \# S+ B5 r2 z; _2 B7 ^- z- Y- r
void find(int i,double tw,double tv) 3 L( H' d# _1 O# X
& @' v6 n7 }8 j3 _: C2 E' p1 e( { { int k; - Z0 D3 q& Z6 X1 l& W% @) Y8 i& y+ m8 N! [' _3 e
/*考虑物品i包含在当前方案中的可能性*/ l. P5 v1 y$ C$ r* I
& ^. l% t' q) C: x& y6 T1 E! k/ ~9 I
if (tw+a.weight<=limitW) / \, u# X7 i9 w' T( m' J5 W, n) v
3 ^# z2 J# \9 G4 D; X { cop=1; , I+ t6 U' @6 q/ W# b" e- n" U; _
, _/ L2 T- u! t; D) R( S- q
if (i + J' {9 C% z/ n$ h3 n4 p 9 A, k! f; G7 {: @ else 5 ^4 a x4 E) q# A" n* P * `; Y/ k& T5 b { for (k=0;k 4 f7 v3 i2 q6 W$ d. i. M
2 a" T- ?0 X8 } option[k]=cop[k]; + e4 s4 G2 `7 n& t
1 G4 H) r: p& S
maxv=tv; % Y# T! A; ?4 d6 M6 U/ k 1 \) q2 U1 B0 \8 Y" k } 6 l1 e( N' a2 V0 m7 a' f; q: U. O$ `' O: l0 F$ l
cop=0; 4 P4 I6 g' _( e1 k! H
* P* z! i* ?5 C& ]
} . h0 p% V/ p3 X! o. O
: P: _0 ~- [( v5 U( S# ~: a, v1 u
/*考虑物品i不包含在当前方案中的可能性*/ + ?/ I4 ]0 N6 J* F& U4 L 2 r5 |- r( y) I6 V/ p if (tv-a.value>maxV) 6 c0 c9 k" Z u# K" X6 A ( t% ~1 |& y! R$ ~ if (i l d; K8 z F; v7 A- ?/ Z( X; Z 3 L* f: c" N0 p else 2 D$ }, Z* `' S! f: p* b% m: r! C& J0 d Z, ^
{ for (k=0;k # J% o# Q8 |% X3 @9 M* \. Q
) `) p7 V+ y9 t$ p option[k]=cop[k]; ) b9 V" z+ o$ r; I- h9 l# ]) ?$ s
7 @! n% S0 ~! k+ p% r
maxv=tv-a.value; ; K( K# }& f9 I; o, |, j: }5 ~/ Q
. ?/ B$ ~9 h- e6 A' P
} - i* H! ]" O% r$ e: ^" Z- M
, d3 f7 Z# t/ X, q" v; b+ w
} . t# P. E8 _( K' v0 l; ~
9 G5 [' p9 H: }* T1 i+ |
void main() 3 z3 L, A' F$ i; u7 o& M; z% Q
+ G. G* L; ?6 w { int k; & z; ]' r( R: v9 T7 N1 |" q/ _
double w,v; 4 `6 @* d& G& l% @ 3 \; v; I# N, ~ printf(“输入物品种数\n”); 3 a8 z4 j) z7 r, O7 \ |9 V$ n/ U$ y " f! `* Y% N* J. E, B scanf((“%d”,&n); . L) ~* d; H' @. A" s2 M( t" i9 C2 E. d1 c# P/ q1 ?: ]
printf(“输入各物品的重量和价值\n”); : o; h$ s- X/ ?) ]
1 r# i3 Z$ s' v# U3 Y
for (totv=0.0,k=0;k , ^4 o0 b( J' Y
" |' B$ A; S9 {* G { scanf(“%1f%1f”,&w,&v); 5 K0 F3 ^& J6 p
7 h+ T" C# P8 o O: f
a[k].weight=w; # v0 Q0 S( X. `9 I! {: s' u9 P1 n5 G' F' K. T% [) s7 `0 n! F2 o
a[k].value=v; 2 i' M C4 {$ {8 |' f% x4 U; ^7 t& A5 @/ f7 V, T5 h
totV+=V; 9 r E/ K n- h) H* |* z
9 z5 u6 l ~6 S3 O
} 8 P( D# r' i9 q1 ^! E$ V, u! P+ ~2 M( z5 E
printf(“输入限制重量\n”); ) W9 S- B6 O* v4 ~# i) \8 {
. z8 T: m( T5 Z. l$ e2 A G k; X! y int cop[N]; : U( p0 V; v5 i0 F
5 o1 d, M9 Z& m8 d' H) O
struct ele { double weight; - x9 S0 m) P. G) d. z2 x# T1 f/ v& g: N" J+ d8 D& b! i" t
double value; 9 E' G1 ^. N' C, }3 D9 i) k) b7 t8 F8 J
} a[N]; : [) u: q' D7 m- E |. V $ c, p. Q7 y6 }/ b int k,n; / W6 X( g4 g# o3 c: k7 O2 a& ~! O# h$ o/ l4 `; d( S: g+ B
struct { int ; ) D) L/ m2 B7 h5 Y) z* {: C4 e+ W1 ]/ y
double tw; : l7 l, h( m4 z# o$ @
2 e( G0 |& E1 k. N% P# p4 x double tv; 3 c) o }5 h6 Z- f9 v: E9 l
+ ~' Y' @$ e1 U# F
}twv[N]; . w' L9 t8 \ P Y* ` 9 a& {/ J. ?! C void next(int i,double tw,double tv) 2 Y& p1 M5 e ^9 d* n" Q4 d
) q, r4 ]5 ^5 X1 B9 n# I8 @6 J8 G |+ c { twv.=1; % |( y0 a" R& @# i4 n4 u, Z" P" n3 Q0 y
twv.tw=tw; 6 p4 q, z7 {" r* O5 c9 D# H8 v Y' K4 o
twv.tv=tv; 4 j7 \2 \! K8 R" y i1 J; Y
& T s; \# h( [' X N7 w } " G9 m# v2 g( ?7 L4 g 3 ^& a6 y* k' c7 }/ k y1 \' k double find(struct ele *a,int n) 3 G+ s7 M r" S0 c& T* w9 T
) l$ }* I6 J4 e E$ q# T
{ int i,k,f; " Q5 g+ S6 G* }' H
, s- S6 F! ^1 Q double maxv,tw,tv,totv; % m6 m }; [' J ; Z; [& ^$ j7 H maxv=0; ' P. @9 ^* X( q+ G8 Y) G . e7 A0 V+ P9 I/ `/ x for (totv=0.0,k=0;k , ^4 Y, w, ~- Q. K
! S1 E+ E3 S1 M' C5 P& ^, b! {
totv+=a[k].value; : A! g! G# ]+ m l+ f t9 a2 o0 J- t. B `1 Q! ^# e, ] next(0,0.0,totv); ; J; ~5 g9 X+ v5 K- s: F+ j2 _
; b+ S! g, J1 E+ c, _; P i=0; 8 d0 ?/ N% ~, t% G* n
* x4 _+ ], y: W4 A While (i>=0) : B) Q; q/ e; y0 B* ]! T, J2 X0 \5 v9 [4 v) w- k6 i
{ f=twv.; 2 t# E6 ]! d" [( a& @3 e1 W
+ z7 o; W! W! t* l
tw=twv.tw; 2 |+ ?- ^( ] V* o
% N+ l* U+ H0 [. S7 \9 I W& l tv=twv.tv; 3 f8 _. q4 e4 H
: c$ m+ h7 Y: G; J switch(f) # G- S+ F5 t9 K h0 `/ q1 N8 v' A, I t$ g
{ case 1: twv.++; 7 H8 y' t/ b* y. A) O
& g8 ?- i0 z/ T! k
if (tw+a.weight<=limitW) ! l0 F. ~" [ d* q1 }. a7 K2 x
q3 B- W2 r% F$ H( L/ y- Y/ U; b
if (i * v5 Q7 O9 ^- Q9 c) C S/ [* g I* A1 ^7 K$ ?1 ~' C { next(i+1,tw+a.weight,tv); & N; d+ V- z2 V. a . [! ]. [. q4 G, X0 `* x: _6 r# Y' b i++; 1 A0 b) `6 m4 W4 _* P( y : @& `! m. m. s$ F, P } % \4 A G+ l+ w/ |/ S1 a: C; W8 z9 f1 F& }
else 4 ~6 I1 a/ C! ]8 q* ^4 g& [
) c) l+ c/ E% k& S* q
{ maxv=tv; / X7 e4 ^+ K+ G7 A( O) E ) u7 p& ^$ j& _* { for (k=0;k 3 K7 q) _; [% L2 T+ Q% k! r/ y6 G
# r* ^9 g- N! L cop[k]=twv[k].!=0; % k: G2 f# y! U* W! V( ?8 |, q0 t3 u
' f7 Z9 ~3 x& O6 ? } ) S& p2 D& S7 [+ y- D0 Z
- D# V; X. b% }( a% d. s
break; * A: w5 A; d2 l* I; @6 X / ]# J; }2 w+ k9 W) j case 0: i--; " n; l& {* d# f: p1 j% x
/ V' @4 s4 H% ?" C1 W' }' J break; `, G/ X7 I+ b7 u
# z& S. J. I/ |
default: twv.=0; 6 C! D) b5 u( p5 A- d
+ H% v0 z" Q% G/ B Z( q7 u6 e
if (tv-a.value>maxv) 9 p9 L# `8 l! C7 m) o$ S9 T/ x( Y8 `2 Y% X
if (i 1 T! V5 u1 v2 J0 c6 S" i 4 V' s0 E9 f* N( ]' D4 j { next(i+1,tw,tv-a.value); . l P4 c/ P7 C( i, B8 I
% e6 G" h$ ]$ b i++; ! G3 h" Z4 J: d- m , a- U5 W6 C0 ` u } " B* x1 C3 D& I* S# J
6 \8 |2 S& G+ V" C9 w9 G8 b* K else 1 r/ A# j6 Y6 H, M" A