基本算法1-枚举法

信息学奥赛中的基本算法,一、枚举法,一、算法相关知识,从广义上讲，算法是指为解决一个问题而采用的方法和步骤。从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解决特定的问题而构成的各种逻辑组合。程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂。,算法的基本特征,有穷性：一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是个死循环；确切性：算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。如在算法中不允许有“计算8/0”或“将7或8与x相加”之类的运算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。输入：一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。如在5个数中找出最小的数，则有5个输入。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设计的目的。它们是同输入有着某种特定关系的量。如上述在5个数中找出最小的数，它的输出为最小的数。如果一个程序没有输出，这个程序就毫无意义了；可行性：算法中每一步运算应该是可行的。算法原则上能够精确地运行，而且人能用笔和纸做有限次运算后即可完成。,如何评价算法的好坏？,时间复杂度：算法运行所占用的时间空间复杂度：算法运行时所占用的空间信息学奥赛中，对程序的运行时间作出了严格的限制，如果运行时间超出了限定就会判错，因此在设计算法时首先要考虑的是时间因素，必要时可以以牺牲空间来换取时间,1.fori:=1to100doforj:=1to100dosi,j:=0;执行次数100*100次，时间复杂度O(1)2.fori:=1tondoforj:=1to200dosi,j:=0;执行次数n*200次，时间复杂度O(n)3.fori:=1tondoforj:=1tondiv2dosi,j:=0;执行次数n*n/2次，时间复杂度O(n2)4.fori:=1tondoforj:=1ton-1dofork:=1ton-2dosi,j,k:=0;执行次数n*(n-1)*(n-2)次，时间复杂度O(n3),时间复杂度怎么算？,5.fori:=1tondobeginforj:=1tondosi,j,0:=0;forj:=1tondofork:=1tondosi,j,k:=1;end;执行次数n*(n+n*n)次，时间复杂度O(n3),按数量级递增排列，常见的时间复杂度有：常数阶O(1)对数阶O(logn)线性阶O(n),线性对数阶O(nlogn)平方阶O(n2)立方阶O(n3).k次方阶O(nk),指数阶O(2n),用例子说明一下改进算法对降低时间复杂度的好处。例：求N！所产生的数后面有多少个0（中间的0不计）,算法一：从1乘到n，每乘一个数判断一次，若后面有0则去掉后面的0，并记下0的个数。为了不超出数的表示范围，去掉与生成0无关的数，只保留有效位数，当乘完n次后就得到0的个数。vari,t,n,sum:longint;begint:=0;sum:=1;readln(n);fori:=1tondobegin,sum:=sum*i;whilesummod10=0dobeginsum:=sumdiv10;inc(t);计数器增加1end;sum:=summod1000;舍去与生成0无关的数end;writeln(t:6);end.,时间复杂度为O（N）,例：求N！所产生的数后面有多少个0（中间的0不计）,算法二：此题中生成0的个数只与含5的个数有关，n！的分解数中含5的个数就等于末尾0的个数，因此问题转化为直接求n！的分解数中含5的个数。vart,n:integer;begin,readln(n);t:=0;repeatn:=ndiv5;inc(t,n);计数器增加nuntiln9999thenbreak;优化语句if（）thenwriteln(y,x);end;end.运行结果：970912,枚举所有可能的除数,验证,穷举法是一种比较笨拙的算法，因为它需要列举出许多个可能解来一一验证，程序往往需要运行很长时间，效率较低。针对穷举法效率较低的缺点，在设计穷举算法时，我们必须注意以下二点：减少枚举变量：充分挖掘各解元素之间的联系，将一些非枚举不可的解元素列为枚举变量，然后在此基础上直接计算出其它解元素的可能值。减少枚举变量的值域：枚举前要尽可能多地将不符合条件的情况预先排除。,809*x+1,(y=1000)and(8*x=100),例3、将1,2.9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.例如:三个三位数192,384,576满足以上条件.,算法分析：此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：fora:=1to9doforb:=1to9dofori:=1to9do这样下去，枚举次数就有9次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围就减少为，在细节上再进一步优化，枚举范围就更少了。,vart,x:integer;s,st:string;c:char;beginforx:=123to321do枚举所有可能的解begint:=0;str(x,st);把整数x转化为字符串，存放在st中str(x*2,s);,st:=st+s;str(x*3,s);st:=st+s;forc:=1to9do枚举9个字符，判断是否都在st中ifpos(c,st)0theninc(t)elsebreak;如果不在st中，则退出循环ift=9thenwriteln(x,x*2,x*3);end;end.,例4:方格填数,如下图所示的八个格子中填入1至8八个数字，使得相邻的和对角线的数字之差不为1。请编程找出所有放法。,分析：由题意可知，放入b3，b6这两个格子中的数，必须和六个数不连续，仅可以和一个数是连续的，这样的数只能是1和8。因此，b1，b3，b6，b8这四个格子中数的放法可以先确定下来：2，8，1，7或7，1，8，2。接着，我们只需枚举b2、b4、b5三个变量，范围都是3至6，而b7可通过计算来得到。(1,2),(1,4),(2,5),(4,7),(5,8),(7,8)共6对格子中的数需要验证。,constlink:array1.6,1.2ofinteger=(1,2),(1,4),(2,5),(4,7),(5,8),(7,8);varb:array1.8ofinteger;存放摆放方案procedureprint;输出一种满足条件的放法beginwriteln(b1:4);writeln(b2:2,b3:2,b4:2);writeln(b5:2,b6:2,b7:2);writeln(b8:4);writeln;end;functionchoose:boolean;检验当前放法是否符合要求vari:integer;beginchoose:=false;fori:=1to6doifabs(blinki,1-blinki,2)=1thenexit;choose:=true;end;,proceduretry;varb2,b4,b5,b7:integer;beginforb2:=3to6do枚举b2，b4，b5，计算b7forb4:=3to6doifb2b4thenforb5:=3to6doif(b5b2)and(b5b4)thenbeginb7:=18-b2-b4-b5;b2:=b2;b4:=b4;b5:=b5;b7:=b7;ifchoosethenprint;end;end;,beginb1:=2;b3:=8;b6:=1;b8:=7;情况一try；b1:=7;b3:=