高中信息技术 全国青少年奥林匹克联赛教案 递推法 (2).doc

算法在信息学奥赛中的应用 (递推法)所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。可用递推算法求解的题目一般有以下二个特点：（1） 问题可以划分成多个状态；（2） 除初始状态外，其它各个状态都可以用固定的递推关系式来表示。在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。递推法应用例1骑士游历:（noip1997tg）设有一个n*m的棋盘(2=n=50,2=m(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，对于一个nm的棋盘，i的值从1到n，j的值从1到m。棋盘上的任意点都可以用坐标(i,j)表示。对于马的移动方法，我们用k来表示四种移动方向(1,2,3,4)；而每种移动方法用偏移值来表示，并将这些偏移值分别保存在数组dx和dy中，如下表 kdxkdyk12122-131241-2 根据马走的规则，马可以由（i-dxk,j-dyk）走到(i,j)。只要马能从（1，1）走到（i-dxk,j-dyk），就一定能走到（i,j）,马走的坐标必须保证在棋盘上。我们以（n,m）为起点向左递推，当递推到（i-dxk,j-dyk）的位置是（1，1）时，就找到了一条从（1，1）到（n,m）的路径。我们用一个二维数组a表示棋盘，对于任务一，使用倒推法，从终点(n,m)往左递推， 设初始值an,m为（-1，-1），如果从(i,j)一步能走到(n,m)，就将(n,m)存放在ai,j中。如下表，a3,2和a2,3的值是（4，4），表示从这两个点都可以到达坐标（4,4）。从（1,1）可到达（2，3）、（3，2）两个点，所以a1,1存放两个点中的任意一个即可。递推结束以后，如果a1,1值为(0,0)说明不存在路径，否则a1,1值就是马走下一步的坐标，以此递推输出路径。-1,-14,44,42,3任务一的源程序：const dx:array1.4of integer=(2,2,1,1); dy:array1.4of integer=(1,-1,2,-2);type map=record x,y:integer; end;var i,j,n,m,k:integer; a:array0.50,0.50of map;begin read(n,m); fillchar(a,sizeof(a),0); an,m.x:=-1;an,m.y:=-1;标记为终点 for i:=n downto 2 do 倒推 for j:=1 to m do if ai,j.x0 then for k:=1 to 4 do begin ai-dxk,j-dyk.x:=i; ai-dxk,j-dyk.y:=j; end; if a1,1.x=0 then writeln(no) else begin存在路径 i:=1;j:=1; write(,i,j,); while ai,j.x-1 dobegin k:=i;i:=ai,j.x;j:=ak,j.y; write(-(,i,j,); end; end;end.对于任务二，也可以使用递推法，用数组ai,j存放从起点(x1,y1)到（i,j）的路径总数，按同样的方法从左向右递推，一直递推到（x2,y2），ax2,y2即为所求的解。源程序（略）在上面的例题中，递推过程中的某个状态只与前面的一个状态有关，递推关系并不复杂，如果在递推中的某个状态与前面的所有状态都有关，就不容易找出递推关系式，这就需要我们对实际问题进行分析与归纳，从中找到突破口，总结出递推关系式。我们可以按以下四个步骤去分析：（1）细心的观察；（2）丰富的联想；（3）不断地尝试；（4）总结出递推关系式。下面我们再看一个复杂点的例子。例2、栈（noip2003pj）题目大意：求n个数通过栈后的排列总数。（1n18）如输入 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:array0.18of longint; n,i,j:integer;begin readln(n); fillchar(a,sizeof(a),0); a0:=1; for i:=1 to n do for