王晓东《算法设计与分析》课件资料讲解.ppt

《王晓东《算法设计与分析》课件资料讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、王晓东《算法设计与分析》课件主要内容介绍（续）第7章概率算法第8章NP完全性理论第9章近似算法第10章算法优化策略2第1章算法引论1.1算法与程序1.2表达算法的抽象机制1.3描述算法1.4算法复杂性分析本章主要知识点：31.1算法与程序输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。是满足下述性质的指令序列。算法：程序：41.

2、从机器语言到高级语言的抽象1.2表达算法的抽象机制高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；52.抽象数据类型1

3、.2表达算法的抽象机制抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。抽象数据类型带给算法设计的好处有：（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。6在本书中，采用Java语言描述算法。1.Jav

4、a程序结构1.3描述算法以下，对Java语言的若干重要特性作简要概述。（1）Java程序的两种类型：应用程序和applet区别：应用程序的主方法为main，其可在命令行中用命令语句java应用程序名来执行；applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行。（2）包：java程序和类可以包(packages)的形式组织管理。（3）import语句：在java程序中可用import语句加载所需的包。例如，importjava.io.*;语句加载java.io包。71.3描述算法2.Jav

5、a数据类型数据类型基本数据类型：详见下页表1-1非基本数据类型：如Byte,Integer,Boolean,String等。Java对两种数据类型的不同处理方式：对基本数据类型：在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称实例）。如:intk;对非基本数据类型：语句Strings;并不建立具有数据类型String的对象，而是建立一个类型String的引用对象，数据类型为String的对象可用下面的new语句建立。s=newString(“Welcome”);Strings=newString(“Welcome

6、”);81.3描述算法表格1-1Java基本数据类型类型缺省值分配空间（bits）取值范围booleanfalse1[true,false]byte08[-128,127]charu000016[u0000,uFFFF]double0.064±4.9*10-324~±1.8*10308float0.032±1.4*10-45~±3.4*1038int032[-2147483648,2147483647]long064±9.2*1017short016[-32768,32767]91.3描述算法3.方法在Java中，执行特定任

7、务的函数或过程统称为方法(methods)。例如，java的Math类给出的常见数学计算的方法如下表所示：方法功能方法功能abs(x)x的绝对值max(x,y)x和y中较大者ceil(x)不小于x的最小整数min(x,y)x和y中较小者cos(x)x的余弦pow(x,y)xyexp(x)exsin(x)x的正弦floor(x)不大于x的最大整数sqrt(x)x的平方根log(x)x的自然对数tan(x)x的正切101.3描述算法3.方法计算表达式值的自定义方法ab描述如下：publicstaticintab(inta,intb){

8、return(a+b+Math.abs(a-b))/2;}（1）方法参数：Java中所有方法的参数均为值参数。上述方法ab中，a和b是形式参数，在调用方法时通过实际参数赋值。（2）方法重载：Java允许方法重载，即允许定义有不同签名的同名方法。上述