算法引论概要.pptx

算法设计与分析算法设计与分析（ACM/ICPC程序设计方法论）程序设计方法论）广东江门五邑大学信息学院广东江门五邑大学信息学院 高宏宾2007年年8月月主要内容介绍第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法第7章概率算法第8章NP完全性理论第9章近似算法第10章算法优化策略第第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算法复杂性分析算法复杂性分析 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+;else if(2*mp23*mp3)mi=2*mp2+1;p2+;else mi=3*mp3+1;p3+;i+;算法核心算法设计思想#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)printf(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的值的值例例3.螺旋方阵螺旋方阵 的生成的生成101311122521201918171615149876543212423 22#define M 64main()int i,j,num,n,aMM;num=1;scanf(%d,&n);if(nM)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);例例4.方阵的旋转方阵的旋转101311122521201918171615149876543212423 22 aijji jn-i+1 an-i+1jtempfor(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;#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+)for(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);2.算法设计方法与实践算法设计方法与实践 递归方法递归方法 分治方法分治方法 动态规划方法动态规划方法 贪心方法贪心方法 回溯方法回溯方法 分支限界方法分支限界方法 概率方法概率方法 NP完全性完全性 近似方法近似方法 算法优化方法算法优化方法 3.算法的概念算法的概念 算法是为解决某个特定问题而设计的由一些命令算法是为解决某个特定问题而设计的由一些命令组成的序列，该序列具备组成的序列，该序列具备5大特征：大特征：1.有穷性有穷性 算法中命令的个数是有限的；每个命令算法中命令的个数是有限的；每个命令 的执行时间是有限的。的执行时间是有限的。2.确定性确定性 算法中每个命令的含义是确切的。算法中每个命令的含义是确切的。3.有效性有效性 算法中每个命令是可行的。算法中每个命令是可行的。4.输入输入 算法需要从外界接受数据算法需要从外界接受数据,且个数且个数0。5.输出输出 算法必须产生一组数据作为其结果，且算法必须产生一组数据作为其结果，且 个数个数 0。4.简单算法举例简单算法举例例6.计算12345的值。推广：计算 i (i=1,n)的值。分析：为了计算 12(i-1)i(i+1)n，我们不妨设 p=12 i 并称p为部分积。此时，对于当前的i,若做操作 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;要点要点:部分积的概念及其表示部分积的概念及其表示;循环变量及其增量的确定循环变量及其增量的确定;进入循环的初始值的确定进入循环的初始值的确定;退出循环的条件。退出循环的条件。类比：计算i(i=1,n)的值S0:输入n；S1:0 s;S2:0 i;S3:i+1i;S4:s+i s;S5:if i n then goto S3;else output s;要点要点:部分和的概念及其表部分和的概念及其表示示;循环变量及其增量的循环变量及其增量的确定确定;进入循环的初始值的确进入循环的初始值的确定定;退出循环的条件。退出循环的条件。例7.判断20002500年中的每一年是否是闰年?此问题的算法设计思路:假设year是年份,则:S1:year=2000;S2:如果 year 是闰年 则 输出year“是闰年”;否则 输出year“不是闰年”;S3:year=year+1;S4:如果 year=2500 则 转向S2;否则 终止该算法;要点:逐步求精_逐步细化。例8.计算(-1)/i(a=i+1,i=1,n)的值问题的性质:部分和问题S0:输入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;1.2 表达算法的抽象机制表达算法的抽象机制1.从机器语言到高级语言的抽象从机器语言到高级语言的抽象高级程序设计语言的主要好处是：高级程序设计语言的主要好处是：（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。高程序质量。（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；员只需要几周时间的培训就可以胜任程序员的工作；（2）高级语言为程序员提供了结构化程序设计的环境和工具，使）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；得设计出来的程序可读性好，可维护性强，可靠性高；（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；因而所写出来的程序可植性好、重用率高；2.抽象数据类型抽象数据类型 抽象数据类型是算法的一个数据模型连同定义在该模型上抽象数据类型是算法的一个数据模型连同定义在该模型上并作为算法构件的一组运算。并作为算法构件的一组运算。抽象数据类型抽象数据类型带给算法设计的带给算法设计的好处好处有有：（1 1）算法顶层设计与底层实现分离；）算法顶层设计与底层实现分离；（2 2）算法设计与数据结构设计隔开，允许数据结构自由选择；）算法设计与数据结构设计隔开，允许数据结构自由选择；（3 3）数据模型和该模型上的运算统一在）数据模型和该模型上的运算统一在ADTADT中，便于空间和时间耗中，便于空间和时间耗费的折衷；费的折衷；（4 4）用抽象数据类型表述的算法具有很好的可维护性；）用抽象数据类型表述的算法具有很好的可维护性；（5 5）算法自然呈现模块化；）算法自然呈现模块化；（6 6）为自顶向下逐步求精和模块化提供有效途径和工具；）为自顶向下逐步求精和模块化提供有效途径和工具；（7 7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。的分析。1.3 算法的描述1.自然语言描述自然语言描述问题：问题：二义性问题。二义性问题。例：1.张先生对李先生讲他的儿子考上了大学。2.下雨天留客天留我不留2.流程图描述流程图描述 结论：用三种控制结构可以描述一切可计算的问题。3.改进的流程图描述改进的流程图描述原则：单一出入口原则。4.N-S流程图描述流程图描述S1S2S1S2SconconS1S2y con n S1 S2While con S S until conScon5.伪代码描述伪代码描述6.程序设计语言描述程序设计语言描述 产生用程序设计语言描述的算法产生用程序设计语言描述的算法程序是程序设计程序是程序设计的最终目标。的最终目标。1.4 算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的量，需算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为要时间资源的量称为时间复杂性时间复杂性，需要空间资源的量称为，需要空间资源的量称为空间复杂性空间复杂性。这个量应该是只依赖于算法要解的问题的规。这个量应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用模、算法的输入和算法本身的函数。如果分别用N、I和和A表示算法要解问题的规模、算法的输入和算法本身，而且表示算法要解问题的规模、算法的输入和算法本身，而且用用C表示复杂性，那么，应该有表示复杂性，那么，应该有C=F(N,I,A)。一般把时间。一般把时间复杂性和空间复杂性分开，并分别用复杂性和空间复杂性分开，并分别用T和和S来表示，则来表示，则有：有：T=T(N,I)和和S=S(N,I)。（通常，让。（通常，让A隐含在复杂性函隐含在复杂性函数名当中）数名当中）最坏情况下的时间复杂性：最坏情况下的时间复杂性：最好情况下的时间复杂性：最好情况下的时间复杂性：平均情况下的时间复杂性：平均情况下的时间复杂性：其中其中D DN N是规模为是规模为N N的合法输入的集合；的合法输入的集合；I I*是是D DN N中使中使T(N,IT(N,I*)达到达到T Tmaxmax(N)(N)的合法输入；的合法输入；是中使是中使T(N,)T(N,)达到达到T Tminmin(N)(N)的合法的合法输入；而输入；而P(I)P(I)是在算法的应用中出现输入是在算法的应用中出现输入I I的概率。的概率。算法复杂性在渐近意义下的阶：算法复杂性在渐近意义下的阶：渐近意义下的记号：渐近意义下的记号：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)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)如果如果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)。的定义的定义：如果存在正的常数：如果存在正的常数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)=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)。