第1单元 算法引论(竞赛专用).pptVIP

中国计算机学会“21世纪大学本科计算机专业系列教材”算法设计与分析 王晓东 编著 主要内容介绍 第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 主要内容介绍（续） 第7章 概率算法 第8章 NP完全性理论 第9章 近似算法 第10章 算法优化策略 第1章 算法引论* 1.1 算法与程序 1.2 表达算法的抽象机制 1.3 描述算法 1.4 算法复杂性分析 1.1 算法与程序 输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 1.2 表达算法的抽象机制 1.从机器语言到高级语言的抽象 1.2 表达算法的抽象机制 2.抽象数据类型 1.3 描述算法 在本书中，采用Java语言描述算法。 1.Java程序结构 1.3 描述算法 2.Java数据类型 1.3 描述算法 表格1-1 Java基本数据类型 1.3 描述算法 3.方法 1.3 描述算法 1.3 描述算法 4.异常 1.3 描述算法 5.Java的类 1.3 描述算法 6.通用方法 1.3 描述算法 1.3 描述算法 1.3 描述算法 7.垃圾收集 8.递归 1.4 算法复杂性分析 1.4 算法复杂性分析 1.4 算法复杂性分析 1.4 算法复杂性分析 * 本章主要知识点： 是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 是满足下述性质的指令序列。* 算法： 程序： 高级程序设计语言的主要好处是： （4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 （1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作； （2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； （3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 抽象数据类型是算法的一个数据模型连同定义在该模型上 并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有： （1）算法顶层设计与底层实现分离； （2）算法设计与数据结构设计隔开，允许数据结构自由选择； （3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； （4）用抽象数据类型表述的算法具有很好的可维护性； （5）算法自然呈现模块化； （6）为自顶向下逐步求精和模块化提供有效途径和工具； （7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 以下，对Java语言的若干重要特性作简要概述。 （1）Java程序的两种类型：应用程序和applet 区别：应用程序的主方法为main，其可在命令行中用命令 语句 java 应用程序名 来执行； applet的主方法为init，其必须嵌入HTML文件，由 Web浏览器或applet阅读器来执行。 （2）包：java程序和类可以包(packages)的形式组织管理。 （3）import语句：在java程序中可用import语句加载所需的包。 例如，import java.io.*;语句加载java.io包。 数据类型 基本数据类型：详见下页表1-1 非基本数据类型：如 Byte, Integer, Boolean, String等。 Java对两种数据类型的不同处理方式： 对基本数据类型：在声明一个具有基本数据类型的变量时，自 动建立该数据类型的对象（或称实例）。如:int k; 对非基本数据类型：语句 String s; 并不建立具有数据类型 String的对象，而是建立一个类型String的引用对象， 数据类型为String的对象可用下面的new语句建立。 s = new String(“Welcome”); String s = new String(“Welcome”); [-32768,32767] 16 0 short ±9.2*1017 64 0 long [-2147483648,2147483647] 32 0 int ±1.4*10-45 ~ ±3.4*1038 32 0.0 float ±4.9*10-324 ~ ±1.8*10308 64 0.0 double [\u0000,\uFFFF] 16 \u0000 char [-128,127] 8 0 byte [true,false] 1 false