信息学奥赛_算法入门教程

《信息学奥赛_算法入门教程》由会员分享，可在线阅读，更多相关《信息学奥赛_算法入门教程（51页珍藏版）》请在金锄头文库上搜索。

1、全国青少年信息学奥林匹克联赛算法讲义算法基础篇 2算法具有五个特征： 2信息学奥赛中的基本算法 （枚举法 ） 6采用枚举算法解题的基本思路： 6枚举算法应用 6信息学奥赛中的基本算法 （回溯法 ） 13回溯基本思想 13信息学奥赛中的基本算法 （递归算法 ） 17递归算法的定义： 17递归算法应用 18算法在信息学奥赛中的应用 （递推法 ） 24递推法应用 25算法在信息学奥赛中的应用 （分治法 ） 31分治法应用 31信息学奥赛中的基本算法 （贪心法 ） 36贪心法应用 37算法在信息学奥赛中的应用（搜索法一） 42搜索算法应用 43算法在信息学奥赛中的应用（搜索法二） 47广度优先算法应用

2、 48算法在信息学奥赛中的应用（动态规划法） 54动态规划算法应用 57算法基础篇学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决 一个问题而采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计 语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的 过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题 的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有 有效算法的程序就像一个没有灵魂的躯体。算法具有五个特征：1、有穷性：一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是个死循环；2、确切性：算法的

3、每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能 得出相同的输出。如在算法中不允许有“计算 8/0 ”或“将 7 或 8 与 x 相加”之 类的运算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做 哪一种也不知道。3 、输入：一个算法有 0 个或多个输入，以描述运算对象的初始情况，所谓 0 个输入是指算法本身定义了初始条件。如在 5 个数中找出最小的数，则有 5 个输 入。4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设计的目的。它们是同输入有着某种特定关系的量。如上述在 5 个数中

4、找 出最小的数，它的出输出为最小的数。如果一个程序没有输出，这个程序就毫无 意义了；5 、可行性： 算法中每一步运算应该是可行的。算法原则上能够精确地运行， 而且人能用笔和纸做有限次运算后即可完成。如何来评价一个算法的好坏呢？主要是从两个方面： 一是看算法运行所占用的时间；我们用时间复杂度来衡量，例如：在以下 3 个程序中，(1) x:=x+1(2 )for i:=1 to n dox:=x+1(3 )for i:=1 to n dofor j:=1 to n dox:=x+1含基本操作“ x 增 1”的语句 x:=x+1 的出现的次数分别为 1，n 和 n2 则这三 个程序段的时间复杂度分别

5、为 O(1)，O(n )，O(n 2)，分别称为常量阶、线性 阶和平方阶。在算法时间复杂度的表示中，还有可能出现的有：对数阶 O(log n) ， 指数阶0(2n)等。在n很大时，不同数量级的时间复杂度有：0(1) O(log n)O(n)v 0(nlog n)O(n 2) 0(n 3) 0(2 n)，很显然，指数阶的算法不是一个好的算法。二是看算法运行时所占用的空间，既空间复杂度。由于当今计算机硬件技术 发展很快，程序所能支配的自由空间一般比较充分，所以空间复杂度就不如时间 复杂度那么重要了，有许多问题人们主要是研究其算法的时间复杂度，而很少讨 论它的空间耗费。时间复杂性和空间复杂性在一定条

6、件下是可以相互转化的。在中学生信息学 奥赛中，对程序的运行时间作出了严格的限制，如果运行时间超出了限定就会判 错，因此在设计算法时首先要考虑的是时间因素，必要时可以以牺牲空间来换取 时间，动态规划法就是一种以牺牲空间换取时间的有效算法。对于空间因素，视 题目的要求而定，一般可以不作太多的考虑。我们通过一个简单的数值计算问题，来比较两个不同算法的效率（在这里只 比较时间复杂度）。例：求N !所产生的数后面有多少个0 （中间的0不计）。算法一：从1乘到n,每乘一个数判断一次，若后面有 0则去掉后面的0,并记下 0 的个数。为了不超出数的表示范围，去掉与生成 0 无关的数，只保留有效位 数，当乘完

7、n 次后就得到 0 的个数。（ pascal 程序如下） var i,t,n,sum:longint;begint:=0; sum:=1;readln（n）;for i:=1 to n dobeginsum:=sum*i;while sum mod 10=0 dobegin sum:=sum div 10;inc(t); 计数器增加 1end;sum:=sum mod 1000; 舍去与生成 0 无关的数 end;writeln(t:6);end.算法二：此题中生成 O 的个数只与含 5 的个数有关， n ！的分解数中含 5 的 个数就等于末尾 O 的个数，因此问题转化为直接求 n ！的分解数

8、中含 5 的个数。 var t,n:integer;beginreadln(n);t:=0;repeatn:=n div 5 ;inc(t,n); 计数器增加 nuntil n5;writeln(t:6);end.分析对比两种算法就不难看出， 它们的时间复杂度分别为 O（N）、O（logN ）, 算法二的执行时间远远小于算法一的执行时间。在信息学奥赛中，其主要任务就是设计一个有效的算法，去求解所给出的问 题。如果仅仅学会一种程序设计语言，而没学过算法的选手在比赛中是不会取得 好的成绩的，选手水平的高低在于能否设计出好的算法。下面，我们根据全国分区联赛大纲的要求，一起来探讨信息学奥赛中的基本算法

9、。信息学奥赛中的基本算法 （枚举法 ）枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题 目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问 题的解。采用枚举算法解题的基本思路：（1 ） 确定枚举对象、枚举范围和判定条件；（2 ） 一一枚举可能的解，验证是否是问题的解下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这 三个方面来探讨如何用枚举法解题。枚举算法应用例 1 ：百钱买百鸡问题： 有一个人有一百块钱， 打算买一百只鸡。 到市场一看， 大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你编一 程序，帮他计划一下，怎么样买法

10、，才能刚好用一百块钱买一百只鸡？算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象(分别 设为 x,y,z ) ,以三种鸡的总数( x+y+z )和买鸡用去的钱的总数 (x*3+y*2+z) 为判 定条件，穷举各种鸡的个数。下面是解这个百鸡问题的程序var x,y,z:integer;beginfor x:=0 to 100 dofor 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); 验

11、证可能的解，并输出符合题目要求的解 end.上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡(x,y )，第三种鸡就可以根据约束条件求得( z=100-x-y )，这样就缩小了枚举范 围，请看下面的程序：var x,y,z:integer;beginfor x:=0 to 100 dofor y:=0 to 100-x dobeginz:=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.未经优化的程序循环了 101 3 次，时间复杂度为 O(n 3)；优化后的程

12、序只循环 了( 102*101/2 )次 ，时间复杂度为 O(n 2)。从上面的对比可以看出，对于枚举 算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间 复杂度，选择适当的枚举对象可以获得更高的效率。如下例：例 2 、将 1,2.9 共 9 个数分成三组 ,分别组成三个三位数 , 且使这三个三位数 构成 1:2:3 的比例 ,试求出所有满足条件的三个三位数 .例如 :三个三位数 192,384,576 满足以上条件 .(NOIP1998pj)算法分析：这是 1998 年全国分区联赛普及组试题(简称 NOIP1998

13、pj ，以下同)。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚 举对象，一位一位地去枚举：for a:=1 to 9 dofor b:=1 to 9 dofor i:=1 to 9 do这样下去，枚举次数就有99次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围就减少为9=在细节上再进一步优化，枚举范围就更少了。程序如下：vart,x:integer;s,st:string;c:char;beginfor x:=123 to 321 do 枚举所有可能的解 begint:=0;str(x,st); 把整数 x 转化为字符串，存放在 st 中str(x*2,

14、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 中，则退出循环 end;end.在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不 全面，就穷举不出正确的结果， 我们再看看下面的例子。例3 元三次方程求解(noip2001tg)问题描述有形如： ax 3+bx 2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数 (a，b ，c ，d 均为实数 )，并约定该方程存在三个不同实根 (根的

15、范围在-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