递归、分治、动态规划、回溯

《递归、分治、动态规划、回溯》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归、分治、动态规划与回溯回溯递归递推一般实现方式正反方向有时可相互转化较简洁,要求数学规律性较强DFS穷举的优化版启发式搜索路径寻找图论/网络流…………数学问题：组合数学树、图、排序等问题分治、以大化小动态规划的实现DP=递归＋贪心回溯、递归、递推是计算机算法中基础内容，范围极其广泛。递归与分治基本原理对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。T(n/2)nT(n/2)T(n/2)T(n/2)T(n)=T(n/2)nT(n/2)T(n/2)T(n/2)T(n)=对这k个子问题

2、分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。递归与分治基本原理n/2T(n/4)T(n/4)T(n/4)T(n/4)将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)

3、T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)递归与分治基本原理递归的概念直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许

4、多高效算法。递推与递归递归与递推表面看来是相逆的过程，其实也是相似的，最终的计算都是从小算到大。递推的使用环境要求高导致了递推的高效性，递推没有重复计算什么数据，保持了高效。递归大多数会重复计算子问题，导致时间浪费，所以一般不要使用过深的递归，甚至会空间溢出。但是也不能说递推好，递归差，因为递归却能解决很多递推做不到的事情，在某些特定的环境下也能实现高效，并且递归容易使用。我们要就事论事！斐波那契数列（Fibonacci），对于f（30），如果使用递归则需要运行1664079次，而递推只需30次就可以了，速度悬殊。递归：longf(longn){ifi<3thenret

5、urn1;elsef(i-1)+f(i-2);}递推：longf(longn){a[1]:=1;a[2]:=1;fori:=1ton-2do{f[i+2]:=f[i]+f[i+1];}递推与递归1.经典递归例如Hanoi塔问题：经典的递归，原问题包含子问题。有些问题或者数据结构本来就是递归描述的，用递归做很自然。2.递归与递推，数学式关系利用递归的思想建立递推关系，如由兔子生崽而来的fibonacci数列。但递推由于没有返回段，因此更为简单，有时可以直接用循环实现。3.分治等以大化小算法不少分治方法是源于递归思想，或是递归分解+合并处理。递归的应用范围递归的应用范围4.

6、回溯规模较小的问题用回溯解决比较自然。注意递归前后要保证现场的保存和恢复，即正确的转化问题。5.动态规划动态规划的子问题重叠性质与递归有某种相似之处。递归+动态修改查表是一种不错的建立动态规划模型的方法。树、图、排序等符合递归子问题思想的结构树、图等数据结构本身就是递归结构，因此当然是使用递归来处理。7.其他例如排列组合等，很杂的。递归举例例1阶乘函数阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。例2Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，…

7、，被称为Fibonacci数列。它可以递归地定义为：边界条件递归方程第n个Fibonacci数可递归地计算如下：publicstaticintfibonacci(intn){if(n<=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}递归举例例3Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下：递归举例例3Ackerman函数前2例中的函数都可以找到相应的非递归方式定义：但本例中的Ackerman函数却无法找到非递