《2022年高中信息技术 全国青少年奥林匹克联赛教案 递推法》由会员分享，可在线阅读，更多相关《2022年高中信息技术 全国青少年奥林匹克联赛教案 递推法（4页珍藏版）》请在装配图网上搜索。
1、2022年高中信息技术 全国青少年奥林匹克联赛教案 递推法
所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
可用递推算法求解的题目一般有以下二个特点：
（1） 问题可以划分成多个状态；
（2） 除初始状态外，其它各个状态都可以用固定的递推关系式来表示。
在我们实际解题中，题目不会直接给出递推关系式，而是需要通过分析各种状态，找出递推关系式。
递推法应用
例1骑士游历:（noip1997tg）
设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如下图,在
2、棋盘上任一点有一个中国象棋马,
马走的规则为: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,起
3、点坐标,终点坐标)
输出格式:路径数目(若不存在从起点到终点的路径,输出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
4、，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]存放两个
5、点中的任意一个即可。递推结束以后，如果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;
6、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
7、:=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）的路径总数，按同样的方法
8、从左向右递推，一直递推到（x2,y2），a[x2,y2]即为所求的解。源程序（略）
在上面的例题中，递推过程中的某个状态只与前面的一个状态有关，递推关系并不复杂，如果在递推中的某个状态与前面的所有状态都有关，就不容易找出递推关系式，这就需要我们对实际问题进行分析与归纳，从中找到突破口，总结出递推关系式。我们可以按以下四个步骤去分析：（1）细心的观察；（2）丰富的联想；（3）不断地尝试；（4）总结出递推关系式。
下面我们再看一个复杂点的例子。
例2、栈（noipxxpj）
题目大意：求n个数通过栈后的排列总数。（1≤n≤18）
如输入 3 输出 5
算法分析：先模拟入栈、出栈操作
9、，看看能否找出规律，我们用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”,后
10、面一个数为“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.
递推算法最主要的优点是算法结构简单，程序易于实现，难点是从问题的分析中找出解决问题的递推关系式。对于以上两个例子，如果在比赛中找不出递推关系式，也可以用回溯法求解。
2022年高中信息技术 全国青少年奥林匹克联赛教案 递推法
