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

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

1、算法设计与分析第2章递归与分治策略2.1递归的概念2.2分治法的基本思想2.3二分搜索技术2.4大整数的乘法2.5Strassen矩阵乘法2.6棋盘覆盖2.7合并排序2.8快速排序2.9线性时间选择2.10最接近点对问题2.11循环赛日程表1学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）线性时间选择；（7）最接近点对问题；（8）循环赛日程表。分治法的总体思想问题分解

2、是求解复杂问题时很自然的做法。求解一个复杂问题可以将其分解成若干个子问题，子问题还可以进一步分解成更小的问题，直到分解所得的小问题是一些基本问题，并且其求解方法是已知的，可以直接求解为止。分治法作为一种算法设计策略，要求分解所得的子问题是同类问题，并要求原问题的解可以通过组合子问题的解来获取。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效的算法。2.1递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。在算法设计中使用递归技术，往往使算法的描述简单明了、易于理解、

3、容易编程和验证。在计算机软件领域，递归算法是一种非常重要并且不可或缺的算法。例1阶乘函数阶乘函数可递归地定义为：边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。边界条件递归方程intFactorial(intn){if(n==0)return1;returnn*Factorial(n-1);}例2Fibonacci（斐波那契）数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：intFibonacci(intn){

4、if(n<=1)return1;returnFibonacci(n-1)+Fibonacci(n-2);}例3Ackerman（阿克曼）函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n,m)定义如下：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(

5、1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2n。M=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的增加，它以难以想象的慢速度趋向正无穷大。例4排列问题设计一个递归算法

6、生成n个元素{r1,r2,…,rn}的全排列。从n个不同元素中任取m(m≤n)个元素，按照一定的顺序排列起叫做从n个不同元素中取出m个元素的一个排列，当m=n时所有的排列情况叫全排列。如1,2,3三个元素的全排列为：1，2，31，3，22，1，32，3，13，1，23，2，1集合X中元素的全排列记为perm(X)。(r)perm(X)表示在全排列perm(X)的每一个排列前加上前缀r得到的排列。设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。R的全排列可归纳定义如下：当n=1时，perm(R)=(r

7、)，其中r是集合R中唯一的元素；当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。templatevoidSwap(T&a,T&b)//交换两个T类型的数{Ttemp;temp=a;a=b;b=temp;}templatevoidPerm(Tlist[],intk,intm)//产生list[k:m]的所有排列{if(k==m){for(inti=0;i<=m;i++)cout<

8、}elsefor(inti=k;i<=m;i++){Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}intmain(){intlist[]={1,2,3};Perm(list,0,2);return0;}例5整数