首页计算机计算机基础计算机算法设计与分析 02 第3章 递归.pptx

02 第3章 递归.pptx

页数:45页文件大小:187.0 KB来源: 计算机算法设计与分析ppt课件

本课件讲解递归算法,先说明递归的定义与子程序调用、栈式现场保存等实现机制,再给出递归算法设计的一般形式与适用条件,并以Hanoi问题、棋子移动、0/1背包、全排列、自然数拆分五个典型问题演示递归求解思路,最后介绍递归关系式的计算与k阶线性齐次递归方程的解法。

第三章递归章节封面,标示本章主题为递归算法的实现机制与设计方法
第三章目录页,列出递归实现机制、递归转非递归、递归算法设计与递归关系式计算四节
递归定义讲解页,说明过程直接或间接调用自身即为递归并指出递归思路清晰但效率较低
查看本课件的文字版(共 45 页,供检索与复制)

第1页:第三章 递归章节封面

第三章递归

第2页:第三章目录

3.1递归算法实现机制3.2递归转非递归3.3递归算法设计3.4递归关系式的计算

第3页:递归的定义与意义

递归

  • 定义一个过程直接地或间接地调用自己,则称这个过程是递归的过程。
  • 递归算法在计算机理论和实际应用中都具有重要意义。
  • 设计和分析思路清晰,实现容易,但效率较低。

第4页:子程序调用的实现机制

3.1递归算法的实现机制主程序Call A1:子程序A主程序Call A2:子程序ACall A1:

第5页:嵌套调用与返回

子程序调用的实现机制Call B2:子程序ACall A1:主程序子程序BCall A2:子程序ACall B1:主程序子程序B

第6页:递归求阶乘算法

proceduref( integer n) integer y; if (n=0) return 1y←f(n−1); return(n×y); end f递归求阶乘的算法主程序: integer fn;fn←f(4);

第7页:递归调用的栈实现

为了保证递归调用的正确性,需要保存调用点的现场(返回地址、局部变量、被调用函数的参数等),以便正确地返回,并且按先进后出的原则来管理这些信息。

高级语言编译程序是利用栈来实现的。

f(n) f(n-1) f(n-2) f(1) f(0)…调用返回调用点PnPn-1Pn-2P11调用时执行入栈操作保存现场,返回时执行出栈操作恢复现场.

第8页:4!递归调用与返回过程

计算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)

第9页:递归章节结构回顾

3.1递归算法实现机制3.2递归转非递归3.3递归算法设计3.4递归关系式的计算

第10页:递归求解问题的条件

3.3递归算法设计可以用递归求解的问题应满足

  • 问题的描述涉及规模
  • 规模发生变化后,问题的性质不变
  • 问题的解决有出口

第11页:递归算法的一般形式

递归算法的一般形式Procedure P(参数表)if递归出口 then简单操作 else简单操作; call P;简单操作 endif end P规模或与规模相关的参数降低规模的处理对递归结果的处理

第12页:递归设计的典型问题

几个典型问题

  • Hanoi问题
  • 棋子的移动问题
  • 简单的0/1背包问题
  • n个元素的全排列
  • 自然数拆分(正整数拆分)

第13页:n阶Hanoi问题描述

n阶Hanoi问题

  • X,Y,Z是三个塔座,开始时有n个盘子依其半径大小套在柱子X上,其中半径大的在下面。现要将X上的圆盘移到Z上,并仍按同样顺序叠置。
  • 移动规则:1:每次只能移动1个圆盘;2:任何时刻都不允许将半径大的圆盘压在半径小的圆盘之上;

第14页:Hanoi问题n=1与n=2

n阶Hanoi问题

  • Hanoi(n,X,Y,Z)
  • n=1, X→Z
  • n=2,X→Y,X→Z,Y→Z,11XYZXYZ21

第15页:Hanoi问题n=3

n阶Hanoi问题

  • Hanoi(n,X,Y,Z)
  • n=3, Hanoi(2,X,Z,Y)X→ZHanoi(2,Y,X,Z)3XYZ

第16页: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

第17页:棋子移动问题描述

棋子的移动问题有2n个棋子(n≥4)排成一行,白子用0表示,黑子用1表示,例如n=5时初始状态为0000011111__(后面至少有两个空位),要求通过棋子移动最终成为0 1 0 1 0 1 0 1 0 1.移动规则:1.每次同时移动相邻两个棋子,颜色不限,移动方向不限,2.每次移动必须跳过若干棋子,3.不能调换两个棋子的位置。

第18页:棋子移动n=4示例

棋子的移动问题n=4时00001111__①000__11101②0001011__1③0__1011001④010101__01⑤__01010101

第19页:棋子移动n=5与n=6

棋子的移动问题n=5时0000011111__0000__11110100001111__01n=6时000000111111__00000__11111010000011111__01

第20页:棋子移动递归思路

棋子的移动问题递归出口: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)简单操作降低问题规模

第21页:棋子移动递归算法

棋子的移动问题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)

第22页:0/1背包问题描述

简单的0/1背包问题背包可容纳物品的最大质量为m,现有n件物品,质量分别为m1,m2,…mn,mi均为正整数,要从n件物品中挑选若干件,使放入背包的质量之和正好为m.

第23页:0/1背包问题示例

简单的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件物品要么取,要么舍,不能取一部分,因此这个问题可能有解,也可能无解。

布尔函数

第24页:0/1背包问题分析

问题分析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

第25页:0/1背包knap算法

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

第26页:全排列问题描述

求n个元素的全排列

  • 设A={a1,a2,…,an}是要进行排列的n个元素的集合,
  • n=1 a1
  • n=2 a1a2a2a1
  • n=3 a1a2a3a1a3a2a2a1a3a2a3a1a3a1a2a3a2a1

第27页:全排列递归思路

求n个元素的全排列

  • range(A)= a1range(A1),a2range(A2),…,anrange(An)集合A用数组实现range(a,1,n):递归出口:range(a,n,n)递归调用:使得集合所有的元素都可以作为前缀出现A-a1A-a2A-an

第28页:全排列递归算法

求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)

第29页:自然数拆分问题

自然数拆分(正整数拆分)

  • 任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和,试求n的所有拆分。
  • n=2 2=1+1
  • n=3 3=1+2=1+1+1
  • n=4 4=1+3=1+1+2=1+1+1+1=2+2

第30页:n=6的自然数拆分

自然数拆分(正整数拆分)

  • n=6 6=1+5=1+1+4=1+1+1+3=1+1+1+1+2=1+1+1+1+1+1=1+1+2+2=1+2+3=2+4=2+2+2=3+3

第31页:自然数拆分要点

自然数拆分(正整数拆分)

  • 拆分的结果用一维数组A保存;
  • 对任意自然数的所有拆分方式,依据A(1)的值,可以分为⌊n/2⌋类;
  • 为保证拆分不重复,A中元素是非降的;
  • 下一次的拆分,用A的下标来控制,而不是A中的元素值;
  • 发生下一次拆分(递归调用)的判断条件

第32页:自然数拆分算法

自然数拆分(正整数拆分)算法 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输出已产生的一种拆分本次拆分的起始位置本次拆分的数值

第33页:3.4 递归关系式的计算

3.4递归关系式的计算递归算法的时间复杂度分析K阶线性齐次递归关系式的解法

第34页:求最大元的二分递归

递归算法的时间复杂度分析

  • 求n个元素的最大元问题二分法Max(A,1,n)A(1)A(2)……A(⌊n/2⌋) A(⌊n/2⌋+1) …A(n)Max(A,1,⌊n/2⌋)Max(A,⌊n/2⌋+1,n)max

第35页:求最大元MAX过程

求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

第36页:求最大元的时间复杂性

时间复杂性

第37页:台阶问题与算法

台阶问题 一个楼有n个台阶,有一个人上楼时有时一次跨一个台阶,有时跨两个台阶,写算法,计算此人有几种不同的上楼方法,并分析算法的时间复杂度。 procedure H(n) if n≤2 then H←n elseH←H(n−1)+H(n−2) endif end H

第38页:台阶问题的时间复杂性

时间复杂性

第39页:k阶线性齐次递归关系式

k阶线性齐次递归关系式的解法

  • 定义3.1递归关系式其中,ck≠0, ci+1, bi是给定常数,称为k阶线性常系数递归关系式。当d(n)=0时,称此递归关系式是齐次的。

第40页:一阶线性齐次递归关系式

一阶线性齐次递归关系式

  • 逐步递推的方法

第41页:母函数求解思路

二阶线性齐次递归关系式

  • 利用母函数这是一个有广泛适用性的方法。它不仅可以用来求解线性常系数高阶齐次和非齐次的递归方程,而且可以用来求解线性变系数高阶齐次和非齐次的递归方程,甚至可以用来求解非线性递归方程。基本思想是设定递归方程解的母函数,努力建立一个关于母函数的可解方程,将其解出,然后返回递归方程的解。

第42页:二阶特征方程与实根解

二阶线性齐次递归关系式

  • 得到特征方程x2+bx+c=0
  • 根据特征根r1和r2,解递归关系式
  • r1和r2为互不相同的实数时,

第43页:二阶共轭复根的解

二阶线性齐次递归关系式

  • r1≠r2,但r1和r2为是一对共轭复根时,

第44页:二阶重根的解

二阶线性齐次递归关系式

  • r1=r2时,

第45页:本章小结

45小结

  • 递归算法的定义、实现机制
  • 递归算法设计要点
  • 递归算法时间复杂性分析
顶部目录