2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞歸算法.doc

《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞歸算法.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞歸算法.doc（4頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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