《2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞歸算法》由會員分享，可在線閱讀，更多相關《2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞歸算法（4頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞歸算法
遞歸算法的定義：
如果一個對象的描述中包含它本身，我們就稱這個對象是遞歸的，這種用遞歸來描述的算法稱為遞歸算法。
我們先來看看大家熟知的一個的故事：
從前有座山，山上有座廟，廟里有個老和尚在給小和尚講故事，他說從前有座山，山上有座廟，廟里有個老和尚在給小和尚講故事，他說……
上面的故事本身是遞歸的，用遞歸算法描述：
procedure bonze-tell-story；
begin
if 講話被打斷 then 故事結束
else begin
從前有座山，山上有座廟，廟里有個老和尚在給小和尚講故事；
2、bonze-tell-story；
end
end;
從上面的遞歸事例不難看出，遞歸算法存在的兩個必要條件：
（1） 必須有遞歸的終止條件；
（2） 過程的描述中包含它本身；
在設計遞歸算法中，如何將一個問題轉化為遞歸的問題，是初學者面臨的難題，下面我們通過分析漢諾塔問題，看看如何用遞歸算法來求解問題；
遞歸算法應用
例1：漢諾塔問題，如下圖，有A、B、C三根柱子。A柱子上按從小到大的順序堆放了N個盤子，現(xiàn)在要把全部盤子從A柱移動到C柱，移動過程中可以借助B柱。移動時有如下要求：
（1） 一次只能移動一個盤子；
（2） 不允許把大盤放在小盤上邊；
（3） 盤子只能放在三根
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柱上
4、剩下的一個盤子移動到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(
5、A,’->’,C)；{把剩下的一個盤子從A移動到C}
Hanoi(N-1,B,A,C)； { 以A柱為中轉柱將N-1個盤子從B柱移動到C柱}
end;
end;
從上面的例子我們可以看出，在使用遞歸算法時，首先弄清楚簡單情況下的解法，然后弄清楚如何把復雜情況歸納為更簡單的情況。
在信息學奧賽中有的問題的結構或所處理的數(shù)據(jù)本身是遞歸定義的，這樣的問題非常適合用遞歸算法來求解，對于這類問題，我們把它分解為具有相同性質(zhì)的若干個子問題，如果子問題解決了，原問題也就解決了。
例2求先序排列 (NOIPxxpj)
[問題描述]給出一棵二叉樹的中序與后序排列。求出它的先序排列。(約定樹結點
6、用不同的大寫字母表示，長度≤8)。
[樣例] 輸入：BADC BDCA?? 輸出：ABCD
算法分析：我們先看看三種遍歷的定義：
先序遍歷是先訪問根結點，再遍歷左子樹，最后遍歷右子樹；
中序遍歷是先遍歷左子樹，再訪問根結點，最后遍歷右子樹；
后序遍歷是先遍歷左子樹，再遍歷右子樹，最后訪問根結點；
從遍歷的定義可知，后序排列的最后一個字符即為這棵樹的根節(jié)點；在中序排列中，根結點前面的為其左子樹，根結點后面的為其右子樹；我們可以由后序排列求得根結點，再由根結點在中序排列的位置確定左子樹和右子樹，把左子樹和右子樹各看作一個單獨的樹。這樣，就把一棵樹分解為具有相同性質(zhì)的二棵子樹，一直遞歸下
7、去，當分解的子樹為空時，遞歸結束，在遞歸過程中，按先序遍歷的規(guī)則輸出求得的各個根結點，輸出的結果即為原問題的解。
源程序
program noipxx_3;
var z,h : string;
procedure make(z,h:string); {z為中序排列,h為后序排列}
var s,m : integer;
begin
m:=length(h);{m為樹的長度}
write(h[m]); {輸出根節(jié)點}
s:=pos(h[m],z); {求根節(jié)點在中序排列中的位置}
if s>1 then make(copy(z,1,s-1),copy(h,1,
8、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.
遞歸算法不僅僅是用于求解遞歸描述的問題，在其它很多問題中也可以用到遞歸思想，如回溯法、分治法、動態(tài)規(guī)劃法等算法中都可以使用遞歸思想來實現(xiàn)，從而使編寫的程序更加簡潔。
比如上期回溯法所講的例2《數(shù)的劃分問題》，若用遞歸來求解，程序非常短小且效率很高，源程序如下
var
n,k:integer;
tol:lon
9、gint;
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)數(shù)列，它的遞歸定義為：
F(n)=1?? (n=1,2)
10、
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;
上面的遞歸過程，調(diào)用一次產(chǎn)生二個新的調(diào)用，遞歸次數(shù)呈指數(shù)增長，時間復雜度為O（2n）,把它改為非遞歸：
x:=1;y:=1;
for i:=3 to n do
begin
z:=y;y:=x+y;x:=z;
end;
修改后的程序，它的時間復雜度為O（n）。
我們在編寫程序時是否使用遞歸算法，關鍵是看問題是否適合用遞歸算法來求解。由于遞歸算法編寫的程序邏輯性強，結構清晰，正確性易于證明，程序調(diào)試也十分方便，在NOIP中，數(shù)據(jù)的規(guī)模一般也不大，只要問題適合用遞歸算法求解，我們還是可以大膽地使用遞歸算法。
2022年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞歸算法
