分治与递归基本思想
分治:分治强调“分而治”,即将一个规模大的难以解决的问题分成若干个规模小的易于解决的并且类型相同的子问题,通过解决这些子问题来最终解决大的问题。
递归:对于分治会产生几个问题,首先是如何将大问题分成各个子问题,其次何时才算“分”完了。这两个问题就是“递归”所关心的。如果分解的子问题还不能满足要求,“递归”会继续分下去,直到达到某个条件为止。
直接或间接地调用自身
的算法称为递归算法。用函数自身给出定义
的函数称为递归函数。
由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。
分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
示例 :
例1 阶乘函数
阶乘函数可递归地定义为:
n! = 1 n = 0 (边界条件)
n! = n(n-1)! n > 0 (递归方程)
边界条件
与递归方程
是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。
例2 Fibonacci数列
例3 快速排序
附录
1. 包含一些算法实现,主要想研究下 “全排列
”
http://www.cnblogs.com/chinazhangjie/archive/2010/10/07/1845034.html
包含一些示例算法来阐述递归与分治的思想
http://www.xinx.sdnu.edu.cn/sfzx/jpsykc/xlcad/xu02.html#%281%29
2. 主讲在有了递归式后,要做的处理
http://www.cs.pitt.edu/~ztliu/wordpress/2011/05/divide-and-conquer-algorithm/
3. 递归分治在快速排序中应用
http://blog.csdn.net/afgasdg/article/details/6040707
分享到:
相关推荐
递归与分治策略是学习计算机算法设计与分析的基础,掌握了这样的思想才能良好地高效率地去解决一些问题
递归与分治实验(二)Problem A:再次Hanoi塔问题Problem B:输油管道问题Problem C:Integer FactorizationProblem D:邮局选址问题Problem E:Gray code
根据给定文件的信息,我们可以总结出以下关于递归与分治技术的重要知识点: ### 一、递归的基本概念 #### 定义: 递归是一种在程序设计中非常重要的方法,它指的是在一个函数或过程中直接或间接地调用自身来解决...
在计算机科学领域,算法是解决问题的关键工具,而“递归与分治”是算法设计中极为重要的策略。本文将深入探讨这两个概念,并结合代码解析,帮助读者理解和掌握它们。 首先,我们来理解“递归”。递归是一种在函数...
分治与递归的关系密切,递归常常是实现分治策略的工具。在 Ackerman 函数中,虽然函数定义本身是递归的,但也可以转换为非递归形式。然而,递归版本往往更直观,更容易理解问题的本质。 在计算复杂度上,递归和分治...
通过不断练习和理解递归与分治的原理,开发者可以更好地应对各种编程挑战。不过,需要注意的是,理解和调试递归函数可能会有一定的难度,因此在实际编程中需要谨慎使用,并考虑优化方法以提高效率。
**算法设计与分析:递归与分治策略** 递归与分治策略是算法设计中的重要方法,它们常用于解决复杂问题。本实验报告主要探讨了三种使用递归策略的算法:Ackerman函数实现、大数划分以及数据集合的排列组合。 1. **...
在IT行业中,递归与分治策略是算法设计中非常重要的概念,尤其是在处理数据结构问题时。本章节内容将会详细阐述递归的概念、分治法的设计思想,以及如何通过递归方法来解决一些复杂的问题。分治策略通过将一个大问题...
计算计算法课件。递归与分治的思想以及几个经典问题
3. **递归分治**:根据二分查找的结果,缩小搜索范围,重复上述过程,直到找到最终的解。 4. **时间复杂度**:整个算法的时间复杂度为\( O(n \log Sum) \),其中\( n \)是序列的长度,\( Sum \)是序列所有元素的...
在计算机科学领域,递归和分治策略是两种强大的算法设计方法,它们广泛应用于解决复杂问题,提升程序的效率和可读性。本主题将深入探讨这两种策略,并结合实际问题——整数划分和特殊棋盘覆盖问题进行实例解析。 ...
算法中的递归与分治策略,这是老师上课的讲课的时候用的PPT,觉得不错!
算法思想——递归与分治 递归和分治是两种常用的算法思想,它们可以单独使用,也可以结合使用以解决复杂的问题。下面我们将详细探讨这两种算法思想。 递归是一种算法思想,它的基本思想是将一个问题分解成一个或多...
在ACM竞赛中,递归与分治是两种非常重要的算法思想,对于解决复杂问题有着极大的帮助。递归是通过函数自身调用解决问题的方法,而分治则是将一个大问题分解为若干个相同或相似的小问题,分别解决后再合并结果。下面...
在一个2的k次方乘以2的k次方个方格的棋盘中,恰有一个方格与其他方格不同为特殊方格,棋盘称为特殊棋盘,用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
递归与分治是计算机科学中两种重要的算法思想,它们在解决复杂问题时起到了关键作用。递归是一种方法,通过函数或程序直接或间接调用自身来解决问题。递归通常包含两个基本要素:边界条件和递归方程。边界条件是递归...
实验二递归与分治 本实验报告的主要内容是递归与分治算法的设计和实现,通过对快速排序和集合划分问题的研究,了解递归算法的思想和分治法的基本思想。 递归算法 递归算法是一种常用的算法设计方法,它通过将问题...