页数:45页文件大小:187.0 KB来源: 计算机算法设计与分析ppt课件
本课件讲解递归算法,先说明递归的定义与子程序调用、栈式现场保存等实现机制,再给出递归算法设计的一般形式与适用条件,并以Hanoi问题、棋子移动、0/1背包、全排列、自然数拆分五个典型问题演示递归求解思路,最后介绍递归关系式的计算与k阶线性齐次递归方程的解法。
第三章递归
3.1递归算法实现机制3.2递归转非递归3.3递归算法设计3.4递归关系式的计算
递归
3.1递归算法的实现机制主程序Call A1:子程序A主程序Call A2:子程序ACall A1:
子程序调用的实现机制Call B2:子程序ACall A1:主程序子程序BCall A2:子程序ACall B1:主程序子程序B
proceduref( integer n) integer y; if (n=0) return 1y←f(n−1); return(n×y); end f递归求阶乘的算法主程序: integer fn;fn←f(4);
为了保证递归调用的正确性,需要保存调用点的现场(返回地址、局部变量、被调用函数的参数等),以便正确地返回,并且按先进后出的原则来管理这些信息。
高级语言编译程序是利用栈来实现的。
f(n) f(n-1) f(n-2) f(1) f(0)…调用返回调用点PnPn-1Pn-2P11调用时执行入栈操作保存现场,返回时执行出栈操作恢复现场.
计算4 !递归过程图示:下图中Pi代表现场信息,栈元素由现场信息和参数构成f(4)=4*f(3) f(3)=3*f(2) f(2)=2*f(1) f(1)=1*f(0) f(0)=1Push(e4) Push(e3) Push(e2) Push(e1)f(4)= 4 * f(3) f(3) = 3 *f(2) f(2)= 2 *f(1) f(1)= 1 * f(0)=24= 6= 2=1P44P33P44P22P33P44P11P22P33P44Pop(e1)Pop(e2)Pop(e3)Pop(e4)
3.1递归算法实现机制3.2递归转非递归3.3递归算法设计3.4递归关系式的计算
3.3递归算法设计可以用递归求解的问题应满足
递归算法的一般形式Procedure P(参数表)if递归出口 then简单操作 else简单操作; call P;简单操作 endif end P规模或与规模相关的参数降低规模的处理对递归结果的处理
几个典型问题
n阶Hanoi问题
n阶Hanoi问题
n阶Hanoi问题
n阶Hanoi问题 procedure Hanoi(n, X, Y, Z) if (n=1) then move(X,Z) elseHanoi(n−1, X, Z, Y)move(X,Z)Hanoi(n−1, Y, X, Z) endifEnd Hanoi
棋子的移动问题有2n个棋子(n≥4)排成一行,白子用0表示,黑子用1表示,例如n=5时初始状态为0000011111__(后面至少有两个空位),要求通过棋子移动最终成为0 1 0 1 0 1 0 1 0 1.移动规则:1.每次同时移动相邻两个棋子,颜色不限,移动方向不限,2.每次移动必须跳过若干棋子,3.不能调换两个棋子的位置。
棋子的移动问题n=4时00001111__①000__11101②0001011__1③0__1011001④010101__01⑤__01010101
棋子的移动问题n=5时0000011111__0000__11110100001111__01n=6时000000111111__00000__11111010000011111__01
棋子的移动问题递归出口:n=4move(4,5)→(9,10)000__11101move (8,9) →(4,5) 0 0 01 01 1 _ _ 1move (2,3) →(8,9) 0 _ _ 1 0 1 10 01move (7,8) →(2,3) 01 01 0 1 _ _ 0 1move (1,2) →(7,8) _ _ 01 0 10 10 12n个棋子的移动:chess(n)move (n,n+1) →(2n+1,2n+2)move (2n-1,2n) →(n,n+1)callchess(n-1)简单操作降低问题规模
棋子的移动问题Procedure Chess(n)ifn=4 thenmove (4,5)→(9,10)move (8,9)→(4,5)move (2,3)→(8,9)move (7,8)→(2,3)move (1,2)→(7,8) elsemove (n,n+1)→(2n+1,2n+2)move (2n−1,2n)→(n,n+1) callChess(n-1) endifEnd Chess递归出口递归调用A(9)←A(4)A(10)←A(5)
简单的0/1背包问题背包可容纳物品的最大质量为m,现有n件物品,质量分别为m1,m2,…mn,mi均为正整数,要从n件物品中挑选若干件,使放入背包的质量之和正好为m.
简单的0/1背包问题例:m=20, n=5, (m1,m2,m3,m4,m5)=(3,5,8,9,10)(x1,x2,x3,x4,x5)=(1,0,1,1,0)m=18?m=28?注:对于第i件物品要么取,要么舍,不能取一部分,因此这个问题可能有解,也可能无解。
布尔函数
问题分析knap(m,n)m初始:…….m1m2…… mn−1mnm…….m1m2…… mn−1mn=mtruemn<mm…….m1m2…… mn−1n>1,即还有可选物品knap(m−mn,n−1)knap(m,n)←knap(m,n−1)knap(m,n)←knap(m−mn,n−1)有解无解mn>mm…….m1m2…… mn−1n>1knap(m,n−1)否则false
function knap(m,n) case:m−mn=0:knap←true:m−mn>0:ifn>1 thenifknap(m−mn,n−1)=true thenknap←true else knap←knap(m,n−1) endif elseknap←false endif:m−mn<0: if n>1 then knap←knap(m,n−1) elseknap←false; endif end caseEnd knap
求n个元素的全排列
求n个元素的全排列
求n个元素的全排列 procedure range(A,k,n)ifk=n then print(A) else for i←k to n doA(k)↔A(i) call range(A,k+1,n)A(k)↔A(i) repeat endif end rangeRange(A,1,n)
自然数拆分(正整数拆分)
自然数拆分(正整数拆分)
自然数拆分(正整数拆分)
自然数拆分(正整数拆分)算法 procedure split(t) for k←1 totdowrite(A(k)) ; repeatj←t; L←A(j) for i←A(j−1)toL/2doA(j)←i; A(j+1)←L−i ; call split(t+1) repeat end split procedure main(n) for i←1 ton/2doA(1)←i; A(2)←n−i; call split(2) repeat end main输出已产生的一种拆分本次拆分的起始位置本次拆分的数值
3.4递归关系式的计算递归算法的时间复杂度分析K阶线性齐次递归关系式的解法
递归算法的时间复杂度分析
求n个元素的最大元问题Procedure MAX (A,i, j)ifi=j then returnA(i) endififj−i=1 then if A(i)>A(j) then returnA(i) else returnA(j) ; endif else k←⌊(i+j)/2⌋m1←MAX(i,k)m2←MAX(k+1,j) if m1>m2 then returnm1 else returnm2; endif endif end MAX
时间复杂性
台阶问题 一个楼有n个台阶,有一个人上楼时有时一次跨一个台阶,有时跨两个台阶,写算法,计算此人有几种不同的上楼方法,并分析算法的时间复杂度。 procedure H(n) if n≤2 then H←n elseH←H(n−1)+H(n−2) endif end H
时间复杂性
k阶线性齐次递归关系式的解法
一阶线性齐次递归关系式
二阶线性齐次递归关系式
二阶线性齐次递归关系式
二阶线性齐次递归关系式
二阶线性齐次递归关系式
45小结
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}