中国计算机学会“21世纪大学本科计算机专业系列教材”算法设计与分析王晓东编著1主要内容介绍第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法2主要内容介绍（续）第7章概率算法第8章NP完全性理论第9章近似算法第10章算法优化策略3第1章算法引论本章主要知识点：1.1算法与程序1.2表达算法的抽象机制1.3描述算法1.4算法复杂性分析41.1算法与程序算法：是满足下述性质的指令序列。输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质4即有限性。51.2表达算法的抽象机制1.从机器语言到高级语言的抽象高级程序设计语言的主要好处是：（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。61.2表达算法的抽象机制2.抽象数据类型抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。71.3描述算法在本书中，采用Java语言描述算法。以下，对Java语言的若干重要特性作简要概述。1.Java程序结构（1）Java程序的两种类型：应用程序和applet区别：应用程序的主方法为main，其可在命令行中用命令语句java应用程序名来执行；applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行。（2）包：java程序和类可以包packages的形式组织管理。（3）import语句：在java程序中可用import语句加载所需的包。例如，importjava.io.语句加载java.io包。81.3描述算法2.Java数据类型基本数据类型：详见下页表1-1数据类型非基本数据类型：如ByteIntegerBooleanString等。Java对两种数据类型的不同处理方式：对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）。如:intk对非基本数据类型：语句Strings并不建立具有数据类型String的对象，而是建立一个类型String的引用对象，数据类型为String的对象可用下面的new语句建立。snewString“Welcome”StringsnewString“Welcome”91.3描述算法表格1-1Java基本数据类型类型缺省值分配空间（bits）取值范围booleanfalse1truefalsebyte08-128127charu000016u0000uFFFFdouble0.064±4.910-324±1.810308float0.032±1.410-45±3.41038int032-21474836482147483647long064±9.21017short016-3276832767101.3描述算法3.方法在Java中，执行特定任务的函数或过程统称为方法methods。例如，java的Math类给出的常见数学计算的方法如下表所示：方法功能方法功能absxx的绝对值maxxyx和y中较大者ceilx不小于x的最小整数minxyx和y中较小者cosxx的余弦powxyxyexpxexsinxx的正弦floorx不大于x的最大整数sqrtxx的平方根logxx的自然对数tanxx的正切111.3描述算法3.方法abab计算表达式值的自定义方法ab描述如下：2publicstaticintabintaintbreturnabMath.absa-b/2（1）方法参数：Java中所有方法的参数均为值参数。上述方法ab中，a和b是形式参数，在调用方法时通过实际参数赋值。（2）方法重载：Java允许方法重载，即允许定义有不同签名的同名方法。上述方法