资源描述：
《递归与分治策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章递归与分治策略本章主要内容2.1递归的概念2.2分治法的基本思想2.3二分搜索技术2.4大整数的乘法2.5Strassen矩阵乘法2.7合并排序2.8快速排序2.11循环赛日程表2.1递归的概念2.1.1递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。在计算机算法设计与分析中，使用递归技术往往使函数的定义和算法的描述简洁且易于理解。使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如C语言、Pascal语言等）使用递归算法要耗用更多的栈空间，应避免采用。一般的的递归算法都可以改写成与之等价的非递归
2、算法。2.1递归的概念2.1.2递归的几个实例例1阶乘函数（理解）可以递归地定义为：其中：n=0时，n!=1为边界条件n>0时，n!=n(n-1)!为递归方程边界条件与递归方程是递归函数的二个要素，只有具备这两个要素，才能在有限次计算后得出结果。2.1递归的概念若乘法执行次数记作M(n)，则有如下结论：M(n)没有定义为n的函数，而是定义它本身在另一点上值的函数，这种等式称为递推关系，或递推式。用反向替换法求解递推关系式：M(n)=M(n-1)+1替换M(n-1)=M(n-2)+1=[M(n-2)+1]+1=M(n-2)+2替换M(n-2)=M(n-
3、3)+1=[M(n-3)+1]+1=M(n-3)+3=M(n-i)+i=M(n-n)+n=n2.1递归的概念例2斐波那契数列（理解）FibonacciSequence黄金分割数列兔子繁殖问题1202年，意大利数学家斐波那契(Fibonacci)在他的《算盘书》中提出这样一个问题：有人想知道一年内一对兔子可繁殖成多少对，便筑了一道围墙把一对兔子关在里面。已知一对兔子每一个月可以生一对小兔子，而一对兔子出生后第二个月就开始生小兔子。假如一年内没有发生死亡，则一对兔子一年内能繁殖成多少对？2.1递归的概念●表示一对成熟的兔子；○表示未成熟的兔子。每一对成熟
4、的兔子经过一个月变成本身的●及新生的未成熟○；未成熟的一对○经过一个月变成成熟的●，没有出生新兔；画出左图。2.1递归的概念在数学上，斐波那契数列是以递归的方法来定义：第n个Fibonacci数可递归地计算如下：2.1递归的概念斐波那契数列一般表达式的初等代数解法已知a1=1，a2=1，an=an−1+an−2首先构建等比数列令α>0，β>0,设an+αan−1=β(an−1+αan−2)化简得an=(β−α)an−1+αβan−2比较系数可得解得2.1递归的概念预知后事如何变换...参见维基百科斐波那契数列http://zh.wikipedia.o
5、rg/zh-cn/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%972.1递归的概念斐波那契数列的通项公式为（又叫“比内公式”，是用无理数表示有理数的一个范例）可它的每一项却都是整数。开普勒发现两个斐波那契数的后两项比会趋近黄金分割：这个数列有广泛的应用，如树的年分枝数目就遵循斐波那契数列的规律；而且计算机科学的发展，为斐波那契数列提供了新的应用场所。2.1递归的概念斐波那契的另一种表示法2.1递归的概念2.1递归的概念前面定义的递归算法效率并不高，为什么？F(5)F(4)F(3)F(3)F(
6、2)F(2)F(1)F(1)F(0)F(2)F(1)F(1)F(0)F(1)F(0)数列的递归调用树Fib(n)//输入：非负整数n//输出：第n个斐波那契数CreateF[0…n]F[0]=1;F[1]=1fori=2tondoF[i]=F[i-1]+F[i-2]returnF(n)2.1递归的概念例3Ackerman函数（了解）当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。前两例都能找到函数的非递归定义，但Ackerman函数却无法找到(?但是有非递归的算法)。Ackerman函数A(n,m)定义如下：2.1递归的概念A(n
7、,m)的自变量m的每个值都定义了一个单变量函数M=0时：A(n,0)=n+2M=1时：A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2A(1,1)=2故A(n,1)=2*n(n>=1)M=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=3时，类似的可以推出，2的层数为nM=4时，A(n,4)的增长速度非常快，没有适当的数学式子来表示这一函数。2.1递归的概念定义单变量的Ackerman函数A(n)为，A(n)=A(n,n)。定义其拟逆函数
8、α(n)为α(n)=min{k｜A(k)≥n}即α(n)是使n≤A(k)成立的最小的k值。A(0)=1,A(
