1、 本 科 毕 业 论 文 常用算法分析 及应用实例 Representative Algorithm Analysis and Application 姓 名： 学 号： 学 院：软件学院 系：软件工程 专 业：软件工程 年 级： 指导教师： 年 月 摘要 众所周知，在现代计算机科学和软件工 程中都会面临许多各种各样复杂的问题。不同的计算机编程语言，各种各样的组件控件，还有花样繁多的新技术不断涌现。这都是计算机科学发展的必然，没有最好的只有更好的。面对这么多不断变幻的选择，只有牢固的掌握了算法设计和分析的能力，才能以不变应万变。所有的技术都是在数据结构和算法的基础上建立的，牢固掌握算法的分析方
2、法和编程的能力就成为相当重要的一个部分。 算法是解题的步骤，可以把算法定义 为解决特定问题而规定的一系列操作。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。 算法的设 计与分析有很多常用的策略和分析方法。 本论文研究几种常用的算法分析策略和设计思想并进行具体问题实例分析。如：递归与分治策略， 动态规划算法， 贪心算法。研究每个算法分析策略的设计过程，实现一个迷宫探险算法的程序实例。 关键词 ：递归与分治；动态规划；贪心算法 . Abstract As we all know, in the modern computer science and so
3、ftware engineering will Face a wide range of complex issues. Different computer programming languages,wide range of control components, as well as diverse new technologies are emerging.This is the inevitable development of computer science, there is no best, only better.Constantly changing the face
4、of so many choices, only a solid grasp of algorithm design and analysis capabilities, to maintaining the status quo. All the technologies are in the data structure and algorithm based on the established and firmly grasp the analysis of algorithms and programming ability to become a very important pa
5、rt. Algorithm is problem-solving steps, the algorithm can solve the specific problem is defined as a series of operations required. In computer science, the algorithm to use language to describe the computer algorithm, algorithm on behalf of a class of computer problem solution accurate and effectiv
6、e method. Algorithm design and analysis of many commonly used strategies and analysis. This paper studies algorithms for some commonly-used analysis of strategies and design concepts and examples of analysis of specific issues. Such as: governance strategy and sub-recursive, dynamic programming algo
7、rithm, greedy algorithm. Analysis of research strategy for each algorithm design process, the realization of a maze exploration algorithm instance. Keywords: Recursion and Divided; Dynamic programming; Greedy algorithm. 目录 第一章 引言 . 1 1.1 为什么选择算法 . 1 1.2 算法概述 . 2 1.3 算法的正确性和效率 . 4 第二章 递归与分治策略 . 8 2.1
8、 递归的概念 . 8 2.2 分治法的基本思想 . 8 2.3 Hanoi 塔问题 . 9 2.3.1 算法分析 . 9 2.3.2 结论 . 12 2.3.4 具体的实验代码 . 13 2.4 快速排序算法 . 14 2.4.1 快速排序算法的分析 . 14 2.4.2 各排序算法的实现与比较 . 17 第三章 动态规划 . 19 3.1 动态规划的基本思想 . 19 3.2 最长公共子序列问题 LCS . 19 3.2.1 算法分析 . 19 3.2.2 算法的改进 . 23 3.2.3 程序实现和实验结果 . 23 3.3 最大子段和 . 24 3.3.1 算法分析 . 24 3.3.2
9、 三种算法的实验结果 . 28 第四章 贪心算法 . 30 4.1 贪心算法定义 . 30 4.2 装箱问题 . 30 4.2.1 算法分析 . 30 4.2.2 算法的实现 . 31 4.3 单源最短路径 . 32 4.3.1 算法基本思想 . 33 4.3.2 算法的实现 . 33 第五章 迷宫探险程序应用实例 . 34 5.1 程序简介 . 34 5.2 程序的设计思路 . 34 5.3 程序的基本结构描述 . 34 5.4 程序代码主体程序 . 36 5.5 程序运行结果 . 39 第六章 总结 . 40 致谢 . 43 参考文献 . 42 附录 . 43 Contents Chapt
10、er 1 Introduction . 1 1.1 Why Choose Algorithm . 1 1.2 Algorithm. 2 1.3 Algorithm Coorectness and Efficiency . 4 Chapter 2 Recursive . 8 2.1 The Concept of Recursive . 8 2.2 Divided . 8 2.3 Hanoi Tower Problem . 9 2.3.1 Algorithm Analysis . 9 2.3.2 Conclusion . 12 2.3.4 Experimental Specific Code .
11、13 2.4 Quick Sort Algorithm . 14 2.4.1 Analysis of Quicksort . 14 2.4.2 Sorting Algorithm Compare . 17 Chapter 3 Dynamic Programming . 19 3.1 The Basic Idea of Dynamic Programming . 19 3.2 Longest Sequence of Public Lcs. 19 3.2.1 Algorithm Analysis . 19 3.2.2 Algorithm . 23 3.2.3 Experimental Result
12、 . 23 3.3 The Largest Sub-Paragraph . 24 3.3.1 Algorithm Analysis . 24 3.3.2 Experimental Results of Three Algorithms. 28 Chapter 4 Greedy Algorithm. 30 4.1 The Definition of Greedy Algorithm. 30 4.2 Bin Packing Problem . 30 4.2.1 Algorithm Analysis . 30 4.2.2 Algorithm . 31 4.3 Single-Source Shorte
13、st Path . 32 4.3.1 The Basic Idea of Algorithm . 33 4.3.2 Algorithm . 33 Chapter 5 Application Maze Explorer . 34 5.1 Introduction . 34 5.2 Design Procedures . 34 5.3 Structure of The Procedures . 34 5.4 The Main Code . 36 5.5 Code and The Results of Experiments . 39 Chapter 6 Conclusion . 40 Acknow
14、ledgements. 41 References . 42 Appendix. 43厦门 大学软件学院毕业论文 常用算法分析及应用实例 1 第一章 引言 1.1 为什么选择算法 计算机既是数学的创造物，又是数学的创造者 ”， 而算法既是计算机理论和实践的核心，也是数学的最基本内容之一 .。甚至有人说， 数学学习的主要作用是形成 “算法思维 ”。算法有着悠久的发展历史，中国古代数学曾经以算法为特色， 取得了举世瞩目的辉煌成就。 在已经逐步进入信息化社会的今天，算法的基本知识、方法、思想日益融入人们社会生活的方方面面，已经也应该成为现代人所应具备的一种基本素质。 我学习算法有以下几个方面的 意义
15、： 算法学习有助于我们全面的理解运算能力。 很多时候 ,人们对运算存在一些误解，认为运算就是按照各种运算法则进行加、减、乘、除，从而学习运算就是背诵书本中给出的计算法则， 形成一些基本的计算技巧，也就是说，能够根据熟记的法则，迅速的计算给定式子的正确答案。 实际上，按照算法规则进行逻辑推理而获得正确结果仅仅是计算的很小的一个方面，更重要的是，在运算中构造、设计、选择一个合理的算法，理解相应的算理。 在算法学习中，我找出一个问题的不同算法，并比较这些算法的优劣，并作出选择，从而提高效率，而这个过程 才是一个真正的运算过程，因此算法学习使得我们拥有更加全面的理解运算能力。 算法学习能够培养在积极的
16、逻辑思维能力。 我们常常说数学是思维的体操，能够训练学生的思维能力。算法作为数学的一个基本内容，在培养逻辑思维能力上能够发挥重要的作用。 算法是解题方法的精确描述。 算法一方面具有具体化、程序化、机械化的特点 , 同时又有高度抽象性、概括性和精确性。 因此，将解决具体问题的方法整理成算法的过程是一个条理化，精确化和逻辑化的过程，有助于培养逻辑思维能力。 厦门 大学软件学院毕业论文 常用算法分析及应用实例 2 1.2 算法概述 什么叫算法 ? 算法（ Algorithm）是解题的步骤，可以把算法定义 为解决特定问题而规定的一系列操作。 在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机
17、解一类问题的精确、有效的方法。算法 +数据结构 =程序，求解一个给定的可计 算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题。 这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。 算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。制定一个算法，一般要经过设计、确 认、分析、编码、测试、调试、计时等阶段。 对算法的学习包括五个方面的内容： 设计算法。算法设计工作是不可能完全自动化的，应学习了解已经被实践证明是有用的一些基本的算法设计方法，这些基本的设计方法不仅适用于计算机科学，而
18、且适用于电气工程、运筹学等领域 ； 表示算法。描述算法的方法有多种形式，例如自然语言和算法语言，各自有适用的环境和特点； 确认算法。算法确认的目的是使人们确信这一算法能够正确无误地工作，即该算法具有可计算性。正确的算法用计算机算法语言描述，构成计算机程序，计算机程序在计算机 上运行，得到算法运算的结果； 分析算法。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较； 验证算法。用计算机语言描述的算法是否可计算、有效合理，须对程序进行测试，测试程序的工作由调试和作时空分布图组成。 算法的特性
19、 算法的特性 包括： 确定性。算法的每一种运算必须有确定的意义，该种运算应执行何种动厦门 大学软件学院毕业论文 常用算法分析及应用实例 3 作应无二义性，目的明确； 能行性。要求算法中有待实现的运算都是基本的，每种运算至少 在原理上能由人用纸和笔在有限的时间内完成； 输入。一个算法有 0 个或多个输入，在算法运算开始之前给出算法所需数据的初值，这些输入取自特定的对象集合； 输出。作为算法运算的结果，一个算法产生一个或多个输出，输出是同输入有某种特定关系的量； 有穷性。一个算法总是在执行了有穷步的运算后终止，即该算法是可达的。 满足前四个特性的一组规则不能称为算法，只能称为计算过程，操作系统是计
20、算过程的一个例子，操作系统用来管理计算机资源，控制作业的运行，没有作业运行时，计算过程并不停止，而是处于等待状态。 算法的描述 算法的描述方法 可以归纳为以下几种： (1) 自然语言； (2) 图形，如 N S图、流程图，图的描述与算法语言的描述对应； (3) 算法语言，即计算机语言、程序设计语言、伪代码； (4) 形式语言，用数学的方法，可以避免自然语言的二义性； 用各种算法描述方法所描述的同一算法，该算法的功用是一样的，允许在算法的描述和实现方法上有所不同。 人们的生产活动和日常生活离不开算法，都在自觉不自觉地使用算法，例如人们到商店购买物品，会首先确定购买哪些物品，准备好 所需的钱，然后确定到哪些商场选购、怎样去商场、行走的路线，若物品的质量好如何处理，对物品不满意又怎样处理，购买物品后做什么等。以上购物的算法是用自然语言描述的，也可以用其他描述方法描述该算法。 算法的复杂性 算法的复杂性 是算法效率的度量，在评价算法性能时，复杂性是一个重要的依据。算法的复杂性的程度与运行该算法所需要的计算机资源的多少有关，所需要的资源越多，表明该算法的复杂性越高；所需要的资源越少，表明该算法的
