算法设计与分析课件 第2章 递归与分治

《算法设计与分析课件 第2章 递归与分治》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Ó2005第2章递归与分治策略2.1递归的概念2.2分治法的基本思想2.3分治法的应用本章小结12.1递归的概念嵌套与递归22.1递归的概念例1:阶乘函数阶乘函数可递归地定义为：边界条件递归方程注意：(1)边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。(2)非递归定义：32.1递归的概念例2:Fibonacci数列问题引入裴波那契（Fibonaccileonardo，约1170-1250）是意大利著名数学家．在他的著作《算盘书》中许多有趣的问题，最富成功的问题是著名的“兔子繁殖问题”：如果每

2、对兔子每月繁殖一对子兔，而子兔在出生后第二个月就有生殖能力，试问一对兔子一年能繁殖多少对兔子？问题分析42.1递归的概念月份初生成熟总数01011011211231234235535865813……………………0123452.1递归的概念数列的特点数列的增长速度自然科学中的若干实例构造一个新数列6定义及解法2.1递归的概念→O(0.618n)→O(n)→O(logn)72.1递归的概念三种解法的比较解法1：O(0.618n)解法2：O(n)解法3：O(logn)fib(110)：O(0.618n)1022次运算O(n)111次运算O(lo

3、gn)7次运算82.1递归的概念思考：楼梯问题有一楼梯共有n阶，上楼可以一步上一阶，也可以一步上两阶。编一个程序，计算共有多少种不同的走法？9例3Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n,m)定义如下：2.1递归的概念102.1递归的概念Ackerman函数A(n,0)＝n+2A(n,1)＝2nA(n,2)＝2n。A(n,4)的增长速度非常快，以致于没有适当的数学式子来表示这一函数。112.1递归的概念例4数列的全排列问题求n个元素R={r1,r2,…,rn}的全排列

4、perm(R)。分析：当n=1时，perm(R)=(r)当n>1时，perm(R)由(r1)perm(R1)(r2)perm(R2)………(rn)perm(Rn)构成。（其中：Ri=R－{ri})122.1递归的概念例5整数划分问题将一个正整数n表示成形如下式的一系列正整数的和，称为n的一个划分。形如：n＝n1＋n2＋……＋nk其中：(ni≥1，i＝1,2,…,k，k≥1)且n≥n1≥n2≥……≥nk≥1132.1递归的概念例如：整数6的划分数有11种:6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1

5、+1，2+1+1+1+1；1+1+1+1+1+1;142.1递归的概念分析：将最大加数n1不大于m的划分个数记作q(n,m)而正整数n的划分数p(n)=q(n,n)。152.1递归的概念几个概念n的r划分n的r划分数n的不可重复划分问题扩展1将正整数划分成连续的正整数之和。15=7+815=4+5+615=1+2+3+4+5问题扩展2一个数分解为N个数的和，使这N个数的积为最大162.1递归的概念例6Hanoi塔问题问题描述：17问题分析：2.1递归的概念？ABCABCHanoi(n,A,B,C)圆盘数源柱辅助柱目标柱18=++ABCHano

6、i(n-1,A,C,B)ABCHanoi(n-1,B,A,C)ABCMove(n,A,C)2.1递归的概念19递归求解voidhanoi(intn,inta,intb,intc){if(n==1)move(a,b);else{hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}递归函数的运行轨迹2.1递归的概念20Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,

7、A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束21时间复杂性分析：规模为n的Hanoi(n)问题，可以分解为2个规模为n-1的Hanoi(n-1)问题和一个Move操作。所以，n个盘子的移动次数为：2.1递归的概念若n=64，则移动次数为264－1264－1＝18,446,744,073,7

8、09,551,615222.1递归的概念264－1＝18,446,744,073,709,551,615是个什么概念？实例1：假设每秒钟移动一次，一年约315569