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

全国青少年信息学奥林匹克联赛

算法讲义

算法基础篇 .................................................................................................................. 2 算法具有五个特征： ............................................................................................. 2 信息学奥赛中的基本算法(枚举法) ............................................................................... 4

采用枚举算法解题的基本思路： ............................................................................ 4 枚举算法应用 ........................................................................................................ 4 信息学奥赛中的基本算法(回溯法) ............................................................................... 7 回溯基本思想 ........................................................................................................ 8 信息学奥赛中的基本算法(递归算法) .......................................................................... 10

递归算法的定义： ............................................................................................... 10 递归算法应用 .......................................................................................................11 算法在信息学奥赛中的应用 (递推法) ........................................................................ 14 递推法应用 ......................................................................................................... 14 算法在信息学奥赛中的应用 (分治法) ........................................................................ 18

分治法应用 ......................................................................................................... 18 信息学奥赛中的基本算法(贪心法) ............................................................................. 21

贪心法应用 ......................................................................................................... 21 算法在信息学奥赛中的应用（搜索法一） ................................................................... 24

搜索算法应用 ...................................................................................................... 25 算法在信息学奥赛中的应用（搜索法二） ................................................................... 28 广度优先算法应用 ............................................................................................... 29 算法在信息学奥赛中的应用（动态规划法） ............................................................... 32

动态规划算法应用 ............................................................................................... 33

算法基础篇

学习过程序设计的人对算法这个词并不陌生，从广义上讲，算法是指为解决一个问题而采用的方法和步骤；从程序计设的角度上讲，算法是指利用程序设计语言的各种语句，为解决特定的问题而构成的各种逻辑组合。我们在编写程序的过程就是在实施某种算法，因此程序设计的实质就是用计算机语言构造解决问题的算法。算法是程序设计的灵魂，一个好的程序必须有一个好的算法，一个没有有效算法的程序就像一个没有灵魂的躯体。

算法具有五个特征：

1、有穷性： 一个算法应包括有限的运算步骤，执行了有穷的操作后将终止运算，不能是个死循环；

2、确切性： 算法的每一步骤必须有确切的定义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，对于相同的输入只能得出相同的输出。如在算法中不允许有“计算8/0”或“将7或8与x相加”之类的运算，因为前者的计算结果是什么不清楚，而后者对于两种可能的运算应做哪一种也不知道。

3、输入：一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。如在5个数中找出最小的数，则有5个输入。

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果，这是算法设计的目的。它们是同输入有着某种特定关系的量。如上述在5个数中找出最小的数，它的出输出为最小的数。如果一个程序没有输出，这个程序就毫无意义了；

5、可行性： 算法中每一步运算应该是可行的。算法原则上能够精确地运行，而且人能用笔和纸做有限次运算后即可完成。

如何来评价一个算法的好坏呢？主要是从两个方面：

一是看算法运行所占用的时间；我们用时间复杂度来衡量，例如：在以下3个程序中，

（1）x:=x+1

（2）for i:=1 to n do

x:=x+1

（3）for i:=1 to n do for j:=1 to n do x:=x+1

2

含基本操作“x增1”的语句x:=x+1的出现的次数分别为1，n和n则这三个程序段的时间复杂度分别为O（1），O（n），O（n2），分别称为常量阶、线性阶和平方阶。在算法时间复杂度的表示中，还有可能出现的有：对数阶O(log n)，指

n

数阶O(2)等。在n很大时，不同数量级的时间复杂度有：O(1)< O(log n)

二是看算法运行时所占用的空间，既空间复杂度。由于当今计算机硬件技术发展很快，程序所能支配的自由空间一般比较充分，所以空间复杂度就不如时间

复杂度那么重要了，有许多问题人们主要是研究其算法的时间复杂度，而很少讨论它的空间耗费。

时间复杂性和空间复杂性在一定条件下是可以相互转化的。在中学生信息学奥赛中，对程序的运行时间作出了严格的限制，如果运行时间超出了限定就会判错，因此在设计算法时首先要考虑的是时间因素，必要时可以以牺牲空间来换取时间，动态规划法就是一种以牺牲空间换取时间的有效算法。对于空间因素，视题目的要求而定，一般可以不作太多的考虑。

我们通过一个简单的数值计算问题，来比较两个不同算法的效率（在这里只比较时间复杂度）。

例：求N！所产生的数后面有多少个0（中间的0不计）。

算法一：从1乘到n，每乘一个数判断一次，若后面有0则去掉后面的0，并记下0的个数。为了不超出数的表示范围，去掉与生成0无关的数，只保留有效位数，当乘完n次后就得到0的个数。（pascal程序如下） var i,t,n,sum:longint; begin

t:=0; sum:=1; readln(n);

for i:=1 to n do begin

sum:=sum*i;

while sum 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); {计数器增加n} until n<5; writeln(t:6); end.

分析对比两种算法就不难看出，它们的时间复杂度分别为O（N）、O（logN）,算法二的执行时间远远小于算法一的执行时间。

在信息学奥赛中，其主要任务就是设计一个有效的算法，去求解所给出的问题。如果仅仅学会一种程序设计语言，而没学过算法的选手在比赛中是不会取得好的成绩的，选手水平的高低在于能否设计出好的算法。

下面，我们根据全国分区联赛大纲的要求，一起来探讨信息学奥赛中的基本算法。

信息学奥赛中的基本算法(枚举法)

枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。

采用枚举算法解题的基本思路：

（1） 确定枚举对象、枚举范围和判定条件； （2） 一一枚举可能的解，验证是否是问题的解

下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。

枚举算法应用

例1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，大鸡三块钱一只，小鸡一块钱三只，不大不小的鸡两块钱一只。现在，请你编一程序，帮他计划一下，怎么样买法，才能刚好用一百块钱买一百只鸡？

算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别设为x,y,z）,以三种鸡的总数（x+y+z）和买鸡用去的钱的总数(x*3+y*2+z)为判定条件，穷举各种鸡的个数。

下面是解这个百鸡问题的程序 var x,y,z:integer; begin

for x:=0 to 100 do for y:=0 to 100 do

for 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 do

for y:=0 to 100-x do begin

z:=100-x-y; if (x*3+y*2+z div writeln('x=',x,'y=',y,'z=',z);

end; end.

3

3=100)and(z mod 3=0)then

未经优化的程序循环了101 次，时间复杂度为O(n)；优化后的程序只循环了（102*101/2）次 ，时间复杂度为O(n2)。从上面的对比可以看出，对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。

在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：

例2、将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.

例如:三个三位数192,384,576满足以上条件.(NOIP1998pj) 算法分析：这是1998年全国分区联赛普及组试题（简称NOIP1998pj，以下同）。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：

for a:=1 to 9 do for b:=1 to 9 do

???

for i:=1 to 9 do

这样下去，枚举次数就有9９次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，穷举的范围就减少为９３，在细节上再进一步优化，枚举范围就更少了。程序如下： var

t,x:integer; s,st:string; c:char; begin

for x:=123 to 321 do{枚举所有可能的解} begin t:=0;

str(x,st);{把整数x转化为字符串，存放在st中} str(x*2,s); st:=st+s;

3