* A0 S% x% J C 迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 2 N, o) j) i7 d+ O" F0 e( A9 i2 e
利用迭代算法解决问题,需要做好以下三个方面的工作: 5 C- h- G. J0 A- c* |$ s+ H; R
7 K( H5 ]6 q: I. L5 D 一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 2 d" \/ z% B& D0 i , M* p9 `/ Q; W1 h1 M1 F$ }2 H 二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。 * t/ @3 k" n. E$ ]- d; @7 x$ x' [* F' E/ h
三、对迭代过程进行控制。在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。 6 C& M' j1 d% E* @. Q6 w0 D$ |# v9 L' W/ T
例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只? ; J, ?8 w9 |9 x% h+ W! A' u ! R3 N! t4 t6 O0 l1 t, @+ W 分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 ( d9 U9 V& J" r: M$ y9 \ , n4 `- J6 U6 s" N8 K5 ~! F3 u u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,…… 1 Q' M8 Z w' e0 ^ [# u- }4 j/ o- e( O- P 根据这个规律,可以归纳出下面的递推公式: & H0 q2 _* K8 [5 W, T# W8 o# n& C# }% r0 |
u n = u n - 1 × 2 (n ≥ 2) 8 R6 `7 V+ A. l: S: p' B* k , e5 }6 o" E2 H, l7 h- x 对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系: , u! v) L4 Z8 _
7 J: k& [& G4 R/ ^! D( d y=x*2 H0 J' [4 M. P7 @6 ^. p: ` ( O* n; y" o9 L) [; { x=y # [$ b) L, g1 o; |- E
( m% {# v: x- d2 T 让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下: 4 k3 |- E/ n3 F) D# ~$ _
5 n+ |0 X A8 K+ \3 i0 m9 N6 A
cls 5 C. w9 D _% m1 e% N5 `6 ~# H! R/ V
x=1 " V; G. \- ?4 T+ M % r' v! a6 H: b& J+ f. }9 W6 M for i=2 to 12 , y" J8 w5 \' R+ }( p9 S2 w+ g $ y5 G( M0 X- i y=x*2 6 z9 b* X: Y( d6 ~+ D% r
+ v. L" C* Y6 w) Z. R" D
x=y 1 S& b4 h) V& q c) f% p ( L$ v* U& v. e- f/ \) r- X next i $ S2 A1 f8 _, s! e) t* v) W w* {: E+ r8 v- ]' R7 K
print y ' S, R' v; q: b5 A3 n2 _
( [9 C+ x p- B, K; N' U- q' ?8 x/ y end 1 }1 U: Z1 r4 a- i( U7 r ( X* Y& c* q! P, F7 _ 例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 220,220个。试问,开始的时候往容器内放了多少个阿米巴?请编程序算出。 6 M g/ e; ?! [6 I. E4 ?
3 |- u9 O. y i1 O- f 分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴2^ 20 个”,即阿米巴分裂 15 次以后得到的个数是 2^20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2^20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。 # T6 B k3 s. d$ [( {1 Q) |9 j
1 D# [+ a* c* u5 H& l) T 设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有 / i! u4 m& F& U [& M N1 @2 ~ , }8 [* M% x3 N) ~ x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1) 5 `! q2 H2 W5 W U* Z2 u% u- h7 ?( F9 }2 n+ ^; c( r) u0 s. M
因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式: " @0 E- G2 }5 Q" H
- W. q8 @7 J6 [
x=x/2 ( x 的初值为第 15 次分裂之后的个数 2^20 ) ; i. L5 G% q4 D' M$ U0 T, t ; N1 C3 L8 w7 R! Y/ k" u/ {) D% t 让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下: & o' G9 z$ R. \1 m9 M
' A/ j: H. U! ]# I l cls 9 c' ?/ A) b, e$ M# h+ b; M" O f& Q: F$ l9 k" g
x=2^20 ( ?, R9 s/ p, _6 E G, A9 c 7 V" R7 u: j: B+ |2 l) ] for i=1 to 15 . d6 S: [3 T) P! h4 B( K) i 2 w8 i+ H) \8 E: N x=x/2 + e' R e& r0 \$ F% v) {; { y, l ( [ v/ x# K& I" l0 K+ t6 H- ^ next i $ i4 |5 Q& Z, \
" b* x3 @& z6 u9 U5 z6 p _: [
print x . X& z# z) Y5 e& G a7 | o$ V4 M: S
end$ h. `1 T5 p- B; I3 }( X* c
/ d( a6 h) p0 ?4 J8 H/ Z' S- D ps:java中幂的算法是Math.pow(2, 20);返回double,稍微注意一下 9 R3 ?( N: y) B7 d( C9 [$ W4 Y' C / v9 I7 t' t( N, `* Y0 B1 _' m 例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。 , Y8 g* T; v, T v- A
, Y) T) Z5 f# ^: x
要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。 ( v7 ~- k1 X* \+ _& @7 C( l % C) Z, ~0 v, |- S$ f 分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是: : s$ Q: Z0 _+ d/ V
, }' D% r* I& C2 O8 b0 I1 D/ Y
if n 为偶数 then 5 _ U) f3 |. Z4 [* V4 `3 v2 _+ \
$ i& k; S i' _/ |5 n, d; }1 B n=n/2 ) D0 \7 n, _; D1 p* i4 @* f1 h9 X- S
else 6 G0 \& n# m% j4 o! a 9 c/ T. [& J! o4 P# K n=n*3+1 7 N k) f0 l) R' d. j( v% J
/ O& d1 _ ?9 n; y; B- s end if : o/ E# g9 U9 N' H) t$ E% ?8 m) r
0 n( ^6 ^( v) U U 这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下: % [/ M4 |( x/ h# |& c
6 Y) T9 Y9 n: ]5 t8 g4 V
cls ! }6 l( g2 r" y* A' y
, r2 j$ l! |) f1 r/ W input "Please input n=";n # T' l/ i: ?/ g# N: _9 Y0 n5 f% z" o! G0 c8 {/ x/ N
do until n=1 ; M0 O- R6 t& U# J/ k5 T% e) L& ]
/ V; s( [* t5 z7 K: a
if n mod 2=0 then 9 p9 h/ r) r" e
' Q. f- M+ L3 q rem 如果 n 为偶数,则调用迭代公式 n=n/2 4 E% h0 I: H7 S$ j& _
& P; b5 N9 u6 A
n=n/2 9 d: Y4 o: |$ `/ K
* c3 `0 F }; W/ e# ] print "—";n; 9 w9 o+ `5 \% n( s. w- r) Q5 {: G * y1 r# p" B" c" v, V8 u6 U% w else : Q. z/ X( E5 H I1 A2 s4 s 6 D$ r3 j) { Z/ \, H n=n*3+1 6 e9 b B( D) T& ~; }$ ]+ } " u' k1 @* m. v ~4 V' E+ G$ @* c print "—";n; # G* Q2 U- g4 i; g / ^4 Y( _/ U" L2 a+ t end if : ~6 G& S" X& x& W V 1 Z" S9 o% \; @# @! [3 C loop ' _6 k. S h. Y8 E+ i) e : o6 n' d2 x( j end * z+ G* d0 q& u* G8 ^9 h& [ 4 p: ^3 J, w* ]! i/ i9 } 迭代法 + l# q J2 I! Z9 J7 D {
5 S9 v0 Q% N! E; Q+ b x2 r 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: ! Y- L9 W+ X! @% Y6 Y' X
# V5 _& y# U& L# o" e; `$ a K0 U, U
(1) 选一个方程的近似根,赋给变量x0; m* h* b; a( n1 }8 x" B
) J, q+ J2 S0 d l2 ^8 T* l1 O (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; ! v' Q8 E& e+ W2 p
$ W- u" p1 O5 P! b2 x (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。 5 O J% _( X- [" o, E: d, u( z' Z& ] 2 r w6 {" |5 f6 t6 P9 O 若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: . h% O6 w5 I( N' U
% i7 e9 g. `: s9 [
【算法】迭代法求方程的根 . I( ?7 z( T# L. {& N% J 5 F: q3 P- l: x9 l { x0=初始近似根; 0 G" o3 h3 \6 }( l - w" S q7 u* W2 Q C# A M do { $ i4 V5 w$ E9 p9 h" Q
9 K8 [$ y* L7 W D x1=x0; ( J' v7 `: B, p1 Z! h1 I; X: e" Z
' ^& j( y+ }2 Q. W; U1 r
x0=g(x1); /*按特定的方程计算新的近似根*/ , z/ S9 m6 E1 G3 E $ y! M) t3 v1 x } while ( fabs(x0-x1)>Epsilon); % Z& F, l: I) F# y0 z6 m2 J& A
) t, M0 i; m3 Z2 }- e } * y; k+ o, ^, u+ N$ X" J3 i9 U1 f @2 S X: L7 p3 p% O. d
迭代算法也常用于求方程组的根,令 : m+ F- |5 B$ E, Y, a
' w+ B2 e; j* l3 x" V S0 M5 Q
X=(x0,x1,…,xn-1) 7 B; j1 J) o& b: F* V8 z. S9 h: ^. z% t% E
设方程组为: . n% Y) c9 `5 E# L
* a$ ?& ~: H7 i6 Z4 j* l/ @/ v xi=gi(X) (I=0,1,…,n-1) d- N' W1 H" i s5 U% C
! y# Y2 \$ s& M, f 则求方程组根的迭代算法可描述如下: & [$ ~9 n7 F, H- m* ~# D# \* s6 z6 q6 ^8 O9 z" ]+ F" e% s
【算法】迭代法求方程组的根 % u" x1 Q" Q- A v. |7 Q
* u: w3 R% A9 D- o* G$ {
{ for (i=0;i ; X; b8 c# H$ Q; U' U6 V) M; ?" P' P6 S
x=初始近似根; ) J Z3 d J5 _9 B
5 E* o# J K/ `2 x$ L8 E do { : w9 _6 F" Y9 u6 r, [! S7 c $ p7 T9 O- z3 k' K for (i=0;i . U, O5 m1 G: t
' G N$ ^0 {+ @5 x, ^
y=x; : e0 `, M1 o; V- w$ u
9 l3 F% ~. r$ C" i for (i=0;i + X, y7 ]3 e+ \( x: h. ^1 H$ _3 d; z3 c' T1 w0 ]( R
x=gi(X); # a9 }1 @7 T/ h2 a& |* G' q: w
$ c3 R& m* k* T
for (delta=0.0,i=0;i ) P3 W& k1 N4 C& C0 m5 V) Y
0 g2 E) k; G7 a4 W o
if (fabs(y-x)>delta) delta=fabs(y-x); # T% n, D* G' d" M; F; ?% ], ~ : U/ Y1 k# k! h' J) j2 } } while (delta>Epsilon); 6 n9 R2 \0 B3 h* P+ y ; M B0 [, U9 r1 F5 s for (i=0;i 1 V. ]+ ~2 x! W! U" N' J u" c$ U) P9 G/ G; I: u$ S printf(“变量x[%d]的近似根是 %f”,I,x); 3 h. K/ ]6 X* R; a, B% r- W y* N) X9 h. V printf(“\n”); ' a" U- a& ]# x1 o
! A7 G! \) p7 N0 o+ w2 x } 8 I; X+ E: m% B Y$ x/ g" a( \1 ]$ h. ` m) y/ `0 I
具体使用迭代法求根时应注意以下两种可能发生的情况: 8 W# C# D: \% V" C) i2 P
; e9 x" `9 F/ _. _) y
(1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; ) q' z, b' t. f* @. }& w1 L0 G" l* L' L" V5 E& O
(2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。 & E e! V: r+ ]2 x, B# O! C3 x( |) h# E
递归 # K: y* X2 q5 X* c+ P+ C! Y/ u
; n- s. n5 u( {: m 递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 ! v( Q c$ {5 k- _% j1 A# n, a : n: \" a$ I& W! @5 L 能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 ) Z0 c; ?7 N; m/ y1 F# |
$ k1 D. j% T2 |5 x 【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 I. k+ d+ [, O8 K) t3 Y$ j$ M& H( Y% @) Y
斐波那契数列为:0、1、1、2、3、……,即: 8 ], g: H7 l2 S y/ Y ~ * B; w' z& _$ l/ h' e1 U1 _ fib(0)=0; " Z1 x$ j! W7 b) [+ n. P
8 R9 c+ A: M; H% T fib(1)=1; 5 ]% h3 |8 E; M# ]! Z/ z5 J
% p: p' r. j" D Y3 _. _. f5 V0 n1 u
fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 , a# \5 \" m6 u; e' w0 i! D 0 H- k7 c v7 N, i 写成递归函数有: : ~, o# K; Z. R, G: O$ |# T8 I
! D9 x! a; g% Q int fib(int n) ! Q7 X# e( c) j3 _9 R
9 F& M, W% \; q) a$ ]# h
{ if (n==0) return 0; * \) f- ^- _# [. E' Z6 Q. k7 v A ' \0 g2 S5 I7 w0 C# |1 D4 i if (n==1) return 1; 8 Z8 Q' \: j7 r6 e( i4 J + H3 |! k- i. f1 I if (n>1) return fib(n-1)+fib(n-2); 2 Y5 P* p. N. {1 C2 j. B2 ], t& P" b) x
} * }6 p \/ q# C' \/ }0 ?4 l
7 a/ v& j7 z& d1 ]# Z7 w6 ^$ K 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。 & |1 l q$ q9 |. H2 }9 V+ x( h
& N( R+ l3 v+ `4 I- m* a" Y
在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 , k6 D, O4 J" M ; [+ [2 r/ C- z U 在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 ( i9 d- `& C. w5 J5 T& W ' W/ u! {$ [! A 由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 # Y. U5 ?! y; j3 B4 D' g 0 [" Y5 L% `5 F- {0 W$ G: g 【问题】 组合问题 ; G4 V- e H- ^( M* Z e, H& }. E/ ~) S0 t0 i0 Y- l m8 S2 Y
问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1 0 z+ _8 e* J3 {
; ~+ q2 l" L. B$ s (4)5、3、2 (5)5、3、1 (6)5、2、1 " ?4 d2 E! y7 b, z( |2 d% x
. O2 S$ {+ N( x9 g' v
(7)4、3、2 (8)4、3、1 (9)4、2、1 " e4 t! I, X$ y. ] 4 p3 ^" k: F' R (10)3、2、1 . m/ F2 A7 d; U& O* N/ w
! [+ j6 F, n# M; h7 e% j
分析所列的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。 ! q% w; z$ u' M7 N
# ~) U* H8 _4 m s# D6 q+ K9 r2 H
【程序】 # y3 X2 ]. j* V! d0 I& U4 o. `- ` \2 [4 g0 D- C
# include : ^0 F9 B1 @& X% w5 h
: F% A2 x( Z2 v) m7 @+ I. { Z/ u1 f/ r5 e
# define MAXN 100 % s( o0 c" A# \- r9 E6 T( }$ {: t$ N; E. w! }& T
int a[MAXN]; 0 }, j; t, |9 O4 H1 U* m* Z; h
7 ^, e6 P. j7 b1 D void comb(int m,int k) Z- h. n) k& S1 I {# E& v( W4 N! v/ c9 v
{ int i,j; 8 k1 i+ d. E" R # D! W+ ^* m# e for (i=m;i>=k;i--) : G; ^4 W3 Q2 q4 u ; \1 Q/ s+ b. K5 g' Z( G { a[k]=i; - C+ V; \7 X# n0 W: L8 G5 Q# y) }6 ] e% ]6 R5 y2 u% v* c
if (k>1) * b) p0 {: }' p8 C
0 F" _# T3 c8 c+ I' p2 n6 f comb(i-1,k-1); 4 o! _4 F3 x6 h& o; k
4 c$ b: O$ g8 M
else " `' J* {0 ~" j3 U8 L9 S
$ R9 p8 ?3 w+ \) t, U { for (j=a[0];j>0;j--) 6 R U0 o. F5 h* ^
s+ v3 _' f% q+ S8 O printf(“%4d”,a[j]); ; D. R# W- I# i/ }
$ m* f+ y1 b; i) C" {5 g/ R printf(“\n”); + n- o( q! {/ [$ h* Q3 c
* F2 [5 I4 |7 e' g
} : I1 x& ~ E+ F O6 S' J6 l; a* N4 I3 D! u' L } $ ~4 b+ t! t ~$ {5 }, d, c
. a' N+ O- p$ t/ O
} & ?. Z" b7 i" {: _ x2 b6 Z7 D# |% E% |, ] W- j5 ?- }+ h
void main() - i& a3 P6 M, D* ? ! _8 J+ l, o5 y% E( \2 B { a[0]=3; ; e" o* T2 U# O
8 e5 v( q% `7 s/ U
comb(5,3); ! N/ D" E+ d9 U2 ] 5 I& D5 z; E/ p: Y- A: g# R& [ } + x) ?7 s: o* ^$ c3 x" e
4 C! y/ T. q) A' j) l: n. d ~/ s# T 【问题】 背包问题 * K( [3 F; M( N0 D$ r7 z$ `
$ {& X2 V, @7 y7 o! v 设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 # J/ N" D \$ n' @
- D- S2 h: F& D7 z# Q; ]
对于第i件物品的选择考虑有两种可能: 9 \5 `$ p9 h0 R6 l( V- S( |1 t
; _5 G6 [6 `0 \" J& t$ D (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 : I3 {2 z! Y0 L
0 v( `/ J6 `9 d, w- B z6 y8 r7 F
(2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 : y& o4 b! U2 L9 G) K; L1 m9 w7 I6 J2 @. [. q! K& N
按以上思想写出递归算法如下: ' G% l; U. @9 s8 q
9 x" n+ q q/ v' T
try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) 3 {3 z" x- Z- A9 \ X
: `+ o2 @$ `# d5 g6 Q" k8 H( j
{ /*考虑物品i包含在当前方案中的可能性*/ + j5 e/ A8 Q1 z. }, m+ r% ]/ g1 K4 D7 i, P4 T
if(包含物品i是可以接受的) 8 a6 D. L; S3 z! n7 P
1 X! p. c: U: S2 K L { 将物品i包含在当前方案中; & I! ?( X: l8 H {* ~# Y + a, q3 O. {( x8 r: C" R if (i 1 i* c0 f6 ~, L7 v
) O# a& n$ d i& S7 M
try(i+1,tw+物品i的重量,tv); 3 ]" ]3 h% r2 D, D " r: K8 W( D) L( O. w else 3 L2 b4 I9 q7 L" q3 N1 O / L5 Q1 y, ?' Y+ C _ /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ 8 L4 y9 s& }, g! S # v. [. J- m' U j 以当前方案作为临时最佳方案保存; 5 z5 G5 q" o0 j+ H; e
v) {6 D0 @" h. J7 C
恢复物品i不包含状态; 8 F! \. T) _3 K; e H# y, O+ q( o' p o% ~. H; W K
} & `9 ]3 Q# e9 [. }& U6 U0 P' C( x- x9 l; B% ^/ W, v. ~
/*考虑物品i不包含在当前方案中的可能性*/ 8 @' i) G }5 ?% s# j/ |* l 7 K5 |- K3 H9 ~$ z2 D. A if (不包含物品i仅是可男考虑的) 2 o& M% s# |% C) e2 Q( R5 u* o7 z# s
if (i 4 y! ^, L, ]$ b0 i8 q6 Z$ F* E- Y1 W# |; S
try(i+1,tw,tv-物品i的价值); # J/ R. W4 N$ C; b: `# \4 `( a$ ^: R: }3 D9 O8 f/ ~
else 1 D: F% x3 J4 P; U _# D0 e. A' h' Z+ Y0 H- Q- O
/*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ 2 _/ ?6 z' S- B* k! W" ?% F
5 C2 ]; U' [9 }% E6 s7 ^0 |
以当前方案作为临时最佳方案保存; ) W7 q. s* I4 g2 e$ ^5 f8 _! w2 {. k
} ' p% P" {5 d d7 T) g/ [; z2 o# X7 W
$ E( S0 A. l' ?7 m 为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: 8 z* D$ U. [$ P& u% c- j 2 s4 u0 Y$ p6 c 物品 0 1 2 3 7 U1 A9 C( |# K! j9 z
5 b$ Z! N- u- `
重量 5 3 2 1 / o% n7 @9 v4 s) Y5 x- U
& O/ l. r) |* F m q
价值 4 4 3 1 " o1 Z) h0 |0 Q& j5 `- V) S5 }
; b" l' p- E/ p$ G
并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 & T- c7 j3 u; _! Z8 O, ^ , x2 u5 D$ Q) a* c1 E$ H 按上述算法编写函数和程序如下: 8 Z% e- i9 E3 q% S* {. d . v' f# \) \+ K. b 【程序】 ! H& L! V5 Z; D. [3 q+ y- r2 q2 C" q) A/ y1 c2 r
# include 2 W0 W& D ^# T, D ) A5 @5 R# i6 m5 C! n3 V# D # define N 100 ; ~& N- ?' ] H% Z' y6 ` x8 p% o6 M" z X$ K4 U+ r
double limitW,totV,maxV; 0 Q# L) F( L$ f R) S( l p
2 T5 V, w% A# S4 u. a3 X" t5 b3 M1 n4 G int option[N],cop[N]; " E `7 D6 ? Q6 W5 \% Z1 \' s& O( u+ \+ P
struct { double weight; 4 k* f+ d9 H) ?2 j l# A; ]/ h2 K* M
double value; 2 ^# o8 c/ l" B g7 u: h+ ?! ~ / `" W% q7 n n( T! c8 \# O1 z }a[N]; 6 o8 s( \2 {. i) y0 x1 l8 \) c
" N1 @# u9 f# W; w
int n; 7 t; R n d* K/ \" T( |5 O" p0 a" e; a, F! n6 _
void find(int i,double tw,double tv) - j% e& `/ n# l2 ?) A5 A- S
& F/ J* t/ \; T9 V' W { int k; 8 K6 m( T) g, s& r4 @0 D. S( g& } ?2 `
/*考虑物品i包含在当前方案中的可能性*/ . z7 P3 o) ^ I; s
) U i9 ^4 s0 Y
if (tw+a.weight<=limitW) $ k* u: o/ v! G, b4 W
4 |& ]- T% L" S, i# z
{ cop=1; ) j/ g' P6 u# Y7 G ( C7 {: o2 z5 x if (i ' b) }; K: s4 f( O
( F$ s* U+ T3 v1 Y) N4 e. p else " r+ e: J; B, T& r5 H2 d$ Q+ T
% E2 p4 B& E k8 E$ N { for (k=0;k $ Z% S9 s3 ~4 }- v
d% t. `3 y& d# b# A, B9 X option[k]=cop[k]; , l0 P1 s5 O; a
, X$ i! @+ y+ K1 `/ ?& z( ?- F& T
maxv=tv; - n5 m& E+ D, E! _8 T
# k; B" o9 C9 u2 W" f' V0 Q
} % K# a0 A1 R" n& \9 Y! x
0 T7 R3 i' \7 x: H cop=0; + F& I5 f- ^: ?( Y* N
: n/ t* t6 a1 l* h8 t4 D# Q
} * @ d8 q1 Q" W! y. Z6 C* K e3 k" M* }9 I. g
/*考虑物品i不包含在当前方案中的可能性*/ - j: z7 J& j8 p0 e 1 `( b: [: d& I6 k5 T8 s if (tv-a.value>maxV) . q) _' |7 t! e9 r% Q/ l 8 g+ g1 Z2 ]2 Q4 T5 I5 A: `9 B if (i 5 r9 y- N' e( ^% { 3 `* \+ [( I7 \) W else ; T/ y: \ V" V: |$ D$ M+ D1 Q* U" f `
{ for (k=0;k 4 U9 A9 ^' \& f7 l3 H7 e( p7 t2 e
option[k]=cop[k]; C3 m/ b, B$ L* c( u$ J" J" d' S4 r# @ $ |( l% O6 B' f( y, S- ]; i& d maxv=tv-a.value; " \/ o' Q" O9 U. m8 ]9 r" r9 k& [6 F( Z1 [9 j3 S4 N
} 1 Q7 w; `5 i4 E& u
3 z6 s5 O, ^5 I' d* @! A
} $ {$ C& l2 j6 [8 z" o2 _
* n4 A- B; j" u, K" k void main() * K) z/ C8 d8 S9 N$ q1 K 1 [) P5 }! Q$ y( T/ M1 y9 j9 G( l { int k; - h* h p" [/ B- v" Q; d& |1 y
- ?+ a* i! P* M0 K double w,v; 1 I: V& U. {2 W$ r0 N. w T9 G
% J9 z G) F9 `3 Q& e# U8 `/ U. { printf(“输入物品种数\n”); 0 b8 n8 P! r$ D
: [+ K. u0 D' ^5 Y- z- b+ x$ G
scanf((“%d”,&n); $ z0 y7 j, t( |" ]' `, J & k1 a* n. o) {3 ]% U printf(“输入各物品的重量和价值\n”); ) @6 d& ^( r+ _6 N
" |, x# ~- A q1 ?
for (totv=0.0,k=0;k ! [% d! O5 C, \ y
3 A, G' r5 }* G* u' a* D4 Q. J
{ scanf(“%1f%1f”,&w,&v); # c' ?4 h R: Y) q, ^0 F
; k3 }6 L6 V" @) @" ~# @( u a[k].weight=w; $ s0 z* o- x/ J8 Y
2 f3 l5 P+ K4 v' v; \
a[k].value=v; 8 d! w' Q" J6 u4 n0 \- |, M* m" G: w% m# U, A
totV+=V; 6 ] U Q" s/ l; J% m
5 u+ ]( ]) B- i# [6 Z& H! q+ F } 5 }( q5 X' z7 L9 U6 P6 o( ]
3 O. A3 ^( C+ N( g3 U
printf(“输入限制重量\n”); ; G9 d( {- c" V$ p5 `) n% m* D3 @$ K
! |' l# Q1 p' U+ ~5 M A
scanf(“%1f”,&limitV); 1 O; G: o/ w8 R0 ~: Q2 l! E
! B& V1 _" \2 i; |* W( Q8 v" l maxv=0.0; ; k |, x& Y1 G
* j7 L8 P9 j" s" h5 Q L1 X for (k=0;k find(0,0.0,totV); 0 x k$ G: W; J+ E( i( F7 l9 z + W$ b6 e) k. @3 z$ E# z# V' R for (k=0;k ; ]+ s7 u. A4 H1 E, v3 F2 E9 g3 T1 M; U8 ?% D$ c
if (option[k]) printf(“%4d”,k+1); $ k2 E; t% m1 |2 b
; Y4 F, X* S& Z" z/ i6 G printf(“\n总价值为%.2f\n”,maxv); , W2 x: i; ^* w/ D
: u4 B7 y8 a; q3 E2 ] 【程序】 8 O% ?3 w: H. } 6 z" w- M0 l6 Y1 d3 F # include . U: H6 c( J) {0 Q, b, Z9 z * V/ F) \9 O& T' A1 V) d # define N 100 , G' s- P8 x7 Z9 v
' _5 R2 X" w0 s2 m @; A double limitW; ( t# s" I6 s, j# Q 1 V" {3 E! w8 @- p- k, [ int cop[N]; % K. y1 e; G9 b" n( C. K3 P" L; \2 J# R7 ^- w
struct ele { double weight; * u) l7 ?7 c7 T9 h7 Q1 q9 f( F7 k+ f9 w7 ]' @/ }
double value; % ?( d7 ?( M' {( m' `- A : X: c- n G# E8 P' l" r: x* F } a[N]; ( P( V7 n( I9 Q* L# S x
$ n5 q7 ?6 w' Z5 X
int k,n; 2 F% t) U2 L9 `, x
' W9 P: o" U' \9 M7 |" p struct { int ; ) E, Q0 s1 ]) }- h* g: c& g9 {
1 q3 W9 h' k0 H J
double tw; : A5 e' E8 |1 G& v3 @3 ^ - I c" R6 w; Y. v$ E double tv; - b, A$ R6 e& D. v4 s4 x' {. v$ s # E& _: v% P) P& W4 I }twv[N]; / M' d8 W8 g5 i4 Q, d. \# @9 V. m- q' _' z! e
void next(int i,double tw,double tv) 7 A, I% F. z! ^" H4 H
* Z4 {; O9 N8 C
{ twv.=1; " B, k- a2 S8 r1 R) L ?# @! y" a3 E twv.tw=tw; + S: ]- P% a' i2 b
+ d! j" |6 @; Y3 k7 |/ _7 R
twv.tv=tv; 2 }6 s) t+ ?( x: l! f$ r6 Y6 P; d n ' ^% `) [2 k8 B# h2 f. U8 k% Q( G } , Q3 `6 U6 q% a2 O. ^ ( B) ?6 g# q* Q) s1 ~ double find(struct ele *a,int n) 1 F) O. V1 n$ _: H! K' H! y 9 M7 s R6 X( _4 r' @' Y [5 { { int i,k,f; ( t W) G7 d% h1 e- A $ O3 B7 j- g$ S. |1 k double maxv,tw,tv,totv; T' s1 L8 y9 T3 P' i% u! u# R5 E4 k A* N
maxv=0; ; }0 o8 ~9 A0 ^- u5 a+ v : @1 w7 M0 y0 ?& [4 H for (totv=0.0,k=0;k # o. S+ m& _) e6 U/ r
! C$ h$ Y# a9 l( e, P totv+=a[k].value; # T/ k. J4 p4 W4 c6 s
; n6 P. b2 y% D0 v
next(0,0.0,totv); 5 ]- e D! i P, O
' ?7 a7 L* }& v+ @& V2 ^
i=0; 8 g' i8 s4 s s5 h$ P+ k / g- t! _: R3 L l5 B) O While (i>=0) 1 F$ f7 h/ }8 t5 y7 O) {
, W. Q7 [- x# M: z3 a) h printf(“输入物品种数\n”); " P) L! K+ N) b4 c' I n 1 |9 }& q0 y( f( } scanf((“%d”,&n); 3 V8 }7 w$ I3 [$ q
3 A% D9 e* o8 l$ E printf(“输入限制重量\n”); . G L5 t8 m X1 |4 Y+ M. d
/ [' g" l7 b* S9 U% `
scanf(“%1f”,&limitW); 7 o+ I9 J9 \) @9 U |# [& ?
' e, K* `: R# F. M0 P( Q, N
printf(“输入各物品的重量和价值\n”); u' N% z/ Z& u& c$ p) |3 t2 r. n
3 F' v7 I4 O6 Y+ l for (k=0;k 7 ~) v( k f+ y( x 5 x! k& f& M- ^6 ` scanf(“%1f%1f”,&a[k].weight,&a[k].value); & Z* D0 v0 ~" x& I
! m+ E9 ^3 f; y3 z/ Y4 T. P3 T maxv=find(a,n); ; l& n7 {9 A# t! ] * m- Y% f+ ~ f* ]% j2 D/ C printf(“\n选中的物品为\n”); : _* h/ J" M) \+ A! @5 z0 Z' m
/ k( D0 F2 O, q% s for (k=0;k * M/ T# j; B, @2 r6 ?6 C 1 b% u1 P* Q+ O2 u/ f: ? if (option[k]) printf(“%4d”,k+1); 8 t7 n" O) X! [) X: g! p" M& \- q
$ [+ e3 l2 R: T1 q7 P3 ^ printf(“\n总价值为%.2f\n”,maxv); 9 n7 E0 B" [. o& T6 f . j8 [3 D/ T, E" A, H& M1 U } 8 |$ B; m# [2 n4 h; t' P9 P& F- }- t9 W# C
递归的基本概念和特点 7 q; d8 c E. Z