《程序与算法》PPT课件

《《程序与算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、前言石志国引言算法设计在计算科学中具有核心的地位和作用，没有好的算法，计算机完成一件工作可能需要1年；有好算法，计算机完成一件工作可能需要几秒。算法被公认为是计算科学的基石，翻开重要的学术刊物，算法都占有一席之地，没有算法，程序将不复存在。程序与算法要成为编程高手，要有必胜的信心，信心的来源是建立在扎实的基本功之上的。而程序员的基本功，无疑就是对“算法与数据结构”的理解。对算法与数据结构的理解有助于程序员了解语言背后的具体细节，同时，数据结构的定义很大程度上决定了程序的可维护性和可扩展性。因此，算法与数据结构是程序员信心之源。课程简介本课程涵盖了绝大多数算法设计中的常用技术。在表达每

2、一种技术时，阐述它的应用背景，强调每个算法运转背后的简洁数学思想，注意运用与其他技术类比的方法来说明它的特征，并提供了大量相应实际问题的例子。同时也注重了对每一种算法的复杂性分析。主要内容全书分成3部分共10章，从基本的数字算法人手，先后介绍了分治、图的遍历、贪心算法、动态规划等技术。书中每章后面都附有大量的习题，有利于读者对书中内容的理解和应用。第一部分算法与数据结构基础第1章算法的基本概念第2章C++算法设计基础第3章线性数据结构基础第4章非线性数据结构基础第二部分实用算法与案例解析第5章实用排序算法基础第6章实用搜索算法基础第7章递归与分治法第8章贪心法与动态规划第9章回溯法与

3、分枝定界第三部分算法综合案例第10章著名算法与综合案例算法简介计算机的问世是20世纪人类最伟大的发明之一，它把人类社会带进了信息技术时代，而算法是计算机科学的重要基础，就像算盘一样，人们需要为计算机编制各种各样的“口诀”即算法(algorithm)，才能使其工作。尽管算法并不给出问题的精确的解，只是说明怎样才能得到解，但是，算法通常都是由有限个操作组成的。这些操作包括加、减、乘、除、判断、赋值等，并按顺序、分支、循环等结构组织在一起。算法的特性：作为一个算法，应该具备如下5个特性①输入性一个算法要具有0个或多个外部量作为算法的输入。这些外部量通常体现为算法中的一组变量。有些输入量需要

4、在算法执行过程中输入。从表面上看，有些算法好像没有输入量，实际上是输入量已被嵌入到算法之中。②输出性一个算法必须具有一个或多个输出，以反映算法对输入数据加工后的结果。没有输出的算法是毫无意义的。③确定性算法的每一个步骤必须具有确定的定义，即每一步要执行的动作是确定的，是无二义性的。在任何条件下，算法只有惟一的一条执行路径，即对于相同的输入得出的输出结果也是相同的。④有穷性对于任何合法的输入值，算法必须在执行有限个步骤之后结束，并且每一步都可以在有限的时间内完成。⑤可行性算法中描述的操作都是可以通过已经实现的基本运算的有限次执行来实现，即算法的具体实现应该能够被计算机执行。算法的判别依

5、据：判断一个算法的好坏主要依据如下4个标准。①正确性正确性是设计一个算法的首要条件，如果一个算法不正确，其它方面就无从谈起。一个正确的算法是指在合理的数据输入下，能在有限的时间内得出正确的结果。②可读性算法主要是为了人的阅读与交流，其次才是让计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的算法易于隐藏较多错误而使实现该算法的程序的调试工作变得更加困难。③健壮性算法应当具备检查错误和对错误进行适当处理的能力。一般而言，处理错误的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。④效率效率是指算法执行时所需计算机资源的多少，包括运行

6、时间和存储空间两方面的要求。运行时间和存储空间都与问题的规模有关。存储空间指的是算法执行过程中所需的最大存储空间。算法描述形式算法的描述形式多种多样，不同的算法描述形式对算法的质量有一定的影响。描述同一个算法可以采用自然语言、流程图、盒图、伪代码、程序设计语言等。常用的描述算法方法有如下3种：①自然语言描述法最简单的描述算法的方法是使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的的理解和阅读。缺点是不够严谨，易产生歧义。当算法比较复杂且包含很多转移分支时，用自然语言描述就不是那么直观清晰了。②算法框图法使用程序流程图、盒图等算法描述工具来描述算法。其特点是简洁、明了，

7、便于理解和交流。③伪码语言描述法数据结构＋算法＝程序大部分的算法最终是需要通过能够向计算机发送一系列命令的程序来实现的。所谓“程序”是指对所要解决问题的各个对象和处理规则的描述，或者说是数据结构和算法的描述，因此有人说，数据结构＋算法＝程序。程序与算法不同。程序可以不满足算法的第④个特性。例如操作系统，它是在无限循环中执行的程序，因而不是算法。然而可把操作系统的各种任务看作一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法实现，该子程序得到输