算法引论概要PPT课件

-,1,算法设计与分析（ACM/ICPC程序设计方法论）,广东江门五邑大学信息学院高宏宾,2007年8月,-,2,主要内容介绍,第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法第7章概率算法第8章NP完全性理论第9章近似算法第10章算法优化策略,-,3,第1章算法引论,1.1算法与程序算法设计实例例1.按递增次序生成M的最小的n个元素，M定义为：1MxM，则y=2x+1My=3x+1M,本章主要知识点,1.1算法与程序1.2表达算法的抽象机制1.3描述算法1.4算法复杂性分析,-,4,0123456789p2p3i,134713,if(2*mp2=3*mp3)mi=2*mp2+1;p2+;p3+;elseif(2*mp2eps)e+=t;/*加当前项*/i+=1;n*=i;/*计算i的阶乘*/t=1/n;/*计算下一项*/printf(e=%fn,e);,例2.计算e的值,-,6,例3.螺旋方阵的生成,10,13,11,12,25,21,20,19,18,17,16,15,14,9,8,7,6,5,4,3,2,1,24,23,22,#defineM64main()inti,j,num,n,aMM;num=1;scanf(%d,-,7,例4.方阵的旋转,10,13,11,12,25,21,20,19,18,17,16,15,14,9,8,7,6,5,4,3,2,1,24,23,22,aijjijn-i+1an-i+1j,temp,for(j=i;jn-i+1;j+)temp=aij;aij=ajn-i-1;ajn-i-1=an-i-1n-j-1;an-i-1n-j-1=an-j-1i;an-j-1i=temp;,-,8,#include#defineM64main()inti,j,temp,n,aMM;scanf(%d,for(i=0;in;i+)for(j=0;jn;j+)printf(%d,aij);printf(n);,-,9,例5.幻方阵的生成,13,6,4,16,14,7,5,23,15,17,24,8,2,1,19,12,10,22,20,25,18,9,11,3,21,#defineM64main()inti,j,n,aMM;scanf(%d,for(i=0;in;i+)for(j=0;jn;j+)printf(%5d,aij);printf(n);,-,10,2.算法设计方法与实践,递归方法分治方法动态规划方法贪心方法回溯方法分支限界方法概率方法NP完全性近似方法算法优化方法,-,11,3.算法的概念,算法是为解决某个特定问题而设计的由一些命令组成的序列，该序列具备5大特征：1.有穷性算法中命令的个数是有限的；每个命令的执行时间是有限的。2.确定性算法中每个命令的含义是确切的。3.有效性算法中每个命令是可行的。4.输入算法需要从外界接受数据,且个数0。5.输出算法必须产生一组数据作为其结果，且个数0。,-,12,4.简单算法举例,例6.计算12345的值。推广：计算i(i=1,n)的值。分析：为了计算12(i-1)i(i+1)n，我们不妨设p=12i并称p为部分积。此时，对于当前的i,若做操作i+1i,然后对部分积p做操作pip，则p的值顺增一个因子。因此，反复进行i+1i；pip；可使p逐渐接近计算目标。再考虑p，i的初始状态以及能够进行上述操作的条件，可以设计出如右所示算法：,S0:输入n；S1:1p;S2:0i;S3:i+1i;S4:pip;S5:ifinthengotoS3;elseoutputp;要点:部分积的概念及其表示;循环变量及其增量的确定;进入循环的初始值的确定;退出循环的条件。,-,13,类比：计算i(i=1,n)的值S0:输入n；S1:0s;S2:0i;S3:i+1i;S4:s+is;S5:ifinthengotoS3;elseoutputs;,要点:部分和的概念及其表示;循环变量及其增量的确定;进入循环的初始值的确定;退出循环的条件。,-,14,例7.判断20002500年中的每一年是否是闰年?此问题的算法设计思路:假设year是年份,则:S1:year=2000;S2:如果year是闰年则输出year“是闰年”;否则输出year“不是闰年”;S3:year=year+1;S4:如果year=2500则转向S2;否则终止该算法;,要点:逐步求精_逐步细化。,-,15,例8.计算(-1)/i(a=i+1,i=1,n)的值问题的性质:部分和问题,S0:输入n；S1:1sign;S2:1sum;S3:2deno;S4:(-1)signsign;产生当前项符号S5:sign(1/deno)term;生成当前项S6:sum+termsum;累加当前项S7:deno+1deno;产生下一项的分母S8:ifdeno=n要点:当前项正负号的转换thengotoS4;elseoutputsum;,-,16,1.2表达算法的抽象机制,1.从机器语言到高级语言的抽象,高级程序设计语言的主要好处是：,（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。,（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；,（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；,（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；,-,17,2.抽象数据类型,抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。,抽象数据类型带给算法设计的好处有：,（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。,-,18,1.3算法的描述,1.自然语言描述问题：二义性问题。例：1.张先生对李先生讲他的儿子考上了大学。2.下雨天留客天留我不留2.流程图描述结论：用三种控制结构可以描述一切可计算的问题。3.改进的流程图描述原则：单一出入口原则。4.N-S流程图描述,S1,S2,S1,S2,S,con,con,S1S2,yconnS1S2,WhileconS,Suntilcon,S,con,-,19,5.伪代码描述6.程序设计语言描述产生用程序设计语言描述的算法程序是程序设计的最终目标。,-,20,1.4算法复杂性分析,算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性。这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。（通常，让A隐含在复杂性函数名当中）,-,21,最坏情况下的时间复杂性：,最好情况下的时间复杂性：,平均情况下的时间复杂性：,其中DN是规模为N的合法输入的集合；I*是DN中使T(N,I*)达到Tmax(N)的合法输入；是中使T(N,)达到Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入I的概率。,-,22,算法复杂性在渐近意义下的阶：,渐近意义下的记号：O、o设f(N)和g(N)是定义在正数集上的正函数。,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)=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)。,-,23,的定义：如果存在正的常数C和自然数N0，使得当NN0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它的一个下界，记为f(N)=(g