四、递归 ryUQU^v
a:IC)]j$_
递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 BdblLUGK#
能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 cZU=o\
【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 k(7&N0V%zz
斐波那契数列为:0、1、1、2、3、……,即: iYm-tsER;
fib(0)=0; PB`Y
g
fib(1)=1; xvl#w
fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 3z9d!I^>k
写成递归函数有: &n}f?
int fib(int n) O#~yKqB
{ if (n==0) return 0; 9YQb&
if (n==1) return 1; e+BQww
if (n>1) return fib(n-1)+fib(n-2); Z|j>gq
} [KaAXv
.X
递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为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的情况。 P& -Qc
在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 })8N5C+KU
在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 qqr?!vem6
由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 f:|1_ j
【问题】 组合问题 6J6BF%
问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1 .A{tQ1&_
(4)5、3、2 (5)5、3、1 (6)5、2、1 j2.|ln"!
(7)4、3、2 (8)4、3、1 (9)4、2、1 sn$9Shgh
(10)3、2、1 1&evG-#<:
分析所列的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。 Gm.T;fc:
【程序】 ujq=F
# include <stdio.h> 9gEwh<
# define MAXN 100 ?;+1)> {
int a[MAXN]; a /l)qB#
void comb(int m,int k) '(yAfL 9}
{ int i,j; g:D>.lKd
for (i=m;i>=k;i--) -)]Yr #Q
{ a[k]=i; e~[/i\
if (k>1) OXSmt
DvJ
comb(i-1,k-1); q#ClnG*
else %D}kD6=
{ for (j=a[0];j>0;j--) LW'D?p#
printf(“%4d”,a[j]); FR4QUk
printf(“\n”); pW@Pt 3u
} ag#S6E^%S
} z.9U}F
} mD0f<gJ1
m=A(NKZ
void main() Bp`]
{ a[0]=3; A8fOQ
comb(5,3); $i}y 8nlQ
} &5spTMw8
【问题】 背包问题 ;I 9&]
问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。 <+Dn8
设n件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 YY((V@|K
对于第i件物品的选择考虑有两种可能: Ym{tR,g7
(1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 EQyC1j
(2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 RO VW s/
按以上思想写出递归算法如下: C] eSizS.
try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) :W:K:lk
{ /*考虑物品i包含在当前方案中的可能性*/ j4qR(p(vC
if(包含物品i是可以接受的) }=UHbU.n~!
{ 将物品i包含在当前方案中; E$:*NSXj
if (i<n-1) W*4-.*U8a
try(i+1,tw+物品i的重量,tv); o"Euwh!!
else #ASz;$P
/*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ o]` *M|
以当前方案作为临时最佳方案保存; @+M
/&
恢复物品i不包含状态; KL:j?.0
} X_ cV%#
/*考虑物品i不包含在当前方案中的可能性*/ {M$1N5Eh
if (不包含物品i仅是可男考虑的) WJndoB.f[2
if (i<n-1) 1i"WDu*h3
try(i+1,tw,tv-物品i的价值); 5k3n\sqZA
else <fjX[l<Uz
/*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ {3p4:*}
以当前方案作为临时最佳方案保存; Av$^
} 1N^[.=
为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: ^f
&XQQY
物品 0 1 2 3 +EAsW(F1
重量 5 3 2 1 @ ZwvBH
价值 4 4 3 1 =wHVsdNCN
Zq|I,l0+E
并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 FQ2
a
%'the
按上述算法编写函数和程序如下: _AYK435>N
【程序】 TJpD{p}
# include <stdio.h> Xy&A~F
# define N 100 %~JJ. &
double limitW,totV,maxV; +L|?~p`V
int option[N],cop[N]; /y#f3r+*2
struct { double weight; [f-?ymmT
double value; mpEK (p
}a[N]; Sh~dwxp*"
int n; }6}l7x
void find(int i,double tw,double tv) #$+*;
{ int k; } FlT%>Gw
/*考虑物品i包含在当前方案中的可能性*/ p8H'{f\G
if (tw+a.weight<=limitW) -.@r#d/
{ cop=1; @* jz
o
if (i<n-1) find(i+1,tw+a.weight,tv); e&F8m%t
else He/8=$c%
{ for (k=0;k<n;k++) qu6D 5t
option[k]=cop[k]; 7qLpZ/
maxv=tv; C12Fl
} %2/EaaR
cop=0; qIE9$7*X
} V/LLaZTE
/*考虑物品i不包含在当前方案中的可能性*/ [M}{G5U.
if (tv-a.value>maxV) '8.r-`l(
if (i<n-1) find(i+1,tw,tv-a.value); qQ/^@3tXL
else #7$
H
{ for (k=0;k<n;k++) /-qNh>v4
option[k]=cop[k]; :&rt)/I
maxv=tv-a.value; H8zK$!
} \*y-g@-{W$
} V-2(?auZd
|t&>5HM
void main() S_4?K)n #
{ int k; =^f<v_L
double w,v; FZ<gpIv!NS
printf(“输入物品种数\n”); UiP"Ixg6
scanf((“%d”,&n); o.g V4%
printf(“输入各物品的重量和价值\n”); GL0L!="!
for (totv=0.0,k=0;k<n;k++) n)e
6>R;
{ scanf(“%1f%1f”,&w,&v); Y%aCMP9j~9
a[k].weight=w; l^-];|Y
a[k].value=v; YQ)kRhFA
totV+=V; >d*@_kJM
} !bx;Ta.
printf(“输入限制重量\n”); e8!5I,I
scanf(“%1f”,&limitV); 8oseYH
maxv=0.0; rjAn@!|:+
for (k=0;k<n;k++) cop[k]=0; T#Z^s~7&I
find(0,0.0,totV); o5O#vW2Il&
for (k=0;k<n;k++) I)6+6pm
if (option[k]) printf(“%4d”,k+1); 9dLV96
printf(“\n总价值为%.2f\n”,maxv); "1*:JVG
} o]_dJB
作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。 q=m'^
,gPS
【程序】 oj<gD
# include <stdio.h> ]t,BMu=%
# define N 100 beGa#JH,
double limitW; Rz/gtEP
int cop[N]; P [ck84F/
struct ele { double weight; P{jbl!UD7
double value; E \EsWb
} a[N]; ~.nmI&3
int k,n; ~2N"#b&J
struct { int flg; _pG-qK
double tw; qLG&WB
double tv; 4G0m\[Du
}twv[N]; V>LwqS~`
void next(int i,double tw,double tv) .},'~NM]
{ twv.flg=1; 'n]w"]|
twv.tw=tw; jo@6?(
*4
twv.tv=tv; F6|]4H.3Q
} $dC?Tl|B0
double find(struct ele *a,int n) EU;9*W<
{ int i,k,f; QXFo1m
double maxv,tw,tv,totv; 1{.|+S Z!
maxv=0; `?@}>.
for (totv=0.0,k=0;k<n;k++) u@M,qo`
totv+=a[k].value; k FD;i
next(0,0.0,totv); )[IC?U:5I
i=0; <w9JRpFY
While (i>=0) XJ\DVZ
{ f=twv.flg; ncdKj}
tw=twv.tw; (OL4Ex' ]
tv=twv.tv; T2W eE@o
switch(f) g2ixx+`?|:
{ case 1: twv.flg++; lU\[aNs
if (tw+a.weight<=limitW) ]^7@}Ce_
if (i<n-1) h"Q8b}$^)
{ next(i+1,tw+a.weight,tv); iC~^)-~H=w
i++; 9T9!kb
} 5PJhEB
else }C?'BRX
{ maxv=tv; 4f@rv^f(X
for (k=0;k<n;k++) WDD%Q8ejV&
cop[k]=twv[k].flg!=0; 2- h{N
} qgHWUwr+n
break; AKfDXy
case 0: i--; ((;!<5-`s
break; Eyqa?$R
default: twv.flg=0; %OCb:s
if (tv-a.value>maxv) eJ-xsH*8
if (i<n-1) p)-^;=<B3
{ next(i+1,tw,tv-a.value); ,^< R{{{-A
i++; &h)yro
} 6;d*r$0Fc
else FVbb2Y?R
{ maxv=tv-a.value; Lg.gfny[(t
for (k=0;k<n;k++) s^9Voi.y
cop[k]=twv[k].flg!=0; Y\P8v
} I;(L%TT `
break; BwpqNQN
} MKk\
u9
} B dfwa
return maxv; xm~`7~nFR
} {\1?ZrCI&
\?-<4Bc@
void main() JFmC\
{ double maxv; pYEMmZ?L
printf(“输入物品种数\n”); |syR6(U}
scanf((“%d”,&n); .`H5cuF`
printf(“输入限制重量\n”); lrE5^;/s1
scanf(“%1f”,&limitW); ? :%@vM
printf(“输入各物品的重量和价值\n”); Of#u
for (k=0;k<n;k++) +TL%-On
scanf(“%1f%1f”,&a[k].weight,&a[k].value); pah'>dAL
maxv=find(a,n); t!l&iVWs
printf(“\n选中的物品为\n”); ^[`%&uj!g
for (k=0;k<n;k++) |YWD8 +
if (option[k]) printf(“%4d”,k+1); i1d'nxk6
printf(“\n总价值为%.2f\n”,maxv); EME|k{W
}