递归与分治ppt课件.ppt

《递归与分治ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章递归与分治2021/7/271计算机算法设计与分析递归的概念简单地说，递归就是用自己来定义自己。一般地说，一个递归过程P可以表示为基语句S(不含P)和P自身的组合β：Pβ(S,P)这样的表示包含了过程不终止的可能，因此递归算法应更准确地表述为PifBthenQelseβ(S,P)其中Q也不包含P，B为递归终止条件。2021/7/272计算机算法设计与分析递归元递归算法的思想是将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。这种规模的变化就体现在递归算法的变元中的一类(一个或几个)变元上，这类变元被称之为递归元。递归元的变化是在递归定义中确定的，它的变化应能导致递归算法

2、的终止。在递归算法的设计中递归元是非常重要的。2021/7/273计算机算法设计与分析Hanoi塔问题例1：Hanoi塔问题：有A、B、C三根柱子。A上有n个圆盘，自下而上由大到小地叠在一起。ABC现要将A上的全部圆盘移到B上，并要求：(1)每次只能移动一个圆盘；(2)任何时刻都不允许将较大的圆盘压在较小的圆盘上；(3)圆盘只能在A、B、C三个柱子间移动。Hanoi塔的解可以很自然地看成这样一个过程：(1)先将A上面n–1个盘移至C。(2)再将A上剩下的1个盘移至B。(3)最后将C上的n–1个盘移至B。于是可得到如下的程序：voidHanoi(intn,intFr,intTo,intAs){

3、if(n>0){Hanoi(n–1,Fro,Ass,To);Move(Fro,To);Hanoi(n–1,Ass,To,Fro)}}2021/7/274计算机算法设计与分析Hanoi塔问题的时间复杂性Hanoi塔问题的时间复杂性为O(2n)。证明：对n归纳证明移动次数move(n)=2n–1。归纳基础：当n=1，move(1)=1=21–1。归纳假设：当nk，move(n)=2n–1。归纳步骤：当n=k+1，移动次数为move(k+1)=2(move(k))+1=2(2k–1)+1=2k+1–1由归纳法可知对任意的n有move(n)=2n–12021/7/275计算机算法设计与分析常见的递

4、归形式多变元递归；多步递归；嵌套递归；联立递归除基本的递归形式外，其它常见的递归形式有四种，它们是：2021/7/276计算机算法设计与分析多变元递归多变元递归就是递归元多于一个的递归。例2：整数划分问题：将一个正整数n表示为一系列正整数之和，n=n1+n2+…+nk其中n1≥n2≥…≥nk≥1,k≥1。正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分的个数成为正整数n的划分数，记作ρ(n)。例如ρ(6)=11，即整数6的划分数为11种：6,5+1,4+2,4+1+1,3+3,3+2+1,3+1+1+12+2+2,2+2+1+1,2+1+1+1+1，1+1+1+1+1+12

5、021/7/277计算机算法设计与分析正整数的划分在正整数的所有不同划分中，将最大加数n1不大于m的划分个数记为q(n,m)，可以建立如下的递归关系：最简单情形：(1)q(n,1)=1,q(1,m)=1n,m≥1;递归关系：(2)q(n,n)=1+q(n,n–1)，n＞1;产生的新情况：(3)q(n,m)=q(n,m–1)+q(n–m,m),n＞m＞1(4)q(n,m)=q(n,n),n＜m。1n=1或m=1q(n,m)=1+q(n,n–1)n≤mq(n,m–1)+q(n–m,m)n＞m＞1的二元递归函数：q(n,m){if(n<1)

6、

7、(m<1)return0;if(n==1)

8、

9、(m==

10、1)return1;if(n==1)

11、

12、(n1Fibonacci函数是一个两步的递归函数。2021/7/279计算机算法设计与分析嵌套递归所谓嵌套递归是指递归调用中又含有递归调用，又称为多重递归。例如A

13、ckermann函数：y+1x=0A(x,y)=A(x–1,1)y=0A(x–1,A(x,y–1))x,y>0Ackermann函数是一个双重的递归函数。同时它也是个二元递归。2021/7/2710计算机算法设计与分析联立递归联立递归是同时定义几个函数，它们彼此相互调用，从而形成递归，又称间接递归。例如Hilbert图案，下面所示为H1，H2和H3：H1H2H32021/7/2711计算机算法设计与分析Hil