四、递归 J0>Q+Y
S<>e(x3g]
递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 bH=5[
能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 `$i`i 'S
【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 )jH"6my_
斐波那契数列为:0、1、1、2、3、……,即: XJQ[aU"[]N
fib(0)=0; N\vc<Zpn
fib(1)=1; !qcR5yk`2
fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 R1SEv$
写成递归函数有: 8IX6MfR}C
int fib(int n) m xWaXb
{ if (n==0) return 0; UA/3lH}
if (n==1) return 1; D8h~?phK
if (n>1) return fib(n-1)+fib(n-2); r^@*Cir
} [<%yU y
递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为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的情况。 u54+oh|,M
在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 $;@s
在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 l"MEX/
由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 K=~h1qV:
【问题】 组合问题 w,l1&=d
问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1 "'PDreS
(4)5、3、2 (5)5、3、1 (6)5、2、1 r)b`3=
(7)4、3、2 (8)4、3、1 (9)4、2、1 nyMA%9,B
(10)3、2、1 >#kzPYsp
分析所列的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。 wRuJein#
【程序】 LAr6J
# include <stdio.h> YY.;J3C
# define MAXN 100 2=#O4k.@
int a[MAXN]; ;bZ)q
void comb(int m,int k) J|I|3h<T
{ int i,j; ?d_Cy\G
for (i=m;i>=k;i--) v5*SoUOF
{ a[k]=i; 1.';:/~(
if (k>1) ;[6u79;I
comb(i-1,k-1); Bg#NB
else VE GUhI/d
{ for (j=a[0];j>0;j--) OixQlAb{
printf(“%4d”,a[j]); O|OPdD
printf(“\n”); & XrV[d[>
} KDY~9?}TM
} P= ]ZXj[
} E-Mp|y /V
c\R!z&y~
void main() *|4~
0w
{ a[0]=3; K_My4>~Il
comb(5,3); 7tyn?t0n
} nVYh1@yLy
【问题】 背包问题 G q:7d]c~T
问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。 )`U T#5
设n件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 !E*-\}[
对于第i件物品的选择考虑有两种可能: .AV--oA~
(1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 Tn-H8;Hg
(2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 3FS:]|oC
按以上思想写出递归算法如下: ha(hG3C
try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) !867DX3*
{ /*考虑物品i包含在当前方案中的可能性*/ @@I2bHyvb
if(包含物品i是可以接受的) *M8 4Dry`y
{ 将物品i包含在当前方案中; PCFm@S@Q
if (i<n-1) 7g=Ze~aq
try(i+1,tw+物品i的重量,tv); J"SAA0)@
else }b0qrr
/*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ BgE]xm
以当前方案作为临时最佳方案保存; b?Vu9!
恢复物品i不包含状态; Y@pa+~[{h3
} Ds-%\@p
/*考虑物品i不包含在当前方案中的可能性*/ k|BEAdQ%M
if (不包含物品i仅是可男考虑的) EKDv3aFQZ#
if (i<n-1) I=b#tUBh8
try(i+1,tw,tv-物品i的价值); myXp]=Sb?
else Maq{H`
/*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ 4[5Z>2w
以当前方案作为临时最佳方案保存; 5 :AAqMa
} {UwJg
为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: AU
>d1S.
物品 0 1 2 3 i1sc oxX3\
重量 5 3 2 1 O,DA{> *m
价值 4 4 3 1 6bU/IVP
)"q2DjfX*
并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 :1AOund
v[~ U*#i
按上述算法编写函数和程序如下: wlkS+$<
【程序】 m2 OP=z@)
# include <stdio.h> Ot/Y?=j~
# define N 100 7$w:~VZ
double limitW,totV,maxV; ukZL
int option[N],cop[N]; yyZjMnuD
struct { double weight; 6vmkDL8{A8
double value; 8T1`TGSFC
}a[N]; L1aN"KGMF
int n; t<$yxD/R
void find(int i,double tw,double tv) ()P?f ed
{ int k; ^^)Pv#[3
/*考虑物品i包含在当前方案中的可能性*/ {E@@14]g
if (tw+a.weight<=limitW) b@,w/Uw[*
{ cop=1; y_a~>S
if (i<n-1) find(i+1,tw+a.weight,tv); kWr*+3Xq
else 9m8`4%y=
{ for (k=0;k<n;k++)
kH{axMNc
option[k]=cop[k]; _:TD{ EO$
maxv=tv; BI}>"',
} ;}:"[B3$
cop=0; Vg2s~ce{
} <FGM/e4
/*考虑物品i不包含在当前方案中的可能性*/ *BSL=8G{
if (tv-a.value>maxV) in%+)`'nH7
if (i<n-1) find(i+1,tw,tv-a.value); $H-s(3vq
else #opFUX-
{ for (k=0;k<n;k++) lZb1kq%9g
option[k]=cop[k]; [5:F
maxv=tv-a.value; CjIkRa@!x
} Prr<:q
} Q%@l`V)Rs
-B@jQg@
>
void main() ncu>
@K$n
{ int k; Y5(`/
double w,v; 20hE)!A
printf(“输入物品种数\n”); "WK.sBFz4
scanf((“%d”,&n); 0;V2>!
printf(“输入各物品的重量和价值\n”); 6)Oe]{-
for (totv=0.0,k=0;k<n;k++) ZLBfQ+pM)
{ scanf(“%1f%1f”,&w,&v); \z<'6,b
a[k].weight=w; d~YDg{H
a[k].value=v; G&:YgwG
totV+=V; BEu9gu
} '"=C^f
printf(“输入限制重量\n”); =TyN"0@
scanf(“%1f”,&limitV); *}yW8i}36
maxv=0.0; W"z!sf5U
for (k=0;k<n;k++) cop[k]=0; #{<Jm?sU
find(0,0.0,totV); 2,dGRf
for (k=0;k<n;k++) [7L1y) I(
if (option[k]) printf(“%4d”,k+1); ?EKYKLwr
printf(“\n总价值为%.2f\n”,maxv); pNE!waR>
} v!40>[?|p
作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。 V18w
【程序】 /&dC? bY
# include <stdio.h> <udp:s3#T
# define N 100 5>/,25
99
double limitW; 3wa }p^
int cop[N]; $zDW)%nAX
struct ele { double weight; OHe<U8iu%
double value; 2D&tDX<
} a[N]; KWU#Swa`
int k,n; 6\'v_A
O
struct { int flg; >b<br
double tw; [|uAfp5R
double tv; u:fiil$
}twv[N]; C9({7[k^%
void next(int i,double tw,double tv) hX~IZ((Hi8
{ twv.flg=1; #y2="$V
twv.tw=tw; UB?a-jGZK
twv.tv=tv; :aco$ZNH5
} Qp%kX@Z'
double find(struct ele *a,int n) llQDZ}T
{ int i,k,f; 4l[f}Z
double maxv,tw,tv,totv; 0Ac]&N d`
maxv=0; ]vhh*
for (totv=0.0,k=0;k<n;k++) O{LWQ"@y
totv+=a[k].value; H@'Y>^z?
next(0,0.0,totv); M="%NxuS
i=0; c5^i5de
While (i>=0) 4B!]%Mw;c
{ f=twv.flg;
03_tt7
tw=twv.tw; Rl<~:,D
tv=twv.tv; ~(G]-__B<
switch(f) F|Jo|02
{ case 1: twv.flg++; eEupqOF*:W
if (tw+a.weight<=limitW) R6CxNPRJ
if (i<n-1) JF!!)6!2#
{ next(i+1,tw+a.weight,tv); 8tLkJOu
i++; !!dNp5h`
} }_XKO\
else SyX>zN!
{ maxv=tv; 'szkn0
for (k=0;k<n;k++) Ow mI*`
cop[k]=twv[k].flg!=0; @ttcFX1:W
} LWf+H 4iZ}
break; Q!|. ,?V
case 0: i--; }fL8<HM\'c
break; c\"oj&>A
default: twv.flg=0; t$rWE|+_z
if (tv-a.value>maxv) qDNqd
if (i<n-1) KZ;U6TBiB
{ next(i+1,tw,tv-a.value); aFd
,
i++; <86upS6
} 1rT}mm/e;
else '2v,!G]^
{ maxv=tv-a.value; n%@xnB$ZX
for (k=0;k<n;k++) 2'_Oi-&
cop[k]=twv[k].flg!=0; E #8 `X
} A]ciox$AjW
break; a!xKS8-S==
} # 1I<qK
} &+JV\
return maxv; bWG}>{fj
} *>zr'Tt,W
O. @_2
void main() Vg&`f
{ double maxv; `{8Sr)
printf(“输入物品种数\n”); H&`p9d*(e
scanf((“%d”,&n); 4s.wQ2m
printf(“输入限制重量\n”); X -6Se
scanf(“%1f”,&limitW); BX2&tQSp
printf(“输入各物品的重量和价值\n”); ;sCX_`t0E
for (k=0;k<n;k++) 03AYW)"}M
scanf(“%1f%1f”,&a[k].weight,&a[k].value); yz,ak+wp
maxv=find(a,n); 1&U'pp|T
printf(“\n选中的物品为\n”); rJKX4,M
for (k=0;k<n;k++) DJT)7l {
if (option[k]) printf(“%4d”,k+1); phEM1",4T
printf(“\n总价值为%.2f\n”,maxv); nD!C9G#oS
}