2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞歸算法.doc
《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞歸算法.doc》由會(huì)員分享,可在線閱讀,更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞歸算法.doc(4頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞歸算法 遞歸算法的定義: 如果一個(gè)對(duì)象的描述中包含它本身,我們就稱這個(gè)對(duì)象是遞歸的,這種用遞歸來描述的算法稱為遞歸算法。 我們先來看看大家熟知的一個(gè)的故事: 從前有座山,山上有座廟,廟里有個(gè)老和尚在給小和尚講故事,他說從前有座山,山上有座廟,廟里有個(gè)老和尚在給小和尚講故事,他說…… 上面的故事本身是遞歸的,用遞歸算法描述: procedure bonze-tell-story; begin if 講話被打斷 then 故事結(jié)束 else begin 從前有座山,山上有座廟,廟里有個(gè)老和尚在給小和尚講故事; bonze-tell-story; end end; 從上面的遞歸事例不難看出,遞歸算法存在的兩個(gè)必要條件: (1) 必須有遞歸的終止條件; (2) 過程的描述中包含它本身; 在設(shè)計(jì)遞歸算法中,如何將一個(gè)問題轉(zhuǎn)化為遞歸的問題,是初學(xué)者面臨的難題,下面我們通過分析漢諾塔問題,看看如何用遞歸算法來求解問題; 遞歸算法應(yīng)用 例1:漢諾塔問題,如下圖,有A、B、C三根柱子。A柱子上按從小到大的順序堆放了N個(gè)盤子,現(xiàn)在要把全部盤子從A柱移動(dòng)到C柱,移動(dòng)過程中可以借助B柱。移動(dòng)時(shí)有如下要求: (1) 一次只能移動(dòng)一個(gè)盤子; (2) 不允許把大盤放在小盤上邊; (3) 盤子只能放在三根柱子上; 算法分析:當(dāng)盤子比較多的時(shí),問題比較復(fù)雜,所以我們先分析簡單的情況: 如果只有一個(gè)盤子,只需一步,直接把它從A柱移動(dòng)到C柱; 如果是二個(gè)盤子,共需要移動(dòng)3步: (1) 把A柱上的小盤子移動(dòng)到B柱; (2) 把A柱上的大盤子移動(dòng)到C柱; (3) 把B柱上的大盤子移動(dòng)到C柱; 如果N比較大時(shí),需要很多步才能完成,我們先考慮是否能把復(fù)雜的移動(dòng)過程轉(zhuǎn)化為簡單的移動(dòng)過程,如果要把A柱上最大的盤子移動(dòng)到C柱上去,必須先把上面的N-1個(gè)盤子從A柱移動(dòng)到B柱上暫存,按這種思路,就可以把N個(gè)盤子的移動(dòng)過程分作3大步: (1) 把A柱上面的N-1個(gè)盤子移動(dòng)到B柱; (2) 把A柱上剩下的一個(gè)盤子移動(dòng)到C柱; (3) 把B柱上面的N-1個(gè)盤子移動(dòng)到C柱; 其中N-1個(gè)盤子的移動(dòng)過程又可按同樣的方法分為三大步,這樣就把移動(dòng)過程轉(zhuǎn)化為一個(gè)遞歸的過程,直到最后只剩下一個(gè)盤子,按照移動(dòng)一個(gè)盤子的方法移動(dòng),遞歸結(jié)束。 遞歸過程: procedure Hanoi(N,A,B,C:integer;);{以B柱為中轉(zhuǎn)柱將N個(gè)盤子從A柱移動(dòng)到C柱} begin if N=1 then write(A,’->’,C){把盤子直接從A移動(dòng)到C} else begin Hanoi(N-1,A,C,B);{ 以C柱為中轉(zhuǎn)柱將N-1個(gè)盤子從A柱移動(dòng)到B柱} write(A,’->’,C);{把剩下的一個(gè)盤子從A移動(dòng)到C} Hanoi(N-1,B,A,C); { 以A柱為中轉(zhuǎn)柱將N-1個(gè)盤子從B柱移動(dòng)到C柱} end; end; 從上面的例子我們可以看出,在使用遞歸算法時(shí),首先弄清楚簡單情況下的解法,然后弄清楚如何把復(fù)雜情況歸納為更簡單的情況。 在信息學(xué)奧賽中有的問題的結(jié)構(gòu)或所處理的數(shù)據(jù)本身是遞歸定義的,這樣的問題非常適合用遞歸算法來求解,對(duì)于這類問題,我們把它分解為具有相同性質(zhì)的若干個(gè)子問題,如果子問題解決了,原問題也就解決了。 例2求先序排列 (NOIPxxpj) [問題描述]給出一棵二叉樹的中序與后序排列。求出它的先序排列。(約定樹結(jié)點(diǎn)用不同的大寫字母表示,長度≤8)。 [樣例] 輸入:BADC BDCA 輸出:ABCD 算法分析:我們先看看三種遍歷的定義: 先序遍歷是先訪問根結(jié)點(diǎn),再遍歷左子樹,最后遍歷右子樹; 中序遍歷是先遍歷左子樹,再訪問根結(jié)點(diǎn),最后遍歷右子樹; 后序遍歷是先遍歷左子樹,再遍歷右子樹,最后訪問根結(jié)點(diǎn); 從遍歷的定義可知,后序排列的最后一個(gè)字符即為這棵樹的根節(jié)點(diǎn);在中序排列中,根結(jié)點(diǎn)前面的為其左子樹,根結(jié)點(diǎn)后面的為其右子樹;我們可以由后序排列求得根結(jié)點(diǎn),再由根結(jié)點(diǎn)在中序排列的位置確定左子樹和右子樹,把左子樹和右子樹各看作一個(gè)單獨(dú)的樹。這樣,就把一棵樹分解為具有相同性質(zhì)的二棵子樹,一直遞歸下去,當(dāng)分解的子樹為空時(shí),遞歸結(jié)束,在遞歸過程中,按先序遍歷的規(guī)則輸出求得的各個(gè)根結(jié)點(diǎn),輸出的結(jié)果即為原問題的解。 源程序 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é)點(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)); {處理左子樹} 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. 遞歸算法不僅僅是用于求解遞歸描述的問題,在其它很多問題中也可以用到遞歸思想,如回溯法、分治法、動(dòng)態(tài)規(guī)劃法等算法中都可以使用遞歸思想來實(shí)現(xiàn),從而使編寫的程序更加簡潔。 比如上期回溯法所講的例2《數(shù)的劃分問題》,若用遞歸來求解,程序非常短小且效率很高,源程序如下 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. 有些問題本身是遞歸定義的,但它并不適合用遞歸算法來求解,如斐波那契(Fibonacci)數(shù)列,它的遞歸定義為: F(n)=1 (n=1,2) 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)生二個(gè)新的調(diào)用,遞歸次數(shù)呈指數(shù)增長,時(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)。 我們在編寫程序時(shí)是否使用遞歸算法,關(guān)鍵是看問題是否適合用遞歸算法來求解。由于遞歸算法編寫的程序邏輯性強(qiáng),結(jié)構(gòu)清晰,正確性易于證明,程序調(diào)試也十分方便,在NOIP中,數(shù)據(jù)的規(guī)模一般也不大,只要問題適合用遞歸算法求解,我們還是可以大膽地使用遞歸算法。- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 遞歸算法 2019 2020 年高 信息技術(shù) 全國青少年 奧林匹克 聯(lián)賽 教案 遞歸 算法
鏈接地址:http://www.3dchina-expo.com/p-2577038.html