资源描述:
《第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整数