《算法引论概要.pptx》由会员分享，可在线阅读，更多相关《算法引论概要.pptx（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、主要内容介绍主要内容介绍第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法第7章概率算法第8章NP完全性理论第9章近似算法第10章算法优化策略第1页/共23页第1章 算法引论 1.1 算法与程序1.算法设计实例例1.按递增次序生成M的最小的n个元素，M定义为：1 M xM，则 y=2x+1 My=3x+1 M本章主要知识点1.1算法与程序1.2表达算法的抽象机制1.3描述算法1.4算法复杂性分析第2页/共23页 0 1 2 3 4 5 6 7 8 9 p2p3 i 1 3 4 7 13if(2*mp2=3*mp3)mi=2*mp2+1;p2+;p3+;e
2、lse if(2*mp23*mp3)mi=2*mp2+1;p2+;else mi=3*mp3+1;p3+;i+;算法核心算法设计思想第3页/共23页#include#define s 100main()int n,p2,p3,i,ms;m1=p2=p3=1;scanf(%d,&n);for(i=2;i=n;i+)if(2*mp2=3*mp3)mi=2*mp2+1;p2+;p3+;else if(2*mp23*mp3)mi=2*mp2+1;p2+;else mi=3*mp3+1;p3+;printf(n);for(i=1;i=n;i+)printf(%4d,mi);if(!(i%10)print
3、f(n);#include#include#define eps 1e-6main()float e,t;/*当前项t*/int i,n;/*i的阶乘n*/e=t=1.0;i=n=1;while(fabs(t)eps)e+=t;/*加当前项*/i+=1;n*=i;/*计算i的阶乘*/t=1/n;/*计算下一项*/printf(e=%fn,e);例2.计算e的值第4页/共23页例3.螺旋方阵 的生成10131112252120191817161514987654321242322#define M 64main()int i,j,num,n,aMM;num=1;scanf(%d,&n);if(n
4、M)exit(0);for(i=0;in/2;i+)for(j=i;jn-i-1;j+)aij=num+;for(j=i;ji;j-)an-i-1j=num+;for(j=n-i-1;ji;j-)aji=num+;if(n%2=1)aij+1=num;for(i=0;in;i+)for(j=0;jn;j+)printf(%5d,aij);printf(n);第5页/共23页例4.方阵的旋转10131112252120191817161514987654321242322 aijji jn-i+1 an-i+1jtempfor(j=i;jn-i+1;j+)temp=aij;aij=ajn-i-1
5、;ajn-i-1=an-i-1n-j-1;an-i-1n-j-1=an-j-1i;an-j-1i=temp;第6页/共23页#include#define M 64main()int i,j,temp,n,aMM;scanf(%d,&n);if(nM)exit(0);for(i=0;in;i+)for(j=0;jn;j+)scanf(%d,&aij);for(i=0;in/2;i+)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;for(i=0;in;i+)f
6、or(j=0;jM|!(n%2)exit(0);for(i=0;in;i+)for(j=0;jn;j+)aij=0;i=0;j=n/2;aij=1;for(num=2;num=n*n;num+)i-;j+;if(i=-1&j=n)i=1;j=n-1;else if(i=-1)i=n-1;else if(j=n)j=0;if(aij!=0)i=i+2;j=j-1 aij=num;for(i=0;in;i+)for(j=0;jn;j+)printf(%5d,aij);printf(n);第8页/共23页 2.算法设计方法与实践 递归方法 分治方法 动态规划方法 贪心方法 回溯方法 分支限界方法 概
7、率方法 NP完全性 近似方法 算法优化方法第9页/共23页 3.算法的概念 算法是为解决某个特定问题而设计的由一些命令组成的序列，该序列具备5大特征：1.有穷性 算法中命令的个数是有限的；每个命令 的执行时间是有限的。2.确定性 算法中每个命令的含义是确切的。3.有效性 算法中每个命令是可行的。4.输入 算法需要从外界接受数据,且个数0。5.输出 算法必须产生一组数据作为其结果，且 个数0。第10页/共23页 4.简单算法举例例6.计算12345的值。推广：计算 i (i=1,n)的值。分析：为了计算 12(i-1)i(i+1)n，我们不妨设 p=12 i 并称p为部分积。此时，对于当前的i,
8、若做操作 i+1i,然后对部分积p做操作 p i p，则p的值顺增一个因子。因此，反复进行 i+1i；p i p；可使p逐渐接近计算目标。再考虑 p，i 的初始状态以及能够进行上述操作的条件，可以设计出如右所示算法：S0:输入n；S1:1 p;S2:0 i;S3:i+1i;S4:p i p;S5:if i n then goto S3;else output p;要点要点:部分积的概念及其表示;循环变量及其增量的确定;进入循环的初始值的确定;退出循环的条件。第11页/共23页类比：计算i(i=1,n)的值S0:输入n；S1:0 s;S2:0 i;S3:i+1i;S4:s+i s;S5:if i
9、 n then goto S3;else output s;要点要点:部分和的概念及其表示;循环变量及其增量的确定;进入循环的初始值的确定;退出循环的条件。第12页/共23页例7.判断20002500年中的每一年是否是闰年?此问题的算法设计思路:假设year是年份,则:S1:year=2000;S2:如果 year 是闰年 则 输出year“是闰年”;否则 输出year“不是闰年”;S3:year=year+1;S4:如果 year=2500 则 转向S2;否则 终止该算法;要点:逐步求精_逐步细化。第13页/共23页例8.计算(-1)/i(a=i+1,i=1,n)的值问题的性质:部分和问题S
10、0:输入n；S1:1sign;S2:1sum;S3:2 deno;S4:(-1)signsign;产生当前项符号S5:sign(1/deno)term;生成当前项S6:sum+term sum;累加当前项S7:deno+1 deno;产生下一项的分母S8:if deno=n 要点:当前项正负号的转换 then goto S4;else output sum;第14页/共23页1.2 表达算法的抽象机制1.从机器语言到高级语言的抽象高级程序设计语言的主要好处是：高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发）把繁杂琐碎的事务交给编译程序，所以自动化程度高
11、，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计
12、算机硬件关系不大，）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；因而所写出来的程序可植性好、重用率高；第15页/共23页2.抽象数据类型 抽象数据类型是算法的一个数据模型连同定义在该模型上抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。并作为算法构件的一组运算。抽象数据类型抽象数据类型带给算法设计的带给算法设计的好处好处有有：（1 1）算法顶层设计与底层实现分离；）算法顶层设计与底层实现分离；（2 2）算法设计与数据结构设计隔开，允许数据结构自由选择；）算法设计与数据结构设计隔开，允许数据结构自由选择；（3 3）数据模
13、型和该模型上的运算统一在）数据模型和该模型上的运算统一在ADTADT中，便于空间和时间耗中，便于空间和时间耗费的折衷；费的折衷；（4 4）用抽象数据类型表述的算法具有很好的可维护性；）用抽象数据类型表述的算法具有很好的可维护性；（5 5）算法自然呈现模块化；）算法自然呈现模块化；（6 6）为自顶向下逐步求精和模块化提供有效途径和工具；）为自顶向下逐步求精和模块化提供有效途径和工具；（7 7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。的分析。第16页/共23页1.3 算法的描述1.自然语言描述问题：二义性问题。例：1.张先生
14、对李先生讲他的儿子考上了大学。2.下雨天留客天留我不留2.流程图描述 结论：用三种控制结构可以描述一切可计算的问题。3.改进的流程图描述原则：单一出入口原则。4.N-S流程图描述S1S2S1S2SconconS1S2y con n S1 S2While con S S until conScon第17页/共23页5.伪代码描述6.程序设计语言描述 产生用程序设计语言描述的算法程序是程序设计的最终目标。第18页/共23页1.4 算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性。这个量应该是只依赖于算法要解的问题的规模、算法
15、的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(N,I)和S=S(N,I)。（通常，让A隐含在复杂性函数名当中）第19页/共23页最坏情况下的时间复杂性：最坏情况下的时间复杂性：最好情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间复杂性：平均情况下的时间复杂性：其中其中D DN N是规模为是规模为N N的合法输入的集合；的合法输入的集合；I I*是是D DN N中使中使T(N,IT(N,I*)达到达到T Tmaxmax
16、(N)(N)的合法输入；的合法输入；是中使是中使T(N,)T(N,)达到达到T Tminmin(N)(N)的合法的合法输入；而输入；而P(I)P(I)是在算法的应用中出现输入是在算法的应用中出现输入I I的概率。的概率。第20页/共23页算法复杂性在渐近意义下的阶：算法复杂性在渐近意义下的阶：渐近意义下的记号：渐近意义下的记号：O O、o o 设设f(N)f(N)和和g(N)g(N)是定义在正数集上的正函数。是定义在正数集上的正函数。O O的定义的定义：如果存在正的常数：如果存在正的常数C C和自然数和自然数N N0 0，使得当，使得当N N N N0 0时有时有f(N)f(N)C Cg(N)
17、g(N)，则称函数，则称函数f(N)f(N)当当N N充分大时上有界，且充分大时上有界，且g(N)g(N)是它的一是它的一个上界，记为个上界，记为f(N)=O(g(N)f(N)=O(g(N)。即。即f(N)f(N)的阶不高于的阶不高于g(N)g(N)的阶。的阶。根据根据O O的定义，的定义，容易证明它有如下运算规则：容易证明它有如下运算规则：(1)O(f)+O(g)=O(max(f,g)(1)O(f)+O(g)=O(max(f,g)；(2)O(f)+O(g)=O(f+g)(2)O(f)+O(g)=O(f+g)；(3)O(f)O(g)=O(fg)(3)O(f)O(g)=O(fg)；(4)(4)如
18、果如果g(N)=O(f(N)g(N)=O(f(N)，则，则O(f)+O(g)=O(f)O(f)+O(g)=O(f)；(5)O(Cf(N)=O(f(N)(5)O(Cf(N)=O(f(N)，其中，其中C C是一个正的常数；是一个正的常数；(6)f=O(f)(6)f=O(f)。第21页/共23页 的定义的定义：如果存在正的常数：如果存在正的常数C C和自然数和自然数N N0 0，使得当，使得当N N N N0 0时时有有f(N)f(N)C Cg(N)g(N)，则称函数，则称函数f(N)f(N)当当N N充分大时下有界，且充分大时下有界，且g(N)g(N)是它是它的一个下界，记为的一个下界，记为f(N
19、)=f(N)=(g(N)(g(N)。即。即f(N)f(N)的阶不低于的阶不低于g(N)g(N)的阶。的阶。的定义的定义：定义：定义f(N)=f(N)=(g(N)(g(N)当且仅当当且仅当f(N)=O(g(N)f(N)=O(g(N)且且f(N)=f(N)=(g(N)(g(N)。此时称。此时称f(N)f(N)与与g(N)g(N)同阶。同阶。o o的定义的定义：对于任意给定的：对于任意给定的0 0，都存在正整数，都存在正整数N N0 0，使得，使得当当N N N0N0时有时有f(N)f(N)/C/Cg(N)g(N),则称函数则称函数f(N)f(N)当当N N充分大时的阶比充分大时的阶比g(N)g(N)低，记为低，记为f(N)=o(g(N)f(N)=o(g(N)。例如，例如，4NlogN+7=o(3N4NlogN+7=o(3N2 2+4NlogN+7)+4NlogN+7)。第22页/共23页感谢您的观看！第23页/共23页