第1章 算法引论精要.ppt

* 算法分析与设计 刘 伟 (Sunny) E-mail: weiliu_china@163.com Tel:* 主要内容介绍 第1章 算法引论 第2章 递归与分治策略 第3章 动态规划 第4章 贪心算法 第5章 回溯法 第6章 分支限界法 * 参考教材 * 算法无处不在 (1) 从学校去火车站走哪条线路所需时间最少？ (2) 如何判断两个人是父子关系（DNA测序）？ (3) 如何让一个体积有限的背包中物品的价值最大？ (4) 如何规划可以让一个省的每个城市之间都有高速公路连通但总长度最小？ (5) 一张中国地图，对每个省进行着色，最少要几种颜色才能保证相邻的两个省颜色不同？ …… * 第1章 算法引论 1.1 算法与程序 1.2 表达算法的抽象机制 1.3 描述算法 1.4 算法复杂性分析 本章主要知识点： * 1.1 算法与程序 输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 是满足下述性质的指令序列。 算法： 程序： * 1.从机器语言到高级语言的抽象 1.2 表达算法的抽象机制 高级程序设计语言的主要好处是： （4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 （1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作； （2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； （3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； * 2.抽象数据类型 1.2 表达算法的抽象机制 抽象数据类型(ADT)是算法的一个数据模型连同定义在该模型上 并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有： （1）算法顶层设计与底层实现分离； （2）算法设计与数据结构设计隔开，允许数据结构自由选择； （3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； （4）用抽象数据类型表述的算法具有很好的可维护性； （5）算法自然呈现模块化； （6）为自顶向下逐步求精和模块化提供有效途径和工具； （7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 * 2.抽象数据类型 1.2 表达算法的抽象机制 抽象数据类型描述： ADT 抽象数据类型名{ 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 }ADT 抽象数据类型名 实例： 线性表 ADT List{ 数据对象: D={ai | ai(-ElemSet, i=1,2,...,n, n=0} 数据关系: R1={ai-1,ai| ai-1, ai(- D, i=2,...,n} 基本操作： InitList(L) DestroyList(L) ListInsert(L,i,e) ListDelete(L,i,e) }ADT List * 3.伪代码 1.2 表达算法的抽象机制 输入3个数，打印输出其中最大的数。 Begin（算法开始） 输入 A，B，C IF AB 则 A→Max 否则 B→Max IF CMax 则 C→Max Print Max End （算法结束） * 4. 程序流程图 1.2 表达算法的抽象机制 * 在本课程中，采用Java语言描述算法。 1.Java程序结构 1.3 描述算法 （1）Java程序的两种类型：应用程序和applet 区别：应用程序的主方法为main，其可在命令行中用命令 语句 java 应用程序名 来执行 （2）包：Java程序和类可以包(packages)的形式组织管理。 （3）import语句：在Java程序中可用import语句加载所需的包。 例如，import java.io.*;语句加载java.io包。 * 1.3 描述算法 2.Java数据类型 数据类型 基本数据类型：详见下页表1-1 非基本数据类型：如 Byte, Integer, Boolean, String等。 Java对两种数据类型的不同处理方式： 对基本数据类型：在声明一个具有基本数据类型的变量时，自 动