王晓东《算法设计和分析》市公开课一等奖百校联赛获奖课件.pptx
《王晓东《算法设计和分析》市公开课一等奖百校联赛获奖课件.pptx》由会员分享,可在线阅读,更多相关《王晓东《算法设计和分析》市公开课一等奖百校联赛获奖课件.pptx(356页珍藏版)》请在咨信网上搜索。
1、中国计算机学会中国计算机学会“二十一世纪大学本科计算机专业系列二十一世纪大学本科计算机专业系列教材教材”算法设计与分析算法设计与分析王晓东王晓东编著编著1第1页主要内容介绍主要内容介绍第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法2第2页主要内容介绍(续)主要内容介绍(续)第7章概率算法第8章NP完全性理论第9章近似算法第10章 算法优化策略3第3页第第1 1章章 算法引论算法引论1.1 算法与程序1.2 表示算法抽象机制1.3 描述算法1.4 算法复杂性分析本章主要知识点:4第4页1.1 算法与程序算法与程序输 入:有零个或多个外部量作为算法输入。
2、输 出:算法产生最少一个量作为输出。确定性:组成算法每条指令清楚、无歧义。有限性:算法中每条指令执行次数有限,执行每条指令时间也有限。是算法用某种程序设计语言详细实现。程序能够不满足算法性质(4)即有限性。是满足下述性质指令序列。算法:程序:5第5页1.从机器语言到高级语言抽象1.2 表示算法抽象机制表示算法抽象机制高级程序设计语言主要好处是:(4)把繁杂琐碎事务交给编译程序,所以自动化程度高,开发周期短,程序员能够集中时间和精力从事更主要创造性劳动,提升程序质量。(1)高级语言更靠近算法语言,易学、易掌握,普通工程技术人员只需 要几周时间培训就能够胜任程序员工作;(2)高级语言为程序员提供了
3、结构化程序设计环境和工具,使得设计出来程序可读性好,可维护性强,可靠性高;(3)高级语言不依赖于机器语言,与详细计算机硬件关系不大,因而所写出来程序可植性好、重用率高;6第6页2.抽象数据类型1.2 表示算法抽象机制表示算法抽象机制 抽象数据类型是算法一个数据模型连同定义在该模型上并作为算法构件一组运算。抽象数据类型带给算法设计好处有:(1)算法顶层设计与底层实现分离;(2)算法设计与数据结构设计隔开,允许数据结构自由选择;(3)数据模型和该模型上运算统一在ADT中,便于空间和时间花费折衷;(4)用抽象数据类型表述算法含有很好可维护性;(5)算法自然展现模块化;(6)为自顶向下逐步求精和模块化
4、提供有效路径和工具;(7)算法结构清楚,层次分明,便于算法正确性证实和复杂性分析。7第7页在本书中,采取Java语言描述算法。1.1.JavaJava程序结构程序结构 1.3 描述算法描述算法以下,对JavaJava语言若干主要特征作简明概述。(1)Java程序两种类型:应用程序和appletapplet区分:应用程序主方法为main,其可在命令行中用命令语句 java 应用程序名 来执行;applet主方法为init,其必须嵌入HTML文件,由Web浏览器或applet阅读器来执行。(2)包:java程序和类能够包(packages)形式组织管理。(3)import语句:在java程序中可用
5、import语句加载所需包。比如,import java.io.*;语句加载java.io包。8第8页1.3 描述算法描述算法2.2.JavaJava数据类型数据类型数据类型 基本数据类型:详见下页表1-1 非基本数据类型:如 Byte,Integer,Boolean,String等。Java对两种数据类型不一样处理方式:对基本数据类型:在申明一个含有基本数据类型变量时,自动建立该数据类型对象(或称实例)。如:int k;对非基本数据类型:语句 String s;并不建立含有数据类型String对象,而是建立一个类型String引用对象,数据类型为String对象可用下面new语句建立。s=n
6、ew StringString(“Welcome”);StringString s=new StringString(“Welcome”);9第9页1.3 描述算法描述算法表格表格1-1 1-1 JavaJava基本数据类型基本数据类型类型缺省值分配空间(bits)取值范围booleanfalse1true,falsebyte08-128,127charu000016u0000,uFFFFdouble0.0644.9*10-324 1.8*10308float0.0321.4*10-45 3.4*1038int032-2147483648,2147483647long0649.2*1017sh
7、ort016-32768,3276710第10页1.3 描述算法描述算法3.3.方法方法在Java中,执行特定任务函数或过程统称为方法(methods)。比如,javaMathMath类类给出常见数学计算方法以下表所表示:方法方法功效方法方法功效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正切11第11页1.3 描述算法描述算法3.3.方法方法 计算表示式 值自定义方法ab
8、描述以下:public static int ab(int a,int b)return(a+b+Math.abs(a-b)/2;(1)方法参数:Java中全部方法参数均为值参数。上述方法ab中,a和b是形式参数,在调用方法时经过实际参数赋值。(2)方法重载:Java允许方法重载,即允许定义有不一样署名同名方法。上述方法ab可重载为:public static double ab(double a,double b)return(a+b+Math.abs(a-b)/2.0;12第12页1.3 描述算法描述算法4.4.异常异常 Java异常提供了一个处理错误方法。当程序发觉一个错误,就引发一个异
9、常,方便在适当地方捕捉异常并进行处理。通惯用trytry块来定义异常处理。每个异常处理由一个catchcatch语句组成。public static void main(String args)try f();catch(exception1)异常处理;catch(exception2)异常处理;finally finally块;13第13页1.3 描述算法描述算法5.5.JavaJava类类(4)访问修饰访问修饰公有(public)私有(private)保护(protected)Java类普通由4个部分组成:(1)类名类名(2)数据组员数据组员(3)方法方法14第14页1.3 描述算法描述算
10、法6.6.通用方法通用方法 下面方法swapswap用于交换一维整型数组a位置i和位置j处值。public static void swap(int a,int i,int j)int temp=ai;ai=aj;aj=temp;public static void swap(object a,int i,int j)object temp=ai;ai=aj;aj=temp;该方法只适合用于该方法只适合用于整型数组整型数组该方法含有通用性,适合该方法含有通用性,适合用于用于ObjectObject类型及其全部类型及其全部子类子类 以上方法修改以下:以上方法修改以下:15第15页1.3描述算法描
11、述算法6.6.通用方法通用方法(1 1)ComputableComputable界面界面 public static Computable sum(Computable a,int n)if(a.length=0)return null;Computable sum=(Computable)a0.zero();for(int i=0;i n;i+)sum.increment(ai);return sum;利用此界面使利用此界面使方法方法sumsum通用化通用化 16第16页1.3 描述算法描述算法6.6.通用方法通用方法(2 2)java.lang.Comparable java.lang.C
12、omparable 界面界面 JavaComparable 界面中惟一方法头compareTo用于比较2个元素大小。比如java.lang.CpareTo(y)返回x-y符号,当xy时返回正数。(3 3)OperableOperable 界面界面 有些通用方法同时需要Computable界面和Comparable 界面支持。为此可定义Operable界面以下:public interface Operable extends Computable,Comparable(4 4)自定义包装类)自定义包装类 因为Java包装类如Integer等已定义为final型,所以无法定义其子类,作深入扩充。
13、为了需要可自定义包装类。17第17页1.3 描述算法描述算法7.7.垃圾搜集垃圾搜集8.8.递归递归Javanewnew运算用于分配所需内存空间。比如,int a=new int500000;分配000字节空间给整型数组a。频繁用new分配空间可能会耗尽内存。Java垃垃圾搜集器圾搜集器会适时扫描内存,回收不用空间(垃圾)给new重新分配。Java允许方法调用其本身。这类方法称为递归方法。public static int sum(int a,int n)if(n=0)return 0;else return an-1+sum(a,n-1);计算一维整型数组前计算一维整型数组前n n个个元素之
14、和递归方法元素之和递归方法 18第18页1.4 算法复杂性分析算法复杂性分析 算法复杂性是算法运行所需要计算机资源量,需要时间资源量称为时间复杂性时间复杂性,需要空间资源量称为空间复杂性空间复杂性。这个量应该只依赖于算法要解问题规模、算法输入和算法本身函数。假如分别用N、I和A表示算法要解问题规模、算法输入和算法本身,而且用C表示复杂性,那么,应该有C=F(N,I,A)。普通把时间复杂性和空间复杂性分开,并分别用T和S来表示,则有:T=T(N,I)和S=S(N,I)。(通常,让A隐含在复杂性函数名当中)19第19页1.4 算法复杂性分析算法复杂性分析最坏情况下时间复杂性:最好情况下时间复杂性:
15、平均情况下时间复杂性:其中DN是规模为N正当输入集合;I*是DN中使T(N,I*)到达Tmax(N)正当输入;是中使T(N,)到达Tmin(N)正当输入;而P(I)是在算法应用中出现输入I概率。20第20页1.4 算法复杂性分析算法复杂性分析算法复杂性在渐近意义下阶:渐近意义下记号:O、o 设f(N)和g(N)是定义在正数集上正函数。O O定义定义:假如存在正常数C和自然数N0,使得当NN0时有f(N)Cg(N),则称函数f(N)当N充分大时上有界,且g(N)是它一个上界,记为f(N)=O(g(N)。即f(N)阶不高于g(N)阶。依据O定义,轻易证实它有以下运算规则:(1)O(f)+O(g)=
16、O(max(f,g);(2)O(f)+O(g)=O(f+g);(3)O(f)O(g)=O(fg);(4)假如g(N)=O(f(N),则O(f)+O(g)=O(f);(5)O(Cf(N)=O(f(N),其中C是一个正常数;(6)f=O(f)。21第21页1.4 算法复杂性分析算法复杂性分析 定义定义:假如存在正常数C和自然数N0,使得当NN0时有f(N)Cg(N),则称函数f(N)当N充分大时下有界,且g(N)是它一个下界,记为f(N)=(g(N)。即f(N)阶不低于g(N)阶。定义定义:定义f(N)=(g(N)当且仅当f(N)=O(g(N)且f(N)=(g(N)。此时称f(N)与g(N)同阶。
17、o o定义定义:对于任意给定0,都存在正整数N0,使得当NN0时有f(N)/Cg(N),则称函数f(N)当N充分大时阶比g(N)低,记为f(N)=o(g(N)。比如,4NlogN+7=o(3N2+4NlogN+7)。22第22页第第2 2章章 递归与分治策略递归与分治策略23第23页将要求解较大规模问题分割成k个更小规模子问题。算法总体思想算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=对这k个子问题分别求解。假如子问题规模依然不够小,则再划分为k个子问题,如此递归进行下去,直到问题规模足够小,很轻易求出其解为止。24第24页算法总体思想算法总体思想对这k个子问题分别求
18、解。假如子问题规模依然不够小,则再划分为k个子问题,如此递归进行下去,直到问题规模足够小,很轻易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)将求出小规模问题解合并为一个更大规模问题解,自底向上逐步求出原来问题解。25第25页算法总体思想算法总体思想将求出小规模问题解合并为一个更大规模问题解,自底向上逐步求出原来问题解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4
19、)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)26第26页算法总体思想算法总体思想将求出小规模问题解合并为一个更大规模问题解,自底向上逐步求出原来问题解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)分治法设计思想是,将一个难以直接处理大问题,分治法设计思想是,将一个难以直接处理大问题,分割成一些规模较小相同问题,方
20、便各个击破,分割成一些规模较小相同问题,方便各个击破,分而治之。分而治之。凡治众如治寡,分数是也。凡治众如治寡,分数是也。-孙子兵法孙子兵法27第27页2.1 2.1 递归概念递归概念直接或间接地调用本身算法称为递归算法递归算法。用函数本身给出定义函数称为递归函数递归函数。由分治法产生子问题往往是原问题较小模式,这就为使用递归技术提供了方便。在这种情况下,重复应用分治伎俩,能够使子问题与原问题类型一致而其规模却不停缩小,最终使子问题缩小到很轻易直接求出其解。这自然造成递归过程产生。分治与递归像一对孪生弟兄,经常同时应用在算法设计之中,并由此产生许多高效算法。下面来看几个实例。28第28页2.1
21、 2.1 递归概念递归概念例例1 1 阶乘函数阶乘函数阶乘函数可递归地定义为:边界条件边界条件递归方程递归方程边界条件与递归方程是递归函数二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。29第29页2.1 2.1 递归概念递归概念例例2 Fibonacci2 Fibonacci数列数列无穷数列1,1,2,3,5,8,13,21,34,55,被称为Fibonacci数列。它能够递归地定义为:边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算以下:public static int fibonacci(int n)if(n 1时,perm(R)由(r1)pe
22、rm(R1),(r2)perm(R2),(rn)perm(Rn)组成。36第36页2.1 2.1 递归概念递归概念例例5 5 整数划分问题整数划分问题将正整数n表示成一系列正整数之和:n=n1+n2+nk,其中n1n2nk1,k1。正整数n这种表示称为正整数n划分。求正整数n不同划分个数。比如正整数6有以下11种不一样划分:6;5+1;4+2,4+1+1;3+3,3+2+1,3+1+1+1;2+2+2,2+2+1+1,2+1+1+1+1;1+1+1+1+1+1。37第37页(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。所以,q(1,m)=1。(1)q(n,1)=1,n1
23、;当最大加数n1小于1时,任何正整数n只有一个划分形式,即 (4)q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n最大加数n1小于m划分由n1=m划分和n1n-1 划分组成。(3)q(n,n)=1+q(n,n-1);正整数n划分由n1=n划分和n1n-1划分组成。2.1 2.1 递归概念递归概念例例5 5 整数划分问题整数划分问题前面几个例子中,问题本身都含有比较显著递归关系,因而轻易用递归函数直接求解。在本例中,假如设p(n)为正整数n划分数,则难以找到递归关系,所以考虑增加一个自变量:将最大加数n1小于m划分个数记作q(n,m)。能够建立q(n,m)以下递归关系。38第3
24、8页2.1 2.1 递归概念递归概念例例5 5 整数划分问题整数划分问题前面几个例子中,问题本身都含有比较显著递归关系,因而轻易用递归函数直接求解。在本例中,假如设p(n)为正整数n划分数,则难以找到递归关系,所以考虑增加一个自变量:将最大加数n1小于m划分个数记作q(n,m)。能够建立q(n,m)以下递归关系。正整数n划分数p(n)=q(n,n)。39第39页40第40页2.1 2.1 递归概念递归概念例例6 Hanoi6 Hanoi塔问题塔问题设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上这
25、一叠圆盘移到塔座b上,并仍按一样次序叠置。在移动圆盘时应恪守以下移动规则:规则1:每次只能移动1个圆盘;规则2:任何时刻都不允许将较大圆盘压在较小圆盘之上;规则3:在满足移动规则1和2前提下,可将圆盘移至a,b,c中任一塔座上。41第41页在问题规模较大时,较难找到普通方法,所以我们尝试用递归技术来处理这个问题。当n=1时,问题比较简单。此时,只要将编号为1圆盘从塔座a直接移至塔座b上即可。当n1时,需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小圆盘依照移动规则从塔座a移至塔座c,然后,将剩下最大圆盘从塔座a移至塔座b,最终,再设法将n-1个较小圆盘依照移动规则从塔座c移至塔座b。由此
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法设计和分析 王晓东 算法 设计 分析 公开 一等奖 联赛 获奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。