资源描述：
《基本算法1-枚举法复习课程.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、信息学奥赛中的基本算法一、枚举法一、算法相关知识从广义上讲，算法是指为解决一个问题而采用的方法和步骤。从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解决特定的问题而构成的各种逻辑组合。程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂。算法的基本特征有穷性：一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是个死循环；确切性：算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。如
2、在算法中不允许有“计算8/0”或“将7或8与x相加”之类的运算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。输入：一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。如在5个数中找出最小的数，则有5个输入。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设计的目的。它们是同输入有着某种特定关系的量。如上述在5个数中找出最小的数，它的输出为最小的数。如果一个程序没有输出，这个程序就毫无意义了；可行性：算法中每一步运算应该是
3、可行的。算法原则上能够精确地运行，而且人能用笔和纸做有限次运算后即可完成。如何评价算法的好坏？时间复杂度：算法运行所占用的时间空间复杂度：算法运行时所占用的空间信息学奥赛中，对程序的运行时间作出了严格的限制，如果运行时间超出了限定就会判错，因此在设计算法时首先要考虑的是时间因素，必要时可以以牺牲空间来换取时间1.fori:=1to100doforj:=1to100dos[i,j]:=0;执行次数100*100次，时间复杂度O(1)2.fori:=1tondoforj:=1to200dos[i,j]:=0;执行次数
4、n*200次，时间复杂度O(n)3.fori:=1tondoforj:=1tondiv2dos[i,j]:=0;执行次数n*n/2次，时间复杂度O(n^2)4.fori:=1tondoforj:=1ton-1dofork:=1ton-2dos[i,j,k]:=0;执行次数n*(n-1)*(n-2)次，时间复杂度O(n^3)时间复杂度怎么算？5.fori:=1tondobeginforj:=1tondos[i,j,0]:=0;forj:=1tondofork:=1tondos[i,j,k]:=1;end;执行次数n
5、*(n+n*n)次，时间复杂度O(n^3)按数量级递增排列，常见的时间复杂度有：常数阶O(1)对数阶O(logn)线性阶O(n),线性对数阶O(nlogn)平方阶O(n^2)立方阶O(n^3)...k次方阶O(n^k),指数阶O(2^n)用例子说明一下改进算法对降低时间复杂度的好处。 例：求N！所产生的数后面有多少个0（中间的0不计）算法一：从1乘到n，每乘一个数判断一次，若后面有0则去掉后面的0，并记下0的个数。为了不超出数的表示范围，去掉与生成0无关的数，只保留有效位数，当乘完n次后就得到0的个数。var i
6、,t,n,sum:longint;begint:=0;sum:=1;readln(n);fori:=1tondobeginsum:=sum*i;whilesummod10=0dobeginsum:=sumdiv10;inc(t);{计数器增加1}end;sum:=summod1000;{舍去与生成0无关的数}end;writeln(t:6);end.时间复杂度为O（N）例：求N！所产生的数后面有多少个0（中间的0不计）算法二：此题中生成0的个数只与含5的个数有关，n！的分解数中含5的个数就等于末尾0的个数，因此问
7、题转化为直接求n！的分解数中含5的个数。vart,n:integer;beginreadln(n);t:=0;repeatn:=ndiv5;inc(t,n);{计数器增加n}untiln<5;writeln(t:6);end.时间复杂度为O（logN）在程序设计中，我们经常需要根据给定的一组条件求满足条件的解。如果问题的解可以用公式，或者按一定的规则、规律求出，那么就可以很容易地写出相应的程序。但是对于许多问题，我们都难以找到明确的公式和计算规则，在这种情况下，我们可以利用计算机高速运算的特点，用穷举法来求解。枚
8、举法（穷举法）基本思想：穷举也叫枚举，它的基本思想是先依据题目的部分条件将所有可能解列举出来，然后用其余的条件对所有可能解进行一一验证，删去那些不符合条件的解，剩下符合条件的解就是整个问题的解。适用枚举法求解的问题必须满足两个条件:1、可事先确定解元素的个数n；2、解变量Ａ１，Ａ２，…，Ａn的可能值为一个连续的值域。例1:百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡
