《信息学奥赛——算法入门教程》由会员分享，可在线阅读，更多相关《信息学奥赛——算法入门教程（35页珍藏版）》请在金锄头文库上搜索。
1、细心整理全国青少年信息学奥林匹克联赛算法讲义算法根底篇1算法具有五个特征：2信息学奥赛中的根本算法(枚举法)4接受枚举算法解题的根本思路：4枚举算法应用4信息学奥赛中的根本算法(回溯法)7回溯根本思想7信息学奥赛中的根本算法(递归算法)10递归算法的定义：10递归算法应用10算法在信息学奥赛中的应用 (递推法)13递推法应用14算法在信息学奥赛中的应用 (分治法)17分治法应用18信息学奥赛中的根本算法(贪心法)20贪心法应用21算法在信息学奥赛中的应用搜寻法一24搜寻算法应用24算法在信息学奥赛中的应用搜寻法二28广度优先算法应用29算法在信息学奥赛中的应用动态规划法32动态规划算法应用33
2、算法根底篇学习过程序设计的人对算法这个词并不生疏，从广义上讲，算法是指为解决一个问题而接受的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂，一个好的程序必需有一个好的算法，一个没有有效算法的程序就像一个没有灵魂的躯体。算法具有五个特征：1、有穷性： 一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是个死循环； 2、精确性： 算法的每一步骤必需有精确的定义，读者理解时不会产生二义性。并且，在任何条件下，算法
3、只有唯一的一条执行路径，对于一样的输入只能得出一样的输出。如在算法中不允许有“计算8/0”或“将7或8与x相加”之类的运算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。 3、输入：一个算法有0个或多个输入，以描述运算对象的初始状况，所谓0个输入是指算法本身定义了初始条件。如在5个数中找出最小的数，那么有5个输入。4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设计的目的。它们是同输入有着某种特定关系的量。如上述在5个数中找出最小的数，它的出输出为最小的数。假如一个程序没有输出，这个程序就毫无意义了； 5、可行性： 算法中每一步运算应当是
4、可行的。算法原那么上能够精确地运行，而且人能用笔和纸做有限次运算后即可完成。 如何来评价一个算法的好坏呢？主要是从两个方面：一是看算法运行所占用的时间；我们用时间困难度来衡量，例如：在以下3个程序中，1x:=x+12for i:=1 to n do x:=x+13for i:=1 to n do for j:=1 to n do x:=x+1含根本操作“x增1”的语句x:=x+1的出现的次数分别为1，n和n2那么这三个程序段的时间困难度分别为O1，On，On2，分别称为常量阶、线性阶和平方阶。在算法时间困难度的表示中，还有可能出现的有：对数阶O(log n)，指数阶O(2n)等。在n很大时，不
5、同数量级的时间困难度有：O(1) O(log n)O(n) O(nlog n)O(n2) O(n3) O(2n)，很明显，指数阶的算法不是一个好的算法。二是看算法运行时所占用的空间，既空间困难度。由于当今计算机硬件技术开展很快，程序所能支配的自由空间一般比拟充分，所以空间困难度就不如时间困难度那么重要了，有许多问题人们主要是探究其算法的时间困难度，而很少探讨它的空间消耗。时间困难性和空间困难性在必需条件下是可以相互转化的。在中学生信息学奥赛中，对程序的运行时间作出了严格的限制，假如运行时间超出了限定就会判错，因此在设计算法时首先要考虑的是时间因素，必要时可以以牺牲空间来换取时间，动态规划法就是
6、一种以牺牲空间换取时间的有效算法。对于空间因素，视题目的要求而定，一般可以不作太多的考虑。我们通过一个简洁的数值计算问题，来比拟两个不同算法的效率在这里只比拟时间困难度。例：求N！所产生的数后面有多少个0中间的0不计。算法一：从1乘到n，每乘一个数判定一次，假设后面有0那么去掉后面的0，并登记0的个数。为了不超出数的表示范围，去掉与生成0无关的数，只保存有效位数，当乘完n次后就得到0的个数。pascal程序如下vari,t,n,sum:longint; begint:=0; sum:=1;readln(n);for i:=1 to n dobegin sum:=sum*i; while sum
7、 mod 10=0 do begin sum:=sum div 10; inc(t);计数器增加1 end; sum:=sum mod 1000;舍去与生成0无关的数end;writeln(t:6);end.算法二：此题中生成O的个数只与含5的个数有关，n！的分解数中含5的个数就等于末尾O的个数，因此问题转化为干脆求n！的分解数中含5的个数。var t,n:integer;begin readln(n);t:=0;repeat n:=n div 5 ; inc(t,n); 计数器增加nuntil n5;writeln(t:6);end.分析比照两种算法就不难看出，它们的时间困难度分别为ON、O
8、logN,算法二的执行时间远远小于算法一的执行时间。在信息学奥赛中，其主要任务就是设计一个有效的算法，去求解所给出的问题。假如仅仅学会一种程序设计语言，而没学过算法的选手在竞赛中是不会取得好的成果的，选手水平的凹凸在于能否设计出好的算法。下面，我们依据全国分区联赛大纲的要求，一起来探讨信息学奥赛中的根本算法。信息学奥赛中的根本算法(枚举法)枚举法，时时称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。接受枚举算法解题的根本思路：（1） 确定枚举对象、枚举范围和判定条件；（2） 一一枚举可能的解，验证是否是问题的解
9、下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。枚举算法应用例1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。此时此刻，请你编一程序，帮他打算一下，怎么样买法，才能刚好用一百块钱买一百只鸡？算法分析：此题很明显是用枚举法，我们以三种鸡的个数为枚举对象分别设为x,y,z,以三种鸡的总数x+y+z和买鸡用去的钱的总数(x*3+y*2+z)为判定条件，穷举各种鸡的个数。下面是解这个百鸡问题的程序var x,y,z:integer;beginfor x:=0 to 100 do
10、 for y:=0 to 100 dofor z:=0 to 100 do枚举全部可能的解if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then writeln(x=,x,y=,y,z=,z); 验证可能的解，并输出符合题目要求的解end.上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡x,y，第三种鸡就可以依据约束条件求得z=100-x-y，这样就缩小了枚举范围，请看下面的程序：var x,y,z:integer;begin for x:=0 to 100 dofor y:=0 to 100-x dobegin z:=
11、100-x-y; if (x*3+y*2+z div 3=100)and(z mod 3=0)then writeln(x=,x,y=,y,z=,z);end;end.未经优化的程序循环了1013 次，时间困难度为O(n3)；优化后的程序只循环了102*101/2次 ，时间困难度为O(n2)。从上面的比照可以看出，对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。在枚举算法中，枚举对象的选择也是特殊重要的，它干脆影响着算法的时间困难度，选择适当的枚举对象可以获得更高的效率。如下例：例2、将1,2.9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,
12、试求出全部满足条件的三个三位数.例如:三个三位数192,384,576满足以上条件.(NOIP1998pj)算法分析：这是1998年全国分区联赛普及组试题简称NOIP1998pj，以下同。此题数据规模不大，可以进展枚举，假如我们不加思地以每一个数位为枚举对象，一位一位地去枚举：for a:=1 to 9 do for b:=1 to 9 dofor i:=1 to 9 do这样下去，枚举次数就有9次，假如我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围就削减为，在微小环节上再进一步优化，枚举范围就更少了。程序如下：var t,x:integer; s,st:string; c:ch
13、ar;begin for x:=123 to 321 do枚举全部可能的解 begin t:=0; str(x,st);把整数x转化为字符串，存放在st中 str(x*2,s); st:=st+s; str(x*3,s); st:=st+s; for c:=1 to 9 do枚举9个字符，判定是否都在st中 if pos(c,st)0 then inc(t) else break;假如不在st中，那么退出循环if t=9 then writeln(x, ,x*2, ,x*3); end;end.在枚举法解题中，判定条件的确定也是很重要的，假如约束条件不对或者不全面，就穷举不出正确的结果，我们再
14、看看下面的例子。例 一元三次方程求解(noip2001tg)问题描述 有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的确定值=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。提示：记方程f(x)=0，假设存在2个数x1和x2，且x1x2，f(x1)*(x2)0，那么在(x1，x2)之间必需有一个根。样例输入：1 -5 -4 20输出：-2.00 2.00 5.00算法分析：由题目的提示很符合二分法求解的原理，所以此题可以用二分法。用二分法解题相对于枚举法来说很要困难许多。此题是否能用枚举法求解呢？再分析一下题目，根的范围在-100到100之间，结果只要保存两位小数，我们不妨将根的值域扩大100倍-10000=x=10000，再以根为枚举对象，枚举范围是-10000到10000，用原方程式进展一一验证，找出方程的解。有的同学在竞赛中是这样做var k:integer; a,b,c,d,x :real;begin read(a,b,c,d); for k:=-10000 to 10000 do begin x
