《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法》由會(huì)員分享，可在線閱讀，更多相關(guān)《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法（4頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法
所謂遞推，是指從已知的初始條件出發(fā)，依據(jù)某種遞推關(guān)系，逐次推出所要求的各中間結(jié)果及最后結(jié)果。其中初始條件或是問(wèn)題本身已經(jīng)給定，或是通過(guò)對(duì)問(wèn)題的分析與化簡(jiǎn)后確定。
可用遞推算法求解的題目一般有以下二個(gè)特點(diǎn)：
（1） 問(wèn)題可以劃分成多個(gè)狀態(tài)；
（2） 除初始狀態(tài)外，其它各個(gè)狀態(tài)都可以用固定的遞推關(guān)系式來(lái)表示。
在我們實(shí)際解題中，題目不會(huì)直接給出遞推關(guān)系式，而是需要通過(guò)分析各種狀態(tài)，找出遞推關(guān)系式。
遞推法應(yīng)用
例1騎士游歷:（noip1997tg）
設(shè)有一個(gè)n*m的棋盤(2<=n<=50,2<=m<=50),如下圖,在
2、棋盤上任一點(diǎn)有一個(gè)中國(guó)象棋馬,
馬走的規(guī)則為:1.馬走日字 2.馬只能向右走，即如下圖所示:
任務(wù)1:當(dāng)N,M 輸入之后,找出一條從左下角到右上角的路徑。
例如:輸入 N=4,M=4
輸出:路徑的格式:(1,1)->(2,3)->(4,4)
若不存在路徑,則輸出"no"
任務(wù)2:當(dāng)N,M 給出之后,同時(shí)給出馬起始的位置和終點(diǎn)的位置,試找出從起點(diǎn)到終點(diǎn)的所有路徑的數(shù)目。
例如:(N=10,M=10),(1,5)(起點(diǎn)),(3,5)(終點(diǎn))
輸出:2(即由(1,5)到(3,5)共有2條路徑)
輸入格式:n,m,x1,y1,x2,y2(分別表示n,m,起
3、點(diǎn)坐標(biāo),終點(diǎn)坐標(biāo))
輸出格式:路徑數(shù)目(若不存在從起點(diǎn)到終點(diǎn)的路徑,輸出0)
算法分析：為了研究的方便，我們先將棋盤的橫坐標(biāo)規(guī)定為i，縱坐標(biāo)規(guī)定為j，對(duì)于一個(gè)n×m的棋盤，i的值從1到n，j的值從1到m。棋盤上的任意點(diǎn)都可以用坐標(biāo)(i,j)表示。對(duì)于馬的移動(dòng)方法，我們用K來(lái)表示四種移動(dòng)方向(1,2,3,4)；而每種移動(dòng)方法用偏移值來(lái)表示，并將這些偏移值分別保存在數(shù)組dx和dy中，如下表
K
Dx[k]
Dy[k]
1
2
1
2
2
-1
3
1
2
4
1
-2
根據(jù)馬走的規(guī)則，馬可以由（i-dx[k],j-dy[k]）走到(i,j)。只要馬能從（1
4、，1）走到（i-dx[k],j-dy[k]），就一定能走到（i,j）,馬走的坐標(biāo)必須保證在棋盤上。我們以（n,m）為起點(diǎn)向左遞推，當(dāng)遞推到（i-dx[k],j-dy[k]）的位置是（1，1）時(shí)，就找到了一條從（1，1）到（n,m）的路徑。
我們用一個(gè)二維數(shù)組a表示棋盤，對(duì)于任務(wù)一，使用倒推法，從終點(diǎn)(n,m)往左遞推， 設(shè)初始值a[n,m]為（-1，-1），如果從(i,j)一步能走到(n,m)，就將(n,m)存放在a[i,j]中。如下表，a[3,2]和a[2,3]的值是（4，4），表示從這兩個(gè)點(diǎn)都可以到達(dá)坐標(biāo)（4,4）。從（1,1）可到達(dá)（2，3）、（3，2）兩個(gè)點(diǎn)，所以a[1,1]存放兩個(gè)
5、點(diǎn)中的任意一個(gè)即可。遞推結(jié)束以后，如果a[1,1]值為(0,0)說(shuō)明不存在路徑，否則a[1,1]值就是馬走下一步的坐標(biāo)，以此遞推輸出路徑。
-1,-1
4,4
4,4
2,3
???任務(wù)一的源程序：
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;{標(biāo)記為終點(diǎn)}
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.
對(duì)于任務(wù)二，也可以使用遞推法，用數(shù)組A[i,j]存放從起點(diǎn)(x1,y1)到（i,j）的路徑總數(shù)，按同樣的方法
8、從左向右遞推，一直遞推到（x2,y2），a[x2,y2]即為所求的解。源程序（略）
在上面的例題中，遞推過(guò)程中的某個(gè)狀態(tài)只與前面的一個(gè)狀態(tài)有關(guān)，遞推關(guān)系并不復(fù)雜，如果在遞推中的某個(gè)狀態(tài)與前面的所有狀態(tài)都有關(guān)，就不容易找出遞推關(guān)系式，這就需要我們對(duì)實(shí)際問(wèn)題進(jìn)行分析與歸納，從中找到突破口，總結(jié)出遞推關(guān)系式。我們可以按以下四個(gè)步驟去分析：（1）細(xì)心的觀察；（2）豐富的聯(lián)想；（3）不斷地嘗試；（4）總結(jié)出遞推關(guān)系式。
下面我們?cè)倏匆粋€(gè)復(fù)雜點(diǎn)的例子。
例2、棧（noipxxpj）
題目大意：求n個(gè)數(shù)通過(guò)棧后的排列總數(shù)。（1≤n≤18）
如輸入 3 輸出 5
算法分析：先模擬入棧、出棧操作
9、，看看能否找出規(guī)律，我們用f(n)表示n個(gè)數(shù)通過(guò)棧操作后的排列總數(shù)，當(dāng)n很小時(shí)，很容易模擬出f(1)=1；f(2)=2；f(3)=5,通過(guò)觀察，看不出它們之間的遞推關(guān)系，我們?cè)俜治鯪=4的情況，假設(shè)入棧前的排列為“4321”，按第一個(gè)數(shù)“4”在出棧后的位置進(jìn)行分情況討論：
（1） 若“4”最先輸出，剛好與N=3相同，總數(shù)為f(3);
（2） 若“4”第二個(gè)輸出，則在“4”的前只能是“1”，“23”在“4”的后面，這時(shí)可以分別看作是N=1和N=2時(shí)的二種情況，排列數(shù)分別為f(1)和f(2),所以此時(shí)的總數(shù)為f(1)*f(2);
（3） 若“4”第三個(gè)輸出，則“4”的前面二個(gè)數(shù)為“12”,后
10、面一個(gè)數(shù)為“3”，組成的排列總數(shù)為f(2)*f(1);
（4） 若“4”第四個(gè)輸出，與情況（1）相同，總數(shù)為f(3);
所以有：f(4)=f(3)+f(1)*f(2)+f(2)*f(1)+f(3);
若設(shè)0個(gè)數(shù)通過(guò)棧后的排列總數(shù)為：f(0)=1；
上式可變?yōu)椋篺(4)=f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0);
再進(jìn)一步推導(dǎo)，不難推出遞推式：
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.
遞推算法最主要的優(yōu)點(diǎn)是算法結(jié)構(gòu)簡(jiǎn)單，程序易于實(shí)現(xiàn)，難點(diǎn)是從問(wèn)題的分析中找出解決問(wèn)題的遞推關(guān)系式。對(duì)于以上兩個(gè)例子，如果在比賽中找不出遞推關(guān)系式，也可以用回溯法求解。
2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞推法
