第5章-递归.ppt

《第5章-递归.ppt》由会员分享，可在线阅读，更多相关《第5章-递归.ppt（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第一页，编辑于星期五：十六点 四十九分。第第5章章 递归递归学习目标: 理解递归的概念。 掌握用分治法设计有效算法的策略。 掌握用动态规划法设计有效算法的策略。 掌握用回朔法解题的算法设计策略。 理解递归算法的工作原理和模拟递归的方法。第二页，编辑于星期五：十六点 四十九分。5.1 递归的概念递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。第三页，编辑于星期五：十六点 四十九分。递归应用举例递归应用举例阶乘函数 int factorial(int n) if(n=0) return 1; return n*factorial(n-1); Fibonacc

2、i数列 int fibonacci(int n) if(n=1) return 1; return fibonacci(n-1)+fibonacci(n-2) 第四页，编辑于星期五：十六点 四十九分。递归应用举例递归应用举例Ackerman函数 A(1,0)=2; A(0,m)=1; A(n,0)=n+2; A(n,m)=A(A(n-1,m),m-1)N个元素全排列 void perm(int list,int k,int m) int i; if(k=m) for(i=0;i=m;i+)printf(“%d”,listi); printf(“n”); else for(i=k;i=m;i+)

3、 swap(listk,listi); perm(list,k+1,m); swap(listk,listi); 第五页，编辑于星期五：十六点 四十九分。递归应用举例递归应用举例整数划分问题 int q(int n,int m) if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(nfirst); int count(link x) if(x=0) return 0; return 1+count(x-next); 第七页，编辑于星期五：十六点 四十九分。递归应用举例递归应用举例间接递归 sin2=2sincos cos2=1-2*sin*sin

4、double s(double x) if(-0.005x&x0.005) return x-x*x*x/6; return 2*s(x/2)*c(x/2); double c(double x) if(-0.005x&x0.005) return 1.0-x*x/2; return 1.0-2*s(x/2)*s(x/2); 第八页，编辑于星期五：十六点 四十九分。5.2.1 分治与递归分治与递归分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。采用分治法解决的问题一般具有的特征如下： 1. 问题的规模缩小到一定的规模就可以较容易地解决。 2

5、. 问题可以分解为若干个规模较小的模式相同的子问题，即该问题具有最优子结构性质。 3. 合并问题分解出的子问题的解可以得到问题的解。 4. 问题所分解出的各个子问题之间是独立的，即子问题之间不存在公共的子问题。设计步骤设计步骤1. 划分步：把输入的问题划分为k个子问题，并尽量使这k个子问题的规模大致相同。 2. 治理步：当问题的规模大于某个预定的阈值n0时，治理步由k个递归调用组成。 3. 组合步：组合步把各个子问题的解组合起来，它对分治算法的实际性能至关重要，算法的有效性很大地依赖于组合步的实现。 第九页，编辑于星期五：十六点 四十九分。5.2.1 分治法应用举例分治法应用举例二分搜索技术

6、二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取an/2与x进行比较。如果x=an/2，则找到x,算法终止。如果xan/2,则只要在数组a的右半部继续搜索x。合并排序：将待排序元素分成大小大致相同的2个子集合，分别对2个子集进行排序，最终将排好序的子集合合并成为所要求的集合。快速排序:线性时间选择：给定线性序集中n个元素和一个整数k,1=k=n,要求找出这n个元素中第k小的元素，即当k=1时找的是最小元素，k=n时找的是最大元素，当k=(n+1)/2时，成为找中位数。 第十页，编辑于星期五：十六点 四十九分。5.2.1 分治法应用举例分治法应用举例 最接近点对问题 给定平面上n个点

7、，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最少。循环赛日程表问题 第十一页，编辑于星期五：十六点 四十九分。动态规划动态规划动态规划算法适用于解最优化问题。通常可以按以下步骤设计： 找出最优解的性质，并刻画其结构特征；递归地定义最优值；以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造最优解。第十二页，编辑于星期五：十六点 四十九分。动态规划动态规划动态规划算法的基本要素最优子结构； 重叠子问题； 备忘录方法；第十三页，编辑于星期五：十六点 四十九分。动态规划举例动态规划举例矩阵连乘问题；最长公共子序列；给定两个序列X和Y,找出X和Y的公共最长子序列 给定两个

8、序列X,Y,当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 例如，若 X=A,B,C,B,D,A,B Y=B,D,C,A,B,A 则序列B,C,A是X,Y的公共子序列。 而序列B,C,B,A是X,Y的最长公共子序列。 第十四页，编辑于星期五：十六点 四十九分。动态规划举例动态规划举例凸多边形最优三角剖分 给定凸多边形P=V0,V1Vn-1,以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分所对应的权，即该三角剖分中诸三角形上权之和为最少。 第十五页，编辑于星期五：十六点 四十九分。动态规划举例动态规划举例图像压缩电路布线

9、流水作业调度0-1背包问题 给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问：应该如何选择装入背包的物品，使得装入背包中物品的总价值最大。 第十六页，编辑于星期五：十六点 四十九分。回溯与递归回溯与递归 回溯法有“通用解题法”之称。用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法，它适用于求解组合数较大的问题。第十七页，编辑于星期五：十六点 四十九分。其他算法其他算法贪心算法 分支定界法概率算法近似算法等第十八页，编辑于星期五：十六点 四十九分。