文档介绍：递归与分治综述
学院:计算机与通信工程学院
系别:计算机科学与技术
班级:
组员:
文档撰写:
程序编写:
目录
组员 2
摘要 4
第1章引言 5
第2章递归与分治策略 8
递归的概念 8
分治法的基本思想 12
第3章算法 14
归并排序算法 14
快速排序算法 18
二分搜索算法 23
大整数乘法算法 27
棋盘覆盖算法 30
33
40
Hanoi塔算法 43
第4章结论 48
参考文献 50
附录:程序源码 51
摘要
本文比较系统的介绍了递归与分治策略在归并排序,快速排序,二分搜索技术,大整数乘法,棋盘覆盖,最接近点对问题,循环赛日程表和Hanoi塔算法中的典型应用,浅显地分析了各类算法的复杂度和效率,通过结合在算法实现过程中遇到的不同程度的问题,归纳出各自的优缺点,并针对其不足提出了一定的解决方案。
关键词:递归、分治、递归调用、非递归调用
Abstraction:This paper partly systematically introduces the typical applications of the strategies of recursion and division-and-conquer in different sorts of algorithms, such as merge-sort, quick-sort, binary-search, multiplication of great integers, coverage of chessboard, most closed double sports, schedule of round robin and Hanoi tower, and superficially analyzes plexity and efficiency, bining those problems which occurs during the execution of the algorithms ,we sum up the advantages and disadvantages of them and propose some methods for their improvements.
Keywords:recursion、division-and-conquer、recursion allocation、un-recursion allocation
第一章引言
算法(Algorithm)一词是有由算术(Algorism)衍生而来的。字典的解释是“解决一类确定问题的任何一种特殊方法”。在计算机科学中算法是指用计算机解决一个问题的精确而有效的方法。一个好的算法对于实现高效的程序有着很大的意义。
算法在现代计算机软件设计的工程中起着非常重要的作用,它除了要保证正确的数据运算外,性能好坏也是十分重要的。
Ellis Horowitz等在《Fundamentals of Data Structure in C》一书中,从数据抽象、算法说明和定义,以及性能分析和量度等方面介绍数据结构,目的是用系统论的方法在整个软件生命周期内定位数据结构。现在更多的作者更是将数据结构和算法分析融为一体,比如Clifford A. Shaffer的《A Practical Introduction to Data Structures and Algorithm Analysis》。
人们可能误认为现代计算机硬件的性能已经很好了,如何组织数据以及程序的效率问题已不像从前那么重要了。实际上从软件的发展来看,正是由于硬件水平的提高,以前认为计算机难以有效求解的问题现在已被征服,计算机的应用也不断地向更复杂的领域扩展,随着求解问题复杂度的增加,高性能的算法仍然是计算机程序设计追求的目标。
谈到递归的历史,我们知道经典的递归算法的例子有例如hanoi塔问题:这个递归的原问题包含子问题。有些问题或者数据结构本来就是递归描述的,用递归做很自然。
递归发展到一定阶段,我们发现递归与递推的关系中,可以利用递归的思想建立递推关系,i数列。但递推由于没有返回段,因此更为简单,有时可以直接用循环实现。
再来看看关于分治策略,不少分治方法是源于递归思想,或是递归分解+合并处理。其实回溯法也是经典的递归算法之一,规模较小的问题用回溯解决比较自然。注意递归前后要保证现场的保存和恢复,即正确的转化问题。再来,动态规划也是递归的经典应用,其子问题重叠性质与递归有某种相似之处。递归加动态修改查表是一种不错的建立动