算法在信息学奥赛中的应用(递推法)所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。可用递推算法求解的题目一般有以下二个特点：（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中，如下表KDx[k]Dy[k]12[122-131241-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,-14,44,42,3任务一的源程序：constdx:array[1..4]ofinteger=(2,2,1,1);dy:array[1..4]ofinteger=(1,-1,2,-2);typemap=recordx,y:integer;end;vari,j,n,m,k:integer;a:array[0..50,0..50]ofmap;beginread(n,m);fillchar(a,sizeof(a),0);a[n,m].x:=-1;a[n,m].y:=-1;{标记为终点}fori:=ndownto2do{倒推}forj:=1tomdoifa[i,j].x<>0thenfork:=1to4dobegina[i-dx[k],j-dy[k]].x:=i;a[i-dx[k],j-dy[k]].y:=j;end;ifa[1,1].x=0thenwriteln('no')elsebegin{存在路径}i:=1;j:=1;write('(',i,',',j,')');whilea[i,j].x<>-1dobegink:=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”，按第一个...
