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

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

算法讲义

算法基础篇 1
算法具有五个特征： 2
信息学奥赛中的基本算法(枚举法) 4
采用枚举算法解题的基本思路： 4
枚举算法应用 4
信息学奥赛中的基本算法(回溯法) 7
回溯基本思想 7
信息学奥赛中的基本算法(递归算法) 10
递归算法的定义： 10
递归算法应用 10
算法在信息学奥赛中的应用 (递推法) 13
递推法应用 14
算法在信息学奥赛中的应用 (分治法) 17
分治法应用 18
信息学奥赛中的基本算法(贪心法) 20
贪心法应用 21
算法在信息学奥赛中的应用（搜索法一） 24
搜索算法应用 24
算法在信息学奥赛中的应用（搜索法二） 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
含基本操作“x增1”的语句x:=x+1的出现的次数分别为1，n和n2则这三个程序段的时间复杂度分别为O（1），O（n），O（n2），分别称为常量阶、线性阶和平方阶。在算法时间复杂度的表示中，还有可能出现的有：对数阶O(log n)，指数阶O(2n)等。在n很大时，不同数量级的时间复杂度有：O(1)< O(log n)<O(n)< O(nlog n)<O(n2) <O(n3) <O(2n)，很显然，指数阶的算法不是一个好的算法。
二是看算法运行时所占用的空间，既空间复杂度。由于当今计算机硬件技术发展很快，程序所能支配的自由空间一般比较充分，所以空间复杂度就不如时间复杂度那么重要了，有许多问题人们主要是研究其算法的时间复杂度，而很少讨论它的空间耗费。
时间复杂性和空间复杂性在一定条件下是可以相互转化的。在中学生信息学奥赛中，对程序的运行时间作出了严格的限制，如果运行时间超出了限定就会判错，因此在设计算法时首先要考虑的是时间因素，必要时可以以牺牲空间来换取时间，动态规划法就是一种以牺牲空间换取时间的有效算法。对于空间因素，视题目的要求而定，一般可以不作太多的考虑。
我们通过一个简单的数值计算问题，来比较两个不同算法的效率（在这里只比较时间复杂度）。
例：求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 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的比例,试求出所有满足条件的三个三位数.
例如:三个三位数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;
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.
在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就穷举不出正确的结果， 我们再看看下面的例子。
例３ 一元三次方程求解(noip2001tg)
问题描述 有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。
要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，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:=k/100;
if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,' ');
end;
end.
用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。
这种解法为什么是错的呢？错在哪里？前面的分析好象也没错啊，难道这题不能用枚举法做吗？ 看到这里大家可能有点迷惑了。
在上面的解法中，枚举范围和枚举对象都没有错，而是在验证枚举结果时，判定条件用错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，再代入ax3+bx2+cx+d中，所得的结果也就不一定等于0，因此用原方程ax3+bx2+cx+d=0作为判断条件是不准确的。
我们换一个角度来思考问题，设f(x)=ax3+bx2+cx+d，若x为方程的根，则根据提示可知，必有f(x-0.005)*(x+0.005)<0，如果我们以此为枚举判定条件，问题就逆刃而解。另外，如果f(x-0.005)=0，哪么就说明x-0.005是方程的根，这时根据四舍5入，方程的根也为x。所以我们用(f(x-0.005)*f(x+0.005)<0) 和 (f(x-0.005)=0)作为判定条件。为了程序设计的方便，我们设计一个函数f(x)计算ax3+bx2+cx+d的值，程序如下：
{$N+}
var
k:integer;
a,b,c,d,x:extended;
function f(x:extended):extended; {计算ax3+bx2+cx+d的值}
begin
f:=((a*x+b)*x+c)*x+d;
end;
begin
read(a,b,c,d);
for k:=-10000 to 10000 do
begin
x:=k/100;
if (f(x-0.005)*f(x+0.005)<0) or (f(x-0.005)=0) then write(x:0:2,' '); {若x两端的函数值异号或x-0.005刚好是方程的根，则确定x为方程的根}
end;
end.
用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。但枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。

信息学奥赛中的基本算法(回溯法)

如果上期的“百钱买百鸡”中鸡的种类数是变化的，用枚举法就无能为力了，这里介绍另一种算法——回溯法。
回溯基本思想
回溯法是一种既带有系统性又带有跳跃性的搜索法，它的基本思想是：在搜索过程中，当探索到某一步时，发现原先的选择达不到目标，就退回到上一步重新选择。它主要用来解决一些要经过许多步骤才能完成的，而每个步骤都有若干种可能的分支，为了完成这一过程，需要遵守某些规则，但这些规则又无法用数学公式来描述的一类问题。下面通过实例来了解回溯法的思想及其在计算机上实现的基本方法。
例1、从N个自然数(1,2,…,n)中选出r个数的所有组合。
算法分析：设这r个数为a1,a2,…ar,把它们从大到小排列，则满足：
（1） a1>a2>…>ar;
（2） 其中第i位数(1<=i<=r)满足ai>r-i;
我们按以上原则先确定第一个数，再逐位生成所有的r个数，如果当前数符合要求，则添加下一个数;否则返回到上一个数，改变上一个数的值再判断是否符合要求，如果符合要求，则继续添加下一个数，否则返回到上一个数，改变上一个数的值……按此规则不断循环搜索，直到找出r个数的组合，这种求解方法就是回溯法。
如果按以上方法生成了第i位数ai，下一步的的处理为：
（1） 若ai>r-i且i=r，则输出这r个数并改变ai的值:ai=ai-1;
（2） 若ai>r-i且i≠r，则继续生成下一位ai+1=ai-1;
（3） 若ai<=r-i，则回溯到上一位，改变上一位数的值:ai-1=ai-1-1;
算法实现步骤：
第一步：输入n,r的值，并初始化； i:=1;a[1]:=n;
第二步：若a[1]>r-1则重复：
若a[i]>r-i，①若i=r，则输出解，并且a[i]:=a[i]-1;
②若i<>r，则继续生成下一位：a[i+1]:=a[i]-1; i:=i+1;
若 a[i]<=r-i，则回溯：i:=i-1; a[i]:=a[i]-1;
第三步：结束；
程序实现
var n,r,i,j:integer;
a:array[1..10] of integer;
begin
readln(n,r);i:=1;a[1]:=n;
repeat
if a[i]>r-i then {符合条件 }
if i=r then {输出}
begin
for j:=1 to r do write(a[j]:3);
writeln;
a[i]:=a[i]-1;
end
else {继续搜索}
begin a[i+1]:=a[i]-1; i:=i+1;end
else{回溯}
begin i:=i-1; a[i]:=a[i]-1;end;
until a[1]=r-1;
end.
下面我们再通过另一个例子看看回溯在信息学奥赛中的应用。
例2 数的划分（noip2001tg）
问题描述 整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
输入：n，k (6<n<=200，2<=k<=6)
输出：一个整数，即不同的分法。
样例
输入： 7 3
输出：4 {四种分法为：1,1,5; 1,2,4; 1,3,3; 2,2,3;}
算法分析：此题可以用回溯法求解，设自然数n拆分为a1,a2,…,ak,必须满足以下两个条件：
（1） n=a1+a2+…+ak ；
（2） a1<=a2<=…<=ak (避免重复计算)；
现假设己求得的拆分数为a1,a2,…ai,且都满足以上两个条件,设sum=n-a1-a2-…-ai,我们根据不同的情形进行处理：
（1） 如果i=k,则得到一个解，则计数器t加1，并回溯到上一步，改变ai-1的值；
（2） 如果i<k且sum>=ai,则添加下一个元素ai+1；
（3） 如果i<k且sum<ai,则说明达不到目标，回溯到上一步，改变ai-1的值；
算法实现步骤如下：
第一步：输入自然数n,k并初始化；t:=0; i:=1;a[i]:=1; sum:=n-1; nk:=n div k;
第二步：如果a[1]<=nk 重复：
若i=k，搜索到一个解，计数器t=t+1;并回溯；
否则：①若sum>=a[i]则继续搜索；
②若sum<a[i]则回溯；
搜索时，inc(i);a[i]:=a[i-1];sum:=sum-a[i];
回溯时，dec(i); inc(a[i]); sum:=sum+a[i+1]-1;
第三步：输出。
程序如下：
var
n,nk,sum,i,k:integer;
t:longint;
a:array[1..6]of integer;
begin
readln(n,k);
nk:=n div k;
t:=0; i:=1;a[i]:=1; sum:=n-1;{初始化}
repeat
if i=k then{判断是否搜索到底}
begin inc(t); dec(i);inc(a[i]); sum:=sum+a[i+1]-1; end {回溯}
else begin
if sum>=a[i] then {判断是否回溯}
begin inc(i);a[i]:=a[i-1];sum:=sum-a[i];end{继续搜}
else begin dec(i); inc(a[i]); sum:=sum+a[i+1]-1; end;{回溯}
end;
until a[1]>nk;
writeln(t);
end.

回溯法是通过尝试和纠正错误来寻找答案，是一种通用解题法，在NOIP中有许多涉及搜索问题的题目都可以用回溯法来求解。

信息学奥赛中的基本算法(递归算法)

递归算法的定义：
如果一个对象的描述中包含它本身，我们就称这个对象是递归的，这种用递归来描述的算法称为递归算法。
我们先来看看大家熟知的一个的故事：
从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事，他说……
上面的故事本身是递归的，用递归算法描述：
procedure bonze-tell-story；
begin
if 讲话被打断 then 故事结束
else begin
从前有座山，山上有座庙，庙里有个老和尚在给小和尚讲故事；
bonze-tell-story；
end
end;
从上面的递归事例不难看出，递归算法存在的两个必要条件：
（1） 必须有递归的终止条件；
（2） 过程的描述中包含它本身；
在设计递归算法中，如何将一个问题转化为递归的问题，是初学者面临的难题，下面我们通过分析汉诺塔问题，看看如何用递归算法来求解问题；
递归算法应用
例1：汉诺塔问题，如下图，有A、B、C三根柱子。A柱子上按从小到大的顺序堆放了N个盘子，现在要把全部盘子从A柱移动到C柱，移动过程中可以借助B柱。移动时有如下要求：
（1） 一次只能移动一个盘子；
（2） 不允许把大盘放在小盘上边；
（3） 盘子只能放在三根柱子上；

算法分析：当盘子比较多的时，问题比较复杂，所以我们先分析简单的情况：
如果只有一个盘子，只需一步，直接把它从A柱移动到C柱；
如果是二个盘子，共需要移动3步:
（1） 把A柱上的小盘子移动到B柱;
（2） 把A柱上的大盘子移动到C柱；
（3） 把B柱上的大盘子移动到C柱；
如果N比较大时，需要很多步才能完成，我们先考虑是否能把复杂的移动过程转化为简单的移动过程，如果要把A柱上最大的盘子移动到C柱上去，必须先把上面的N-1个盘子从A柱移动到B柱上暂存，按这种思路，就可以把N个盘子的移动过程分作3大步：
（1） 把A柱上面的N-1个盘子移动到B柱；
（2） 把A柱上剩下的一个盘子移动到C柱；
（3） 把B柱上面的N-1个盘子移动到C柱；
其中N-1个盘子的移动过程又可按同样的方法分为三大步，这样就把移动过程转化为一个递归的过程，直到最后只剩下一个盘子，按照移动一个盘子的方法移动，递归结束。
递归过程：
procedure Hanoi(N,A,B,C:integer;)；{以B柱为中转柱将N个盘子从A柱移动到C柱}
begin
if N=1 then write(A,’->’,C){把盘子直接从A移动到C}
else begin
Hanoi(N-1,A,C,B)；{ 以C柱为中转柱将N-1个盘子从A柱移动到B柱}
write(A,’->’,C)；{把剩下的一个盘子从A移动到C}
Hanoi(N-1,B,A,C)； { 以A柱为中转柱将N-1个盘子从B柱移动到C柱}
end;
end;
从上面的例子我们可以看出，在使用递归算法时，首先弄清楚简单情况下的解法，然后弄清楚如何把复杂情况归纳为更简单的情况。
在信息学奥赛中有的问题的结构或所处理的数据本身是递归定义的，这样的问题非常适合用递归算法来求解，对于这类问题，我们把它分解为具有相同性质的若干个子问题，如果子问题解决了，原问题也就解决了。
例2求先序排列 (NOIP2001pj)
[问题描述]给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。
[样例] 输入：BADC BDCA   输出：ABCD
算法分析：我们先看看三种遍历的定义：
先序遍历是先访问根结点，再遍历左子树，最后遍历右子树；
中序遍历是先遍历左子树，再访问根结点，最后遍历右子树；
后序遍历是先遍历左子树，再遍历右子树，最后访问根结点；
从遍历的定义可知，后序排列的最后一个字符即为这棵树的根节点；在中序排列中，根结点前面的为其左子树，根结点后面的为其右子树；我们可以由后序排列求得根结点，再由根结点在中序排列的位置确定左子树和右子树，把左子树和右子树各看作一个单独的树。这样，就把一棵树分解为具有相同性质的二棵子树，一直递归下去，当分解的子树为空时，递归结束，在递归过程中，按先序遍历的规则输出求得的各个根结点，输出的结果即为原问题的解。
源程序
program noip2001_3;
var　z,h : string;
procedure make(z,h:string); {z为中序排列,h为后序排列}
var　s,m : integer;
begin
m:=length(h);{m为树的长度}
　write(h[m]); {输出根节点}
　s:=pos(h[m],z); {求根节点在中序排列中的位置}
　if s>1 then make(copy(z,1,s-1),copy(h,1,s-1)); {处理左子树}
　if m>s then make(copy(z,s+1,m-s),copy(h,s,m-s)); {处理右子树}
end;
begin
　readln(z);
　readln(h);
　make(z,h);
end.
递归算法不仅仅是用于求解递归描述的问题，在其它很多问题中也可以用到递归思想，如回溯法、分治法、动态规划法等算法中都可以使用递归思想来实现，从而使编写的程序更加简洁。
比如上期回溯法所讲的例2《数的划分问题》，若用递归来求解，程序非常短小且效率很高，源程序如下
var
n,k:integer;
tol:longint;
procedure make(sum,t,d:integer);
var i:integer;
begin
if d=k then inc(tol)
else for i:=t to sum div 2 do make(sum-i,i,d+1);
end;
begin
readln(n,k);
tol:=0;
make(n,1,1);
writeln(tol);
end.

有些问题本身是递归定义的，但它并不适合用递归算法来求解，如斐波那契(Fibonacci)数列，它的递归定义为：
F(n)=1   (n=1,2)
F(n)=F(n-2)+F(n-1) (n>2)
用递归过程描述为：
Funtion fb(n:integer):integer;
Begin
if n<3 then fb:=1
else fb:=fb(n-1)+fb(n-2);
End;
上面的递归过程，调用一次产生二个新的调用，递归次数呈指数增长，时间复杂度为O（2n）,把它改为非递归：
x:=1;y:=1;
for i:=3 to n do
begin
z:=y;y:=x+y;x:=z;
end;
修改后的程序，它的时间复杂度为O（n）。
我们在编写程序时是否使用递归算法，关键是看问题是否适合用递归算法来求解。由于递归算法编写的程序逻辑性强，结构清晰，正确性易于证明，程序调试也十分方便，在NOIP中，数据的规模一般也不大，只要问题适合用递归算法求解，我们还是可以大胆地使用递归算法。

算法在信息学奥赛中的应用 (递推法)

所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
可用递推算法求解的题目一般有以下二个特点：
（1） 问题可以划分成多个状态；
（2） 除初始状态外，其它各个状态都可以用固定的递推关系式来表示。
在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。
递推法应用
例1骑士游历:（noip1997tg）
设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如下图,在棋盘上任一点有一个中国象棋马,

马走的规则为:1.马走日字 2.马只能向右走，即如下图所示:

任务1:当N,M 输入之后,找出一条从左下角到右上角的路径。
例如:输入 N=4,M=4

输出:路径的格式:(1,1)->(2,3)->(4,4)
若不存在路径,则输出"no"
任务2:当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目。
例如:(N=10,M=10),(1,5)(起点),(3,5)(终点)

输出:2(即由(1,5)到(3,5)共有2条路径)
输入格式:n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标)
输出格式:路径数目(若不存在从起点到终点的路径,输出0)
算法分析：为了研究的方便，我们先将棋盘的横坐标规定为i，纵坐标规定为j，对于一个n×m的棋盘，i的值从1到n，j的值从1到m。棋盘上的任意点都可以用坐标(i,j)表示。对于马的移动方法，我们用K来表示四种移动方向(1,2,3,4)；而每种移动方法用偏移值来表示，并将这些偏移值分别保存在数组dx和dy中，如下表
K
Dx[k]
Dy[k]
1
2
1
2
2
-1
3
1
2
4
1
-2
根据马走的规则，马可以由（i-dx[k],j-dy[k]）走到(i,j)。只要马能从（1，1）走到（i-dx[k],j-dy[k]），就一定能走到（i,j）,马走的坐标必须保证在棋盘上。我们以（n,m）为起点向左递推，当递推到（i-dx[k],j-dy[k]）的位置是（1，1）时，就找到了一条从（1，1）到（n,m）的路径。
我们用一个二维数组a表示棋盘，对于任务一，使用倒推法，从终点(n,m)往左递推， 设初始值a[n,m]为（-1，-1），如果从(i,j)一步能走到(n,m)，就将(n,m)存放在a[i,j]中。如下表，a[3,2]和a[2,3]的值是（4，4），表示从这两个点都可以到达坐标（4,4）。从（1,1）可到达（2，3）、（3，2）两个点，所以a[1,1]存放两个点中的任意一个即可。递推结束以后，如果a[1,1]值为(0,0)说明不存在路径，否则a[1,1]值就是马走下一步的坐标，以此递推输出路径。

-1,-1

4,4

4,4

2,3

   任务一的源程序：
const
dx:array[1..4]of integer=(2,2,1,1);
dy:array[1..4]of integer=(1,-1,2,-2);
type
map=record
x,y:integer;
end;
var
i,j,n,m,k:integer;
a:array[0..50,0..50]of map;
begin
read(n,m);
fillchar(a,sizeof(a),0);
a[n,m].x:=-1;a[n,m].y:=-1;{标记为终点}
for i:=n downto 2 do {倒推}
for j:=1 to m do
if a[i,j].x<>0 then
for k:=1 to 4 do
begin
a[i-dx[k],j-dy[k]].x:=i;
a[i-dx[k],j-dy[k]].y:=j;
end;
if a[1,1].x=0 then writeln('no')
else begin{存在路径}
i:=1;j:=1;
write('(',i,',',j,')');
while a[i,j].x<>-1 do
begin
k:=i;
i:=a[i,j].x;j:=a[k,j].y;
write('->(',i,',',j,')');
end;
end;
end.
对于任务二，也可以使用递推法，用数组A[i,j]存放从起点(x1,y1)到（i,j）的路径总数，按同样的方法从左向右递推，一直递推到（x2,y2），a[x2,y2]即为所求的解。源程序（略）
在上面的例题中，递推过程中的某个状态只与前面的一个状态有关，递推关系并不复杂，如果在递推中的某个状态与前面的所有状态都有关，就不容易找出递推关系式，这就需要我们对实际问题进行分析与归纳，从中找到突破口，总结出递推关系式。我们可以按以下四个步骤去分析：（1）细心的观察；（2）丰富的联想；（3）不断地尝试；（4）总结出递推关系式。
下面我们再看一个复杂点的例子。
例2、栈（noip2003pj）
题目大意：求n个数通过栈后的排列总数。（1≤n≤18）
如输入 3 输出 5
算法分析：先模拟入栈、出栈操作，看看能否找出规律，我们用f(n)表示n个数通过栈操作后的排列总数，当n很小时，很容易模拟出f(1)=1；f(2)=2；f(3)=5,通过观察，看不出它们之间的递推关系，我们再分析N=4的情况，假设入栈前的排列为“4321”，按第一个数“4”在出栈后的位置进行分情况讨论：
（1） 若“4”最先输出，刚好与N=3相同，总数为f(3);
（2） 若“4”第二个输出，则在“4”的前只能是“1”，“23”在“4”的后面，这时可以分别看作是N=1和N=2时的二种情况，排列数分别为f(1)和f(2),所以此时的总数为f(1)*f(2);
（3） 若“4”第三个输出，则“4”的前面二个数为“12”,后面一个数为“3”，组成的排列总数为f(2)*f(1);
（4） 若“4”第四个输出，与情况（1）相同，总数为f(3);
所以有：f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3);
若设0个数通过栈后的排列总数为：f(0)=1；
上式可变为：f(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0);
再进一步推导，不难推出递推式：
f(n)=f(0)*f(n-1)+f(1)*f(n-2)+…+f(n-1)*f(0);
即f(n)= (n>=1)
初始值：f(0)=1;
有了以上递推式，就很容易用递推法写出程序。
var
a:array[0..18]of longint;
n,i,j:integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
a[0]:=1;
for i:=1 to n do
for j:=0 to i-1 do a[i]:=a[i]+a[j]*a[i-j-1];
writeln(a[n]);
end.
递推算法最主要的优点是算法结构简单，程序易于实现，难点是从问题的分析中找