第1章算法引论剖析.ppt
《第1章算法引论剖析.ppt》由会员分享,可在线阅读,更多相关《第1章算法引论剖析.ppt(28页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1算法分析与设计算法分析与设计刘刘 伟伟(Sunny)E-mail:weiliu_Tel:135748184482主要内容介绍主要内容介绍第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法3参考教材参考教材4算法无处不在算法无处不在(1)从学校去火车站走哪条线路所需时间最少?(2)如何判断两个人是父子关系(DNA测序)?(3)如何让一个体积有限的背包中物品的价值最大?(4)如何规划可以让一个省的每个城市之间都有高速公路连通但总长度最小?(5)一张中国地图,对每个省进行着色,最少要几种颜色才能保证相邻的两个省颜色不同?5第第1 1章章 算法引论算法引论1.
2、1 算法与程序1.2 表达算法的抽象机制1.3 描述算法1.4 算法复杂性分析本章主要知识点:61.1 算法与程序算法与程序输输 入入:有零个或多个外部量作为算法的输入。输输 出出:算法产生至少一个量作为输出。确定性确定性:组成算法的每条指令清晰、无歧义。有限性有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。是算法用某种程序设计语言的具体实现算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性有限性。是满足下述性质的指令序列满足下述性质的指令序列。算法:程序:71.从机器语言到高级语言的抽象1.2 表达算法的抽象机制表达算法的抽象机制高级程序设计语言高级程序
3、设计语言的主要好处是:(4)把繁杂琐碎的事务交给编译程序,所以自动化程度高,开发周期短,程序员可以集中时间和精力从事更重要的创造性劳动,提高程序质量。(1)高级语言更接近算法语言,易学、易掌握,一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作;(2)高级语言为程序员提供了结构化程序设计的环境和工具,使得设计出来的程序可读性好,可维护性强,可靠性高;(3)高级语言不依赖于机器语言,与具体的计算机硬件关系不大,因而所写出来的程序可植性好、重用率高;82.抽象数据类型1.2 表达算法的抽象机制表达算法的抽象机制 抽象数据类型(ADT)是算法的一个数据模型连同定义在该模型上算法的一个数据模
4、型连同定义在该模型上并作为算法构件的一组运算并作为算法构件的一组运算。抽象数据类型抽象数据类型带给算法设计的好处有:(1)算法顶层设计与底层实现分离;(2)算法设计与数据结构设计隔开,允许数据结构自由选择;(3)数据模型和该模型上的运算统一在ADT中,便于空间和时间耗费的折衷;(4)用抽象数据类型表述的算法具有很好的可维护性;(5)算法自然呈现模块化;(6)为自顶向下逐步求精和模块化提供有效途径和工具;(7)算法结构清晰,层次分明,便于算法正确性的证明和复杂性的分析。92.抽象数据类型1.2 表达算法的抽象机制表达算法的抽象机制抽象数据类型描述:ADT 抽象数据类型名 数据对象:数据关系:基本
5、操作:ADT 抽象数据类型名实例:实例:线性表线性表ADT List 数据对象:D=ai|ai(-ElemSet,i=1,2,.,n,n=0 数据关系:R1=|ai-1,ai(-D,i=2,.,n 基本操作:InitList(&L)DestroyList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)ADT List103.伪代码1.2 表达算法的抽象机制表达算法的抽象机制输入3个数,打印输出其中最大的数。Begin(算法开始)输入 A,B,C IF AB 则 AMax 否则 BMax IF CMax 则 CMax Print MaxEnd(算法结束)114.
6、程序流程图1.2 表达算法的抽象机制表达算法的抽象机制12在本课程中,采用Java语言描述算法。1.Java程序结构程序结构 1.3 描述算法描述算法(1)Java程序的两种类型:应用程序和applet区别:应用程序的主方法为main,其可在命令行中用命令语句 java 应用程序名 来执行(2)包:Java程序和类可以包(packages)的形式组织管理。(3)import语句:在Java程序中可用import语句加载所需的包。例如,import java.io.*;语句加载java.io包。131.3 描述算法描述算法2.Java数据类型数据类型数据类型 基本数据类型:详见下页表1-1 非基
7、本数据类型:如 Byte,Integer,Boolean,String等。Java对两种数据类型的不同处理方式:对基本数据类型:在声明一个具有基本数据类型的变量时,自动建立该数据类型的对象(或称实例)。如:int k;对非基本数据类型:语句 String s;并不建立具有数据类型String的对象,而是建立一个类型String的引用对象,数据类型为String的对象可用下面的new语句建立。s=new String(“Welcome”);String s=new String(“Welcome”);141.3 描述算法描述算法表表1-1 Java基本数据类型基本数据类型类型类型缺省值缺省值分配
8、空间(分配空间(bitsbits)取值范围取值范围booleanfalse1true,falsebyte08-128,127charu000016u0000,uFFFFdouble0.0644.9*10-324 1.8*10308float0.0321.4*10-45 3.4*1038int032-2147483648,2147483647long0649.2*1017short016-32768,32767151.3 描述算法描述算法3.方法方法在Java中,执行特定任务的函数或过程统称为方法(methods)。例如,Java的Math类类给出的常见数学计算的方法如下表所示:方法方法功能功能
9、方法方法功能功能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的正切161.3 描述算法描述算法3.方法方法 计算表达式 值的自定义方法ab描述如下:public static int ab(int a,int b)return(a+b+Math.abs(a-b)/2;(1)方法参数:Java中所有方法的参数均为值参数。上述方法ab中,a和b是形式参数(形参
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 引论 剖析
限制150内