第2章 递归与分治策略 ppt课件.ppt

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

1、第二章递归与分治策略——“分”而治之2.1递归的概念2.2分治法的基本思想2.3二分搜索技术（折半查找）2.4大整数的乘法2.5Strassen矩阵乘法2.6棋盘覆盖2.7合并排序2.8快速排序2021/9/191第二章递归与分治策略——“分”而治之2.9线性时间选择2.10最接近点对问题2021/9/192第二章递归与分治策略——“分”而治之对大规模问题的求解利用分治法求解大规模问题1.基本思想分而治之方法法与软件设计的模块化方法非常相似。为解决一个大问题，可以（1）把它分解成两个或多个更小的问题；（2）分别解决每个小问题；（3）把各小问题的解答组合起来，即可得到原问题

2、的解。小问题通常与原问题相似或同质，因而可以递归地使用分而治之策略解决。2021/9/193通常，子问题与原始问题“同质”2021/9/1942.1递归的概念自己调用自己的函数称为递归函数(recursivefunction)直接递归：FF间接递归：FGH…F完整的递归定义必须满足如下条件：包含一个基本部分，对于n的一个或多个值，F(n)必须是直接定义的（即非递归）。在递归部分中，右侧所出现的所有F的参数都必须有一个比n小。2021/9/1952.1递归的概念直接或间接地调用自身的算法称为递归算法。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提

3、供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。2021/9/196例1阶乘函数阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。publicstaticintfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}2.1递归的概念2021/9/19

4、7例2Fibonacci数列(1202,莱昂纳多.斐波那契)无穷数列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);}2.1递归的概念2021/9/198该程序的优点：与数学定义在句法上几乎一样。缺点：效率极低，很多值被重复计算了多次。例如:F4=F3+F2=F2+F1+F1+F0=3F1+2F0=3对于任意n,

5、F(n-2)计算了2次，F(n-3)计算了3次，F(n-4)计算了5次。2.1递归的概念2021/9/199例1的非递归方式定义：n!=1*2*3*…*(n-1)*n例2的非递归方式定义：F(n)-F(n-1)-F(n-2)=0特征方程r2-r-1=02021/9/19102021/9/1911例3Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下：2.1递归的概念2021/9/1912例3Ackerman函数前2例中的函数都可以找到相应的非递归方式定义但本例中的Ackerman函数却无法找到非

6、递归的定义。2.1递归的概念2021/9/1913例3Ackerman函数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)=2n。m=3时，类似的可以推出A(n,3)=22..2,其中2的层数为n。m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。202

7、1/9/1914例4排列问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。设R={r1,r2,…,rn}是要进行排列的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)构成。2.1递归的概念2021/9/1915分析：