算法设计与分析递归课件.ppt

《算法设计与分析递归课件.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析递归课件.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第3章 递 归递归调用的内部实现原理递归程序的阅读递归转非递归递归算法的设计解递归方程递归的定义递归的定义在定义一个过程或函数时出现调用本过程或本函在定义一个过程或函数时出现调用本过程或本函数的成分数的成分, ,称之为称之为递归递归。若调用自身。若调用自身, ,称之为称之为直接递直接递归归。若过程或函数。若过程或函数p p调用过程或函数调用过程或函数q,q,而而q q又调用又调用p,p,称之为称之为间接递归间接递归。 3.1 递归调用的内部实现原理图3.1 子程序调用的几种形式(1)两次值传送方式按指定类型为变参设置相应的存储空间，在执行调用时，将实参值传送给变参，在返回时将变参的值回传实参。

2、(2)地址传送方式在内部将变参设置成一个地址，调用时首先执行地址传送，将实参的地址传送给变参，在子程序执行过程中，对变参的操作实际上变成所对应的实参的操作。值的回传在执行调用时，系统至少执行如下操作：a.返回地址进栈，同时在栈顶为被调子程序的局部变量开辟空间；b.为被调子程序准备数据：计算实参值，并赋给对应的栈顶的形参；c.将指令流转入被调子程序的入口处；在执行返回操作时，系统至少执行如下操作：a.若有变参或是函数，将其值保存到回传变量中；b.从栈顶取出返回地址；c.按返回地址返回；d.若有变参或是函数，从回传变量中取出保存的值传送给相应的变量或位置上。子程序调用的内部实现3.2.1 模拟系统

3、栈方式例3.1 求m，n(mn)的最大公因子的递归过程。procedure GCD(m，nint；var hint) begin1if n=02 then begin hm； write(h)； end3else call GCD(n，m mod n，h)；4endp；3.2 递归程序的阅读call GCD(28，6，X)执行过程指令流方式GCD(100，18，x)执行write(x)的运行过程，指令流方式指令流方式例3.3 对下面的递归过程，写出调用P(3)的运行结果。procedure P(wint)；begin if w0 then begin call P(w-1)； write(w)

4、； call P(w-1)； end；endp；递归算法的程序设计存在两个问题：并不是所有语言都支持递归；递归程序比非递归程序要花费更多的时间，当递归层数太多时，会出现栈溢出。3.3 递归转非递归系统自动地为递归设置了一个栈，因此，在等价的非递归程序中，需要设置栈S，初始为空调用的c操作是将程序的执行流程转入到子程序的入口处，所以等价程序中，用无条件的转移语句实现，并在入口处设置一个标号L0。对程序中的每个递归调用，用以下几个等价操作替换：a.保留现场：开辟栈顶存储空间，用于保存返回地址(不妨用Li，i=1，2，)和调用层的形参和局部变量的值(最外层调用不必考虑)； 递归转非递归方法b.准备数

5、据：为被调子程序准备数据，计算实参值，并赋给对应的形参；c.执行goto L0；d.在返回处设一个标号Li(i=1，2，3，)，并根据需要设置以下语句：若有变参或是函数，从回传变量中取出所保存的值，并传送到相应的实参或位置。对返回语句，如果栈不空，则依次执行如下操作，否则结束本子程序，返回。a.回传数据：若有变参或是函数，将其值保存到回传变量中；b.恢复现场：从栈顶取出返址(不妨设保存到X中)及各变量、形参的值，并退栈；c.返回，执行goto X；d.对其中的非递归调用和返回操作可照搬。例3.4 将下面的递归程序转化成等价的非递归程序。procedure P(wint)；begin if w0

6、 then begin call P(w-1)； write(w)； end；endp；解 按转化规则可得 procedure P1(wint)； begin init(S)；l0 if w0 then begin push(S，w，l1)； ww-1 goto l0；l1 write(w)； end； if not empty(S) then begin pop(S，w，X)； goto X； end； endp；简化规则1 如果递归程序中只有一次递归调用，则在转换时，返回地址不入栈。 图3.4 例3.4的流程图procedure P1(wint)；begin init(S)； while

7、w0 do begin push(S，w)； ww-1； end；while not empty(S) do begin pop(S，w)； write(w)； end；endp； 修改后的程序例3.5 将下面递归程序改为等价的非递归程序。procedure P(wint)；begin if w0 then begin write(w)； call P(w-1)； end；endp；procedure P1(wint)；begin init(S)；l0 if w0 then begin write(w)； push(S，w)； ww-1； goto l0；l1 end； if not empt

8、y(s) then begin pop(S，w)； goto l1； end；endp；简化规则2 在尾递归调用时，不必执行入栈操作。注意：如果有变参或是函数，则在返回后还要执行赋值操作，所以不能算尾递归。图3.5 例3.5流程图procedure P1(wint)；beginl0if w0 then begin write(w); ww-1; goto l0 end;endp; 修改后的程序例3.6 将例3.1转换成等价的非递归程序。 procedure GCD(m,nint;var hint); var temp,backvarint; begin init(S);l0if n=0 the

9、n begin hm; write(h); end else begin push(S,m,n,h); temp m; m n; n temp mod n; goto l0;l1h backvar; end; if not empty(S) then begin backvar h; pop(S,m,n,h); goto l1; end;endp;图3.6 例3.6的流程图 procedure GCD(m,nint;var hint); var temp,backvar int; begin init(S); while n0 do begin push(S,m,n,h); temp m; m

10、 n; n temp mod n; end; h m;write(h);while not empty(S) do begin backvar h; pop(S,m,n,h); h backvar; end;endp; 修改后的程序适宜于用递归算法求解的问题的适宜于用递归算法求解的问题的充分必要条件是：充分必要条件是：问题 P 的描述涉及规模，即 P(size)；规模发生变化后，问题的性质不发生变问题的解决有出口。 表现形式procedure P(参数表)；begin if 递归出口 then 简单操作 else begin 简单操作；call P; 简单操作 end;endp;3.4 递归算

11、法的设计例3.7 简单的0/1背包问题。设一背包可容物品的最大质量为m，现有n个物品，质量为(w1,w2,wn)，wi均为正整数，从n件物品中挑选若干件，使放入背包的质量之和正好为m。例3.9 棋子移动。有 2n 个棋子(n4)排成一行，白子用0代表，黑子用1代表，n =5的初始状态为：0 0 0 0 0 1 1 1 1 1 _ _(右边至少有两个空位)移动规则是每次必须同时移动相邻两个棋子，颜色不限，移动方向不限，每次移动必须跳过若干棋子，不能调换两个棋子的位置，最后成为：0 1 0 1 0 1 0 1 0 1下面用不完全归纳法找出口和递推关系。n=4 0 0 0 0 1 1 1 1_ _

12、第一步 0 0 0 _ _ 1 1 1 0 1 (4,5)(9,10)第二步 0 0 0 1 0 1 1 _ _ 1 (8,9) (4,5) 第三步 0 _ _ 1 0 1 1 0 0 1 (2,3) (8,9)第四步 0 1 0 1 0 1 _ _ 0 1 (7,8) (2,3)第五步 _ _ 0 1 0 1 0 1 0 1 (1,2) (7,8) n=5 0 0 0 0 0 1 1 1 1 1 _ _第一步 0 0 0 0 _ _ 1 1 1 1 0 1 (5,6) (11,12)第二步 0 0 0 0 1 1 1 1 _ _ 0 1 (9,10)(5,6) 这时前 8 枚棋子是 n =4

13、的情况，移法如 n =4的第一步到第五步即可完成 n =5时的移子。n=6 0 0 0 0 0 0 1 1 1 1 1 1 _ _第一步 0 0 0 0 0 _ _ 1 1 1 1 1 0 1 (6,7)(13,14)第二步 0 0 0 0 0 1 1 1 1 1 _ _ 0 1 (11,12)(6,7) 前 10 枚棋子为 n =5的情况。由此归纳出：n =4时是递归的出口，在退出时作5个移动操作：move (4,5) (9,10)move (8,9) (4,5)move (2,3) (8,9)move (7,8) (2,3)move (1,2) (7,8)如果 2n 个棋子的移动用 che

14、ss( n )表示，则递推关系是：Move (n,n+1) (2n+1,2n+2);move (2n-1,2n) (n,n+1);call chess(n-1);例3.10 求 n 个元素的全排列。分析： n =1输出：a1;n =2输出：a1 a2 a2 a1;n =3输出： a1 a2 a3 a1 a3 a2 a2 a1 a3 a2 a3 a1 a3 a1 a2 a3 a1 a2分析 n =3，全部排列分成三类： a1 类： a1 之后跟a2 ， a3 的所有全排列。 a2 类： a2 之后跟a1 ， a3 的所有全排列。 a3 类： a3 之后跟a2 ， a1 的所有全排列。将中a1 ，

15、 a2 的互换位置，得到；将中a1 ， a3 的互换位置，得到。它说明可以用循环的方式重复执行交换位置，后面跟随剩余序列的所有排列，对剩余序列再使用这个方法，这就是递归调用，当后跟的元素没有时就得到递归的边界。例3.11 自然数拆分。任何一个大于1的自然数 n，总可以拆分成若干个小于 n 的自然数之和，试求 n 的所有拆分。n =2 可拆分成 2=1+1n =3 可拆分成 3=1+2= 1+1+1n =4 可拆分成 4=1+3= 1+1+2= 1+1+1+1= 2+2 n =7 可拆分成 7=1+6= 1+1+5= 1+1+1+4= 1+1+1+1+3= 1+1+1+1+1+2= 1+1+1+

16、1+1+1+1= 1+1+1+2+2= 1+1+2+3= 1+2+4= 1+2+2+2= 1+3+3= 2+5= 2+2+3= 3+4递推法公式解法解递归方程39对于某些递归关系，可以通过逐次递推求得递归方程的解。例1.4 Hanoi塔问题1.3.1 递推法40Hanoi塔问题的递归算法的时间复杂性，由下面递归方程给出：41所以，Hanoi塔问题的递归算法的时间复杂性为T(n)=O(2n)。将3个盘子从A座移到C座需要移7次，如果将64个盘子从A座移到C座需要移多少时间？需要移18446744073709551615次，假设和尚每次移动1个盘子用1秒钟，则移动84467440737095516

17、15次需要18446744073709551615秒，大约相当于610 e11年，即大约600亿年，所以有人戏称，当老和尚移完64个盘子之时，“世界末日”也到了。42例1.5 第6章介绍分治法。这里举一个分治法的例子。设n表示问题的尺寸，n/b表示将这个问题分成a个子问题后，每个子问题的尺寸，其中a，b为常数。d(n)表示在分解或合成子问题而得到整个问题解决时的时间耗费。则整个问题的时间耗费由下面递归方程给出，求解递归方程。43MasterMaster定理定理 )()(),()/(1,0),()(.3)log()(),()(.2)()(,0),()(1.)(),()/()()(1,1loglo

18、glogloglognfnTncfbnafncnnfnnnTnnfnnTnOnfnTnfbnaTnTnfbaaaaaabbbbb 那那么么有有和和所所有有的的充充分分大大的的且且对对于于某某个个常常数数那那么么那那么么为为非非负负整整数数为为函函数数为为常常数数，设设 44例例1 1 nnTnT )3/(9)()()(),()(,)(, 3, 9219log29log33nnTnOnfnnnnfba 例例2 21)3/2()( nTnT)log()(),()(, 1, 1)(, 2/3, 11log01log2/32/3nnTnnfnnnfba 例例3 3nnnTnTlog)4/(3)( )l

19、og()(, 4/3),(log)4/3()4/log()4/( 3)/(, 2 . 0),()(),(,log)(, 4, 33log793. 03log44nnnTncncfnnnnbnafnnfnOnnnnfba 充充分分大大 451. 1. 常系数线性齐次递推方程的求解常系数线性齐次递推方程的求解 标准形式：标准形式：k k阶阶0,.,0)()2()1()(2121 kkkaaaaknknHanHanHanH是是常常数数，求解步骤：求解步骤： （1）求出特征方程）求出特征方程 的的k k个个根根（2）如果没有重根，则该递推方程的通解为）如果没有重根，则该递推方程的通解为0.11 kkk

20、axax 待待定定常常数数knkknnCCCqCqCqCnH,.,.)(212211 如果有重根，如果如果有重根，如果q q是是e e重特征根，通解对应于根重特征根，通解对应于根q q的部分为的部分为neeqnCnCC).(121 整个通解为各个不等的特征根的对应部分之和整个通解为各个不等的特征根的对应部分之和 （3 3）代入初值确定待定常数。）代入初值确定待定常数。46例例6 Fibonacci6 Fibonacci数列数列 1, 11021 fffffnnn 解：解：x x2 2-x-1 =0 -x-1 =0 的根为的根为 251,251 ，递推方程的通解为递推方程的通解为 nnnCCf

21、25125121带入初值带入初值 得得 125125112121CCCC解得解得 25151,2515121 CC 112515125151 nnnf47例例7 H(n)+H(n-1)-3H(n-2)-5H(n-3)-2H(n-4) = 07 H(n)+H(n-1)-3H(n-2)-5H(n-3)-2H(n-4) = 0 H(0) = 1, H(1) = 0, H(2) = 1, H(3) = 2 H(0) = 1, H(1) = 0, H(2) = 1, H(3) = 2 特征方程特征方程 x x4 4+x+x3 3-3x-3x2 2-5x-2 = 0 , -5x-2 = 0 , 特征根特征

22、根-1-1，-1-1，-1-1，2 2，通解为通解为 289314420212)1)()(4321432143214142321CCCCCCCCCCCCCCCnCnCCnHnn解得解得 92, 0,31,974321 CCCC解为解为 nnnnnH292)1(31)1(97)( 48 常系数线性非齐次递推方程求解常系数线性非齐次递推方程求解 标准形标准形 121021)1(.,)2(,)1(,)0()()(.)2()1()( kkdkHdHdHdHnfknHanHanHanH通解为对应的齐次通解加上特解通解为对应的齐次通解加上特解 特解的函数形式依赖于特解的函数形式依赖于f(n) f(n) 求

23、解的关键是用待定系数法确定一个特解求解的关键是用待定系数法确定一个特解H H* *(n(n）)(*)()(nHnHnH 49f(n)f(n)为为n n的的t t次多项式，一般次多项式，一般H H* *(n)(n)也为也为n n的的t t次多项式次多项式例例1 1 求求a an n +5a+5an-1n-1 +6a +6an-2n-2 = 3n = 3n2 2 的通解的通解设设 a an n* * = P = P1 1n n2 2 + P + P2 2n + Pn + P3 3 , , 代入得代入得 P P1 1n n2 2+P+P2 2n+Pn+P3 3+5P+5P1 1(n-1)(n-1)2

24、 2+P+P2 2(n-1)+P(n-1)+P3 3+6P+6P1 1(n-2)(n-2)2 2+P+P2 2(n-2)+P(n-2)+P3 3=3n=3n2 2 从而得到方程组从而得到方程组 12P12P1 1 = 3 = 3 -34P -34P1 1+ 12P+ 12P2 2 = 0 = 0 29P 29P1 1 17P 17P2 2 + 12P + 12P3 3 = 0 = 0 288115241741288115,2417,412*321 nnaPPPn 通解为通解为288115241741)3()2(221 nnCCannn50例例2 Hanoi2 Hanoi塔塔 H(n) = 2

25、H(n-1)+1 H(n) = 2 H(n-1)+1 设设 H H* *(n) = P(n) = P P = 2 P + 1 , P = -1 P = 2 P + 1 , P = -1 H(n) = A 2 H(n) = A 2n n 1 1 代入初值代入初值 H(1) = 1H(1) = 1得得 A = 1A = 1解为解为 H(n) = 2H(n) = 2n n 1 151f(n)f(n)为指数函数为指数函数 n n，特解也为指数形式，特解也为指数形式 若不是特征根，则特解为不是特征根，则特解为H H* *(n) = P(n) = P n n 若若 是是e e重特征根，则特解为重特征根，则

26、特解为PnPne e n n 例例3 H(n) +5H(n-1) +6H(n-2) = 423 H(n) +5H(n-1) +6H(n-2) = 42 4 4n n令令 H H* *(n) = P 4(n) = P 4n n , , 代入得代入得 P 4P 4n n + 5P 4 + 5P 4n-1n-1 + 6P 4 + 6P 4 n-2n-2 = 42 = 42 4 4n n 42P = 42 42P = 42 16, P =1616, P =16通解为通解为 H(n) = CH(n) = C1 1(-2)(-2)n n + C + C2 2(-3)(-3)n n + 4 + 4n+2n+

27、2 52H(n) H(n) 5H(n-1) + 6H(n-2) = 2 5H(n-1) + 6H(n-2) = 2n n 求特解求特解2 2为为1 1重根重根令令 H H* *(n) = Pn 2(n) = Pn 2n n , , 代入得代入得 Pn2Pn2n n 5 P(n-1) 2 5 P(n-1) 2n-1n-1 + 6 P(n-2) 2 + 6 P(n-2) 2n-2n-2 = 2 = 2n n 解得解得 P= -2 P= -2 H H* *(n) = -n 2(n) = -n 2n+1n+1 53作业汉诺塔问题 （1）递归方式实现 （2）非递归方式，用栈实现 （3）非递归方式，用循环

28、实现 #include using namespace std;const int MAX =1000; int aMAX,bMAX; /a 数组表示待拆分的数， b 数组表示参与拆分的数 int n;void find(int m,int start,int k)/ m 表示待拆分的数值， start 表示可拆分数的起始值 k 新拆分数所在数组下标（已拆分个数）) int i,j; for (i=start;i=m/2;i+) ak=m-i; bk=i;/ 记录下有关数据， coutn=; for (j=1;j=k;j+) coutbj+; coutakendl; find(ak,i,k+1); return ; int main() coutn;find(n,1,1); 一个整数，大于0，不用循环和本地变量，按照n,2n,4n,8n的顺序递增。当值大于5000时，把值按照指定顺序输出来。 例：n=1237 则输出为： 1237，2474，4948，9896，9896，4948，2474，1237有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？请用递归算法编程实现.