算法分析与设计第一二三章2(描述算法)

1、2008-09-01版权所有：杨波，武汉科技大学理学院 第一章第一章 数学预备知识数学预备知识 第二章第二章 导引与基本数据结构导引与基本数据结构第三章第三章 递归算法递归算法武汉科技大学理学院信息与计算科学系杨 波cookie_2008年9月2008-09-01版权所有：杨波，武汉科技大学理学院 SPARKS语言语言n教材为描述算法选用的一种计算机语言n类PASCAL语言n结构化设计n凡掌握一门程序设计语言的人都能很快看懂2008-09-01版权所有：杨波，武汉科技大学理学院 基本语法成分基本语法成分1）数据类型 整型 integer 实型 float 布尔型 boolean 字符型 cha

2、r2）变量声明 类型说明符 变量 integer i,j boolean b char c3）数组 任意整数下标 integer A(1:5,7:20) integer B(5,7:20) 2008-09-01版权所有：杨波，武汉科技大学理学院 4）赋值运算 （变量）（表达式） x 2 + x5）逻辑运算：and or not6）关系运算： 2008-09-01版权所有：杨波，武汉科技大学理学院 7）控制结构： 顺序:（略） 分支: if cond then S1 else S2 endif case :cond 1: S1 :cond 2: S2 :cond n: Sn :else: Sn+

3、1 endcase循环:while cond do Srepeatloop Suntil cond repeatfor vblestart to finish by increment do Srepeat 2008-09-01版权所有：杨波，武汉科技大学理学院 8) 函数的定义与调用 过程定义 procedure NAME(参数表) （说明部分） S end NAME 过程的调用： CALL 过程名 函数定义 类型名 procedure NAME(参数表) （说明部分） S return (表达式) end NAME 函数的引用：x function（参数）；2008-09-01版权所有：杨

4、波，武汉科技大学理学院 9) 变量的分类 a）根据数据类型分类 整型、实型、字符型等 b）根据作用域分类： 全程变量、局部变量、形式参数 c）根据是否带入、带出数据值/结果分类： in型变量 out型变量 inout型变量 边界效应：改变了参变量或全程变量的值 函数：通过函数值返回输出结果，没有边界效应 纯过程：没有函数值返回，只通过边界效应带出输出结果2008-09-01版权所有：杨波，武汉科技大学理学院 10) 特殊语句 a）exit 退出当前一层的循环 b）return 退出过程 return(表达式) : 函数返回结果 c）goto 无条件转向语句 goto label 11) 递归

5、a）直接递归：过程中包含对自身的调用 b）间接递归：间接调用自身12) 输入输出 read、print13）注释 /注释/2008-09-01版权所有：杨波，武汉科技大学理学院 JAVA语言语言n教学算法大多使用JAVA语言n面向对象的语言n使算法结构紧凑、可读性强2008-09-01版权所有：杨波，武汉科技大学理学院 Java程序结构（程序结构（1）n应用程序和appletqJava应用程序一定有一个主方法main，而applet的主方法名为init。qJava应用程序可在命令行中用命令语句：Java programNameqJava的applet必须嵌入HTML文件，由Web浏览器或app

6、let阅览器来执行qJava程序必须先编译后执行。系统在编译时将Java源程序转化为Java字节码(bytecode)。Java源程序文件的后缀为.java，编译后字节码文件的后缀为.class。 qJava字节码可以看作是在一台虚拟计算机即Java虚拟机（JVM）上运行的语言。本地计算机通过Java虚拟机解释运行Java程序。 2008-09-01版权所有：杨波，武汉科技大学理学院 Java程序结构（程序结构（1）Java源代码Java字节码编译JVMJVMJVM操作系统操作系统操作系统硬件硬件硬件2008-09-01版权所有：杨波，武汉科技大学理学院 Java程序结构（程序结构（2）n包q

7、Java程序和类可以包(packages)的形式组织管理。qJava自带的包有java.awt，java.io，java.lang，java.util等。 qJava用户可根据需要将自己的程序组织成各种应用包。 nImport语句 qJava程序中可以用import语句加载所需的包。 qimport java.io.*；语句加载java.io包。语句import java.io.PrintStream；则加载java.io包中的PrintStream类。2008-09-01版权所有：杨波，武汉科技大学理学院 Java数据类型数据类型Java的基本数据类型类型缺省值 分配空间（位）取值范围boo

8、leanfalse1true, falsebyte08-128+127charu000016u0000uFFFFdouble0.0644.910-324 1.810308float0.0321.410-45 3.41038int032-2147483648 2147483647long064-9.21017 +9.21017short016-32768327672008-09-01版权所有：杨波，武汉科技大学理学院 Java数据类型数据类型n经过包装的非基本数据类型qByteqIntegerqBooleanqStringq2008-09-01版权所有：杨波，武汉科技大学理学院 Java数据类型

9、数据类型n基本数据类型和包装类型的区别：q在声明一个具有基本数据类型的变量时，自动建立该数据类型的对象（或称为实例） 。q对经过包装的非基本数据类型，并不建立该数据类型的对象，而是建立一个该类型的引用对象（内存地址）。该数据类型的对象可用new语句建立。 2008-09-01版权所有：杨波，武汉科技大学理学院 Java数据类型数据类型int a;0aString s;s=new String(“str);nulls地址istsr地址i2008-09-01版权所有：杨波，武汉科技大学理学院 n方法：在Java语言中，执行特定任务的函数或过程统称为方法(methods)方法功能方法功能abs(x)

10、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的正切 方法方法Java的Math类给出的常见数学计算的方法2008-09-01版权所有：杨波，武汉科技大学理学院 对计算表达式 2baba值的自定义方法ab描述如下： public static int ab(int a,int b) return (a+b+Math.abs(a-b)/2;

11、 public static double ab(double a,double b) return (a+b+Math.abs(a-b)/2; 2008-09-01版权所有：杨波，武汉科技大学理学院 异常异常nJava的异常（exception）提供了一种处理错误的简洁的方法。当程序发现一个错误，就引发一个异常，以便在程序最合适的地方捕获异常并进行处理。 public static int ab(int a,int b) if(a=0|b0”); else return (a+b+Math.abs(a-b)/2;2008-09-01版权所有：杨波，武汉科技大学理学院 public stati

12、c void main(String args) tryf(); /try定义异常处理 catch(exception1) /catch捕获异常 异常处理1； /出现异常要执行的代码块 catch(exception2) 异常处理2； finally finally块； /无异常产生时都必须执行 2008-09-01版权所有：杨波，武汉科技大学理学院 异常处理完整的例子异常处理完整的例子public static void main(String args) trySystem.out.println(ab=+ab(-5,-7); catch(IllegalArgumentException

13、e) System.out.println(a=+(-5)+ b=+(-7); System.out.println(e); catch(Throwable e) System.out.println(e); finally System.out.println(Thanks); public static int ab(int a,int b) if(a=0|b0); else return (a+b+Math.abs(a-b)/2;2008-09-01版权所有：杨波，武汉科技大学理学院 Java的类的类nJava的类一般由4个组成部分： q类名q数据成员q方法q访问修饰 nPublic（公

14、有）：在public域中声明的数据成员和方法可以在程序的任何部分访问。 nprivate（私有）：在private域中声明的数据成员和方法构成类的私有部分，只能由该类的对象和方法对它们进行访问 。nprotected（保护）：在protected域中声明的数据成员和方法允许该类的对象、方法和子类访问。 2008-09-01版权所有：杨波，武汉科技大学理学院 public class Rectangle public static final int MAX=2000; private int x,y,h,w;/(x,y)是矩形左下角点的坐标，h是高，w是宽 public Rectangle(i

15、nt xx,int yy,int hh,int ww)/构造函数 if(hhMAX|wwMAX) throw new IllegalArgumentException(“Illegal values of h or w”); else x=xx; y=yy; h=hh; w=ww; public Rectangle()/构造方法 this(0,0,0,0); public int getHeigth()return h;/返回矩形的高 public int getWidth()return w;/返回矩形的宽 public static void main(String args) Recta

16、ngle r=new Rectangle(); Rectangle s=new Rectangle(1,1,20,20); System.out.println(”r.h=”+r.getHeight()+” r.w= “+r.getWidth(); System.out.println(“s.h=”+s.GetHeight()+” s.w= “+s.getWidth(); n构造函数qJava类的构造方法(Constructor)用于初始化对象的数据成员。构造方法名与它所在的类名相同。构造方法必须声明为类的公有方法。构造方法不可有返回值也不得指明返回类型。 n静态类成员qstatic：类成员前

17、的关键字static表明该类成员是静态成员。Java只维护静态类成员的一个拷贝，而非静态类成员的每个对象都有一个拷贝。qfinal：表示值不可修改。 n类对象q类对象的声明与创建方式类似于变量的声明与创建方式。对一个对象成员进行访问或调用可用运算符来实现。 n静态方法q静态方法的调用方式是：方法名（实际参数）。q非静态方法的调用方式是：. 2008-09-01版权所有：杨波，武汉科技大学理学院 垃圾收集垃圾收集 nJava的new运算用于分配所需内存空间。例如，int a=new int5000；分配5000字节空间给整型数组a。频繁用new分配空间可能会耗尽内存。Java的垃圾收集器会适时扫描内存