第1章算法引论

1、算法设计与分析主要内容介绍o第1章算法引论o第2章递归与分治策略o第3章动态规划o第4章贪心算法o第5章回溯法o第6章分支限界法o第7章概率算法o第8章NP完全性理论o第9章近似算法o第10章 算法优化策略第1章 算法引论o1.1算法与程序o1.2表达算法的抽象机制o1.3描述算法o1.4算法复杂性分析1.1 算法与程序算法：算法：是满足下述性质的指令序列。o输 入：有零或多个外部量作为算法的输入。o输 出：算法产生至少一个量作为输出。o确定性：组成算法的每条指令清晰、无歧义。 o有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。程序：程序： 是算法用某种程序设计语言的具体实现。

2、程序可以不满足算法的性质(4)即有限性。例如：操作系统是一个程序，不是算法，但其各种任务如作业管理、进程调度可以采用特定的算法来实现。1.2 表达算法的抽象机制1. .算法的三要素算法的三要素（数据、运算和控制）算法的数据：基本数据（布尔值 字符 整数 实数）较复杂数据（向量 矩阵 记录）更复杂数据（集合 树 图 声音 图像）算法的运算：基本运算（逻辑 赋值 算术 关系）复杂运算（函数值计算 向量运算 集合运算 表、树、图上的运算）2.2.从机器语言到高级语言的抽象从机器语言到高级语言的抽象高级程序设计语言的主要好处是：（1）更接近算法语言，易学、易掌握；（2）提供了结构化程序设计的环境和工具

3、，使得设计出来的程序可读性好，可维护性强，可靠性高；（3）不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；（4）把繁杂琐碎的事务交给编译程序，自动化程度高。3.抽象数据类型抽象数据类型算法从非形式的自然语言表达到形式化的高级语言表达，是一个复杂的过程，要做很多繁杂琐碎的事情，因而仍然需要抽象。对于一个数学问题，设计算法的一般步骤为：（1）先选用该问题的一个数据模型。（2）接着，弄清数据模型在已知条件下的初始状态和要求的结果状态，以及两个状态之间的关系。（3）然后探索从已知初始状态出发到达要求的结果状态所必需的运算步骤。例如：计算自然数例如：计算自然数m,n的

4、的最大公约数最大公约数按照自顶向下逐步求精的原则，在探索运算步骤时，首先应该考虑算法顶层运算步骤，然后再考虑底层运算步骤。 顶层运算步骤顶层运算步骤：是指定义在数据模型级上的运算步骤，或叫宏观运算。它们组成算法的主干部分。表达这部分算法的程序就是主程序。底层运算步骤底层运算步骤：是指顶层抽象的运算的具体实现。它们依赖于数据模型的结构，依赖于数据模型结构的具体表示。包括两部分:一是数据模型的具体表示;二是定义在该数据模型上的运算的具体实现。 抽象数据类型：抽象数据类型：为了将顶层算法与底层算法隔开，使二者在设计时不会互相牵制、互相影响，必须对二者的接口进行一次抽象。让底层只通过这个接口为顶层服务

5、，顶层也只通过这个接口调用底层的运算。这个接口就是抽象数据类型抽象数据类型。其英文术语是Abstract Data Types，简记ADT。抽象数据类型：抽象数据类型：是算法的一个数据模型连同定义在该模型上、作为该算法构件的一组运算。 抽象数据类型的概念实际上是我们熟悉的基本数据类型概念的引伸和发展。高级语言基本数据类型已隐含着数据模型和定义在该模型上的运算的统一。例如：逻辑类型就是逻辑值数据模型和或()、与()、非()三种逻辑运算的统一体；整数类型就是整数值数据模型和加(+)、减(-)、乘(*)、除(div)四种运算的统一体； 抽象数据类型带给算法设计的好处有： （1）算法顶层设计与底层实现

6、分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 1.3 描述算法o描述算法可以有多种方式n自然语言方式、表格方式、图示形式等n本书采用Java语言描述算法oJava语言的优点是类型丰富、语句精炼，具有面向过程和面向对象的双重特点，可以充分利用抽象数据类型这一有力工具表述算法。下面，对Java语言作简要概述1.Java

7、1.Java程序结构程序结构 （1）应用程序和applet区别：应用程序的主方法为main，后缀为.java，执行时先编译为字节码文件(.class)，然后可以在任何一台java虚拟机上运行。applet的主方法为init，其必须嵌入HTML文件，由Web浏览器或applet阅读器来执行。（2）包：java程序和类可以包(packages)的形式组织管理。 （3）import语句：在java程序中可用import语句加载所需的包。例如：import java.io.*;/语句加载java.io包2.Java2.Java数据类型数据类型 Java对两种数据类型的不同处理方式：o对基本数据类型：在

8、声明一个变量时，自动建立该类型的对象（或称实例）。o对非基本数据类型：声明时，只建立该类型对象的引用，创建对象要使用new语句建立。例如：String s; s=new String(“Welcome”); String s=new String(“Welcome”);数据类型 基本数据类型：详见表1-1 非基本数据类型：如 String等。 类型缺省值分配空间（bits）取值范围booleanfalse1true,falsebyte08-128,127charu000016u0000,uFFFFdouble0.064 4 . 9 * 1 0- 3 2 4 1.8*10308float0.03

9、21.4*10-45 3.4*1038int032-2147483648,2147483647long0649.2*1017short016-32768,32767表格表格1-1 Java基本数据类型基本数据类型3.3.方法方法 Java中，执行特定任务的函数或过程统称为方法(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

10、(x) 不大于x的最大整数 sqrt(x)x的平方根log(x)x的自然对数tan(x)x的正切自定义方法： public static int ab(int a, int b) return (a+b+Math.abs(a-b)/2; （1）方法参数：（2）方法重载：允许定义有不同签名的同名方法2baba计算表达式 值的自定义方法ab描述如下： 4.异常异常Java的异常提供了一种处理错误的方法。当程序发现一个错误，就引发一个异常，以便在合适地方捕获异常并进行处理。异常来源：（1）Java运行时环境自动抛出系统生成的异常。如，除数为0。（2）程序员自己抛出的异常。通常用try块来定义异常处理

11、。每个异常处理由一个catch语句组成。一般结构为：public static void main(String args) try f ( ); catch (exception1) 异常处理; catch (exception2) 异常处理; finally finally块; 异常是针对方法来说的，抛出、捕获和处理异常都是在方法中进行的。下面来举例说明异常处理：（1）声明）声明ab方法时定义要抛出的异常：方法时定义要抛出的异常：public static int ab(int a,int b)if(a=0|b0);else return (a+b+Math.abs(a-b)/2;（2）调

12、用）调用ab方法时对异常进行处理：方法时对异常进行处理：public static void main(String args)/在try中调用ab方法，若发生异常，则抛出trySystem.out.println(ab=+ab(-5,-7);/捕获到Ill异常，则执行该catch块中内容catch (IllegalArgumentException e)System.out.println(a=+(-5)+ b=+(-7);System.out.println(e); catch(Throwable e)System.out.println(e);/无论是否发生异常都执行finallySys

13、tem.out.println(thanks);5.Java的类的类Java的类一般由4个部分组成：（1）类名（2）数据成员（3）方法（4）访问修饰举例说明：定义矩形Rectangle类公有(public) 私有(private)保护(protected) public class Rectangle public static final int MAX=2000;private int x,y,h,w;public Rectangle(int xx,int yy,int hh,int ww)if(hhMAX | wwMAX)throw new IllegalArgumentExceptio

14、n(Illegal Values of h or w);elsex=xx; y=yy; h=hh; w=ww;public Rectangle()this(0,0,0,0);public int getHeight() return h;public int getWidth() return w;public static void main(String args)Rectangle r=new Rectangle();Rectangle s=new Rectangle(1,1,20,20);System.out.println(r.h=+r.getHeight()+ r.w=+r.get

15、Width();System.out.println(s.h=+s.getHeight()+ s.w=+s.getWidth();类相关内容：（1）类的对象：一个对象成员可以使用.运算符访问（2）构造方法：构造方法用来对对象进行初始化，可以重载，无返回值（3）静态类成员对于静态类成员java只维护其一个拷贝，非静态成员，每个对象有一个拷贝。main为静态方法。非静态方法的调用：.静态方法的调用：6.通用方法下面的方法swap用于交换一维整型数组a的位置i和位置j处的值。 public static void swap(int a,int i,int j)int temp=ai;ai=aj;aj

16、=temp;public static void swap(Object a,int i,int j)Object temp=ai;ai=aj;aj=temp;该方法只适用于整型数该方法只适用于整型数组组该方法具有通用性，适该方法具有通用性，适用于用于Object类型及其所类型及其所有子类有子类 （1）接口接口同继承、多态一样，都是Java 程序语言的特色。Java 程序设计中的接口，是一种规范。定义了类应该做什么？但不关心如何做？即接口中只有方法名，没有方法体。public static Computable sum(Computable a,int n)if(a.length=0) ret

17、urn null;Computable sum=(Computable) a0.zero();for (int i=0;in;i+)sum.increment(ai);return sum;接口定义：接口定义：public interface Computable public Object add(Object x);public Object substract(Object x);public Object multiply(Object x);public Object divide(Object x);public Object mod(Object x);public Object

18、 increment(Object x);public Object zero();public Object identity();（2）java.lang.Comparable 接口o此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序。o该接口唯一的方法为compareTo方法，用来比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。（3）接口的多继承o例如：public interface Operable extends Computable,Comparable （4）自定义包装类o 由于Java的包装类如Integer

19、等已定义为final型，因此无法定义其子类，作进一步扩充。为了需要可自定义包装类。 o例如：public class MyInteger implements Operableprivate Integer value;public Object add(Object x) return new MyInteger(value+(MyInteger)x).value);public int compareTo(Object o) int y=(MyInteger)x).value;if(value0,b0,c0，abbalogbaabcccloglog)(loganabnbloglogbaaccblogloglogaabb