资源描述：
《第2章递归算法与分治策略ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法设计与分析1第2章递归与分治策略本章主要知识点：2.1递归的概念2.2分治法的基本思想2.3二分搜索技术2.4大整数的乘法2.5Strassen矩阵乘法2.6棋盘覆盖2.7合并排序2.8快速排序2.9线性时间选择2.10最接近点对问题2.11循环赛日程表22.1递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。在计算机算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。下面来看几个实例。32.1递归的概念例1阶乘函数可递归地定义为：其中：n=0时，n!=1为边界条件n>0时，n!
2、=n(n-1)!为递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。42.1递归的概念例2Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为：第n个Fibonacci数可递归地计算如下：publicstaticintfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}小兔子问题5兔子问题著名的意大利数学家斐波那契(Fibon
3、acci)在他的著作《算盘书》中提出了一个“兔子问题”：假定小兔子一个月就可以长成大兔子，而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子，问到年底时将有多少对兔子? (当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)6(1)分析问题。这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是144只)，但仔细观察一下这个表格，你会发现兔子的数目增长得越来越快，如果时间再长，只用列表的方法就会有困难。(例如，你愿意用列表的方法求出5年后兔子的数目吗？)我们需要研究表中的规律，找出一般的方法，去解决这个问题。1月2月3月4月5月6月
4、7月8月9月10月11月12小兔111235813213455大兔1123581321345589合计11235813213455891447仔细研究表，你有些什么发现？每一个月份的大兔数、小兔数与上一个月的数字有什么联系，能肯定这个规律吗？8(2)设计算法。“兔子问题”很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F(N)，我们有：这是因为每月的大兔子数目一定等于上月的兔子总数，而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。92.1递归的概念例3Ackerman函数当一个函数及它的一个变量是由函数自身定义
5、时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下：前2例中的函数都可以找到相应的非递归方式定义。但本例中的Ackerman函数却无法找到非递归的定义。102.1递归的概念A(n，m)的自变量m的每一个值都定义了一个单变量函数：M=0时，A(n,0)=n+2M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2^n。M=
6、3时，类似的可以推出M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。定义其拟逆函数α(n)为：α(n)=min{k｜A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。α(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有α(n)≤4。但在理论上α(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。112.1递归的概念例4排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。设R={r1,r2,…,rn}
7、是要进行排列的n个元素，Ri=R-{ri}。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。12131415例4排列问题VoidPerm(Typelist[],intk,intm){//递归的产生前缀是list[0:k-1]后缀是list[k:m]的全排列的所有排列if
8、(k==m){//只剩下一个元素for(inti=0;i<=m;i++)cout<
