《递归与分治》PPT课件

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

1、Ó2005第2章递归与分治策略几个例子2.1递归的概念2.2分治法的基本思想2.3分治法的应用本章小结1几个例子称球游戏给定n个球，其中一个球为次品。次品在外表上与正常球无区别，但重量有分别（可能偏重或偏轻）。现在给一个天平，问：需要称几次才能将次品甄别出来？募捐问题向贫困山区儿童募捐10,000元。世界杯足球赛全球200多支球队里，选出最好的。分治法的设计思想是:将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。凡治众如治寡，分数是也。----孙子兵法22.1递归的概念例

2、1:阶乘函数阶乘函数可递归地定义为：边界条件递归方程注意：(1)边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。(2)非递归定义：32.1递归的概念例2:Fibonacci数列问题引入裴波那契（Fibonaccileonardo，约1170-1250）是意大利著名数学家．在他的著作《算盘书》中许多有趣的问题，最富成功的问题是著名的“兔子繁殖问题”：如果每对兔子每月繁殖一对子兔，而子兔在出生后第二个月就有生殖能力，试问一对兔子一年能繁殖多少对兔子？问题分析4

3、2.1递归的概念月份初生成熟总数01011011211231234235535865813……………………0123452.1递归的概念数列的特点（1）数列的增长速度（2）自然科学中的若干实例（3）构造一个新数列6定义：2.1递归的概念72.1递归的概念如何求解？解法1：O(0.618n)intfib(intn){if((n=0)

4、

5、(n==1))returnn;returnfibonacci(n-1)+fibonacci(n-2);}解法2：O(n)解法3：O(logn)fib(110)：O(0.618n

6、)1022次运算O(n)111次运算O(logn)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)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。

7、112.1递归的概念例4排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。集合X中元素的全排列记为perm(X)，(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。122.1递归的概念R的全排列可归纳定义如下：当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n>1时，perm(R)由:(r1)perm(R1)(r2)perm(R2)………(rn)perm(Rn)构

8、成。参考算法：132.1递归的概念例5整数划分问题将一个正整数n表示成形如下式的一系列正整数的和，称为n的一个划分。形如：n＝n1＋n2＋……＋nk其中：(ni≥1，i＝1,2,……,k，k≥1)且n≥n1≥n2≥……≥nk≥1142.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+1，2+1+1+1+1；1+1+1+1+1+1;152.1递归的概念分析：将最大加数n1不大于m的划分个数记作q(n,m)(1)q(n,1)

9、=1,n³1;(2)q(n,m)=q(n,n),m³n;最大加数n1实际上不能大于n。因此，q(1,m)=1。(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1≤n-1的划分组成。(4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1的划分组成。16而：正整数n的划分数p(n)=q(n,n)。2.1递归的概念因此：q(n,m)的递归定义如下172.1递归的概念例6Hanoi塔问题问题描述：18问题分

10、析：2.1递归的概念？ABCABCHanoi(n,A,B,C)圆盘数源柱辅助柱目标柱19=++ABCHanoi(n-1,A,C,B)ABCHanoi(n-1,B,A,C)ABCMove(n,A,C)2.1递归的概念20递归求解voidhanoi(intn,inta,intb,intc){if(n>0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}递归函数的运行轨迹2.1递归的概念