资源描述：
《第二章 递归与分治策略ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章递归与分治策略本章学习要点理解递归的概念掌握设计有效算法的分治策略通过范例学习分治策略设计技巧2.1递归的基本概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数2.1递归的基本概念存在于算法中的常用自调用函数：例1阶乘函数阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。2.1递归的基本概念例2Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。Fibonacci数列可以递归地定义为：
2、边界条件递归方程第n个Fibonacci数可递归地计算如下：publicstaticintfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}2.1递归的基本概念例3Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下：2.1递归的基本概念例3Ackerman函数前2例中的函数都可以找到相应的非递归方式定义：但本例中的Ackerman函数却无法找到非递归的定义。2.1递归的基本概念例3Ackerman函数A
3、(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=3时，类似的可以推出M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。2.1递归的基本概念定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。例3Ackerman函数α(
4、n)在复杂度分析中常遇到。对于通常所见到的正整数n，有α(n)≤4。但在理论上α(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。定义其拟逆函数α(n)α(n)=min{k｜A(k)≥n},即α(n)是使n≤A(k)成立的最小的k值。2.2用递归法解决实际问题1、排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：当n
5、=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。2.2用递归法解决实际问题2、Hanoi塔问题用递归法设计模拟汉诺塔问题求解的过程汉诺塔问题的描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，求把A柱上的盘子全部移到C柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。2.2用递归法解决实际问题2、Hanoi塔
6、问题基本分析：1个盘子的汉诺塔问题可直接移动；n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。4个盘子汉诺塔问题的递归求解示意图如下图所示：2.2用递归法解决实际问题123412342342、Hanoi塔问题112234341234图2-1汉诺塔问题的递归求解示意图434如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移动步数最小的方案2.2用递归法解决实际问题思考题：2、Hanoi塔问题名人问题在一群人中寻找一个人，这个人被所
7、有人认识，但他却不认识人群中的任何一个人算法一：判断是否为1，并且是否为N该算法的时间复杂度为：名人问题算法二：由N-1归纳出N个人的情况若N-1中没有名人，则只需判断是否为1，并且是否为N若N-1中有一个名人，则只需判断是否为1，并且是否为N该算法的时间复杂度为：在一群人中寻找一个人，这个人被所有人认识，但他却不认识人群中的任何一个人名人问题在一群人中寻找一个人，这个人被所有人认识，但他却不认识人群中的任何一个人算法三：，若则；若则该算法的时间复杂度为：递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大
