【正文】 ********************39。 VAR m,n: 0..maxsize。 {打印 } change {改變布局 ， 繼續(xù)找解 } END ELSE extend {繼續(xù)試探下一個(gè)皇后位置 } ELSE change。每一個(gè)位置代表棋盤上的一個(gè)方格。行中第一個(gè)數(shù)字 表示該線路上的公共汽車的首次到達(dá)本站的時(shí)刻；第二個(gè)數(shù)字表示該線路上的公共汽車兩次到達(dá)本站的時(shí)間間隔。 表達(dá)式以字符串輸入，長(zhǎng)度不超過２５５。 s:=s+t。遞歸 +動(dòng)態(tài)修改查表是一種不錯(cuò)的建立動(dòng)態(tài)規(guī) 劃模型的方法。 if s10 then find(copy(a,1,s1),copy(b,1,s1))。因此，在考慮使用遞歸算法編寫程序時(shí)，應(yīng)滿足兩點(diǎn)： 1）該問題能夠被遞歸形式描述； 2）存在遞歸結(jié)束的邊界條件。 ( 1) 非波那契 (Fibonacci)數(shù)列 . 數(shù)列的遞歸公式如下 : 1 1F? (n=1) 2 1F? (n=2) 12n n nF F F????( 3n? ) 按照上面的遞歸公式 ,可寫出如下 PASCAL 程序 program fibonacci。 begin a:=39。即： HANOI(N,A,B,C) 可轉(zhuǎn)化為 HANOI(N1,A,C,B)與 HANOI(N1,B,A,B) 其中 HANOI中的參數(shù)分別表示需移動(dòng)的盤數(shù)、起始盤、臨時(shí)盤與終止盤， 這種轉(zhuǎn)換直至轉(zhuǎn)入的盤數(shù)為 0為止，因?yàn)檫@時(shí)已無盤可移了。因?yàn)樵谶f歸調(diào)用的執(zhí)行過程中，系統(tǒng)必須花費(fèi)時(shí)間與空間以棧的方式記下每次調(diào)用的返回位置地址及每一次過程執(zhí)行的中間結(jié)果，以便當(dāng)遞歸調(diào)用終止條件成立時(shí)，能沿著 逐步深入 的路線 逐步返回 ，取得這些數(shù)據(jù)，最終準(zhǔn)確地回到初始調(diào)用處。 begin write(39。N!=39。 例 1 利用遞歸調(diào)用手段編程計(jì)算 N!。 源程序如下： program ex11_9。 repeat inc(i)。 例 2 著名的菲波納葜 (Fibonacci)數(shù)列，其第一項(xiàng)為 0，第二項(xiàng)為 1， 從第三項(xiàng)開始，其每一項(xiàng)都是前兩項(xiàng)的和。 while abs(x1x0)a do begin x0:=x1。 end. （四）――迭代與遞推 本次我們想與大家共同探討一下迭代與遞推。 assign(int,name)。y:=h[t,2]+dy[i]。 dy:array[1..4] of 1..1=(0,1,0,1)。j:=0。 end until p=n。 源程序一： 用數(shù)組實(shí)現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu) program ex116a。 思路： (1)可以建立兩種隊(duì)列，一 種隊(duì)列是存放數(shù)值的數(shù)值隊(duì)列 Q1，并有 Q1[A]到 Q1[Z]共 26 條數(shù)值隊(duì)列，另一種隊(duì)列 Q2存放字母，表示將要向該字母所對(duì)應(yīng)的數(shù)值隊(duì)列輸入數(shù)值的事件隊(duì)列。 39。 end。 39。)。 begin new(p)。 dec(tb)。8)。 dec(tb)。 39。 begin write(39。當(dāng)某個(gè)用戶要求使用 CPU時(shí)，相應(yīng)的終端代號(hào)就入隊(duì)（插入隊(duì)尾），而隊(duì)頭的終端用戶則是 CPU 當(dāng)前服務(wù)的對(duì)象。在隊(duì)列的運(yùn)算中需設(shè)兩個(gè)指針： head：隊(duì)頭指針，指向?qū)嶋H隊(duì)頭元素的前一個(gè)位置 tall：隊(duì) 尾指針，指向?qū)嶋H隊(duì)尾元素所在的 位置一般情況下，兩個(gè)指針的初值設(shè)為０，這時(shí)隊(duì)列為空，沒有元素。然后，將一開始表示轉(zhuǎn)換關(guān)系的 N根據(jù) ascii表序號(hào)化成大寫字母放在最前面。 until (i length(s)) or (s[i 1] 39。) or (s[i] 39。 readln(s)。(39。: dec(number[p], number[p + 1])。 const max = 100。 ＋ － 優(yōu)先數(shù)：２ ２ １ １ （語句結(jié)束符“；”的優(yōu)先數(shù)為零） 在運(yùn)算過程中，優(yōu)先數(shù)高的運(yùn)算符應(yīng)先進(jìn)行運(yùn)算（但遇到括號(hào)時(shí)，應(yīng)另作處理）。 readln(d)。對(duì)于入棧運(yùn)算中的“上溢”，則是一種致命的錯(cuò)誤，將使程序無法繼續(xù)運(yùn)行，所以要設(shè)法避免。 PROCEDURE PUSH(VAR s:stack?！皸！钡膽?yīng)用很廣泛，大家在 PASCAL 程序設(shè)計(jì)中，常遇的一種錯(cuò)誤就是“?！背?，那么，“?！睘楹挝锬?？ 棧是只能在某一端插入和刪除的特殊線性表。 進(jìn)棧（ PUSH）算法 ①若 TOP≥ｎ時(shí)，則給出溢出信息，作出錯(cuò)處理（進(jìn)棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）； ②置 TOP=TOP+1（棧指針加１，指向進(jìn)棧地址）； ③ S(TOP)=X，結(jié)束（ X為新進(jìn)棧的元素）； 退棧（ POP）算法 ①若 TOP≤ 0，則給出下溢信息，作出錯(cuò)處理 (退棧前先檢查是否已為空棧， 空則下溢；不空則作② )； ② X=S(SOP)，（退棧后的元素賦給 X）； ③ TOP=TOP1，結(jié)束（棧指針減１，指向棧頂）。top:=top1。 write(39。因此，為了使編譯程序能夠正確地求值，必須事先規(guī)定求值的順序和規(guī)則。設(shè)輸入的表達(dá)式串是合法的。: inc(number[p], number[p + 1])。, 39。 begin write(39。 repeat {取數(shù)入操作數(shù)棧 } inc(i)。 push。 例如當(dāng) N=1，輸入的句子為 ABCXYZ時(shí)，則其轉(zhuǎn)換碼為 ABCXYZ不變。所有需要進(jìn)隊(duì)的數(shù)據(jù)項(xiàng)，只能從隊(duì)尾進(jìn)入，隊(duì)列中的數(shù)據(jù)項(xiàng)只能從隊(duì)頭離去。 隊(duì)列和棧一樣，有著非常廣泛的應(yīng)用。 ar = array[1..1000] of node。Result is 39。, b[tb].zhi, 39。 end。, b[tb].zhi, 39。 procedure createfifo(var c: link)。 createfifo(a)。)。, b^.zhi, 39。 a := a^.nxt。 end. ： 例：設(shè)有一個(gè)表，記為 L=(a1,a2,a3,...,an)，其中 L——表名 a1,a2,a3,..,an——表中元素。設(shè)立指針 j 指向當(dāng)前結(jié)點(diǎn)，則移動(dòng)結(jié)點(diǎn)過程為 j:=a[j]，當(dāng)數(shù)到 m時(shí)， m結(jié)點(diǎn)出鏈，則 a[j]:=a[a[j]]。p:=p+1。 {申請(qǐng)第 2 到 n 結(jié)點(diǎn) } ptr^.val:=i。 算法步驟： 1． 從文件中讀入 m*n 矩陣陣列，將其轉(zhuǎn)換為 boolean 矩陣存入 bz數(shù)組中； 2． 沿 bz數(shù)組矩陣從上到下，從左到右，找到遇到的第一個(gè)細(xì)胞； 3． 將細(xì)胞的位置入隊(duì) h，并沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置 bz數(shù)組置為 FLASE； 4． 將 h 隊(duì)的隊(duì)頭出隊(duì)，沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置 bz數(shù)組置為 FLASE； 5． 重復(fù) 4，直至 h 隊(duì)空為止，則此時(shí)找出了一個(gè)細(xì)胞； 6． 重復(fù) 2，直至矩陣找不到細(xì)胞； 7． 輸出找到的細(xì)胞數(shù)。h[1,1]:=p。input file:39。NUMBER of cells=39。 var x0,x1,X:real。 遞推算法的首要問題是得到相鄰的數(shù)據(jù)項(xiàng)間的關(guān)系（即遞推關(guān)系）。 i:=2。請(qǐng)編一個(gè)程序計(jì)算從頂?shù)降椎哪程幍囊粭l 路徑，使該路徑所經(jīng)過的數(shù)字總和最大。 圖 1 遞歸過程的執(zhí)行流程 從圖 1 可以看出，遞歸過程的執(zhí)行總是一個(gè)過程體未執(zhí)行完， 就帶著本次執(zhí)行的結(jié)果又進(jìn)入另一輪過程體的執(zhí)行，??，如此反復(fù)，不斷深入，直到某次過程 的執(zhí)行遇到終止遞歸調(diào)用的條件成立時(shí)，則不再深入，而執(zhí)行本次的過程體余下的部分，然后又返回到上一次調(diào)用的過程體中，執(zhí)行其余下的部分，??，如此反復(fù)，直到回到起始位置上，才最終結(jié)束整個(gè)遞歸過程的執(zhí)行，得到相應(yīng)的執(zhí)行結(jié)果。readln(n)。 a[n]:=i。函數(shù) F 由于存在著兩次的遞歸調(diào)用，使遞歸調(diào)用產(chǎn)生執(zhí)行流程的 二叉樹 行式，大家可參照?qǐng)D 2 來理解這個(gè)執(zhí)行過程。 A桿為臨時(shí)桿，從 B 桿將 1 至 N1 號(hào)盤移至 C 桿。 hanoi(n1,b,a,c)。這是一個(gè)天文數(shù)字，即使一臺(tái)功能很強(qiáng)的現(xiàn)代計(jì)算機(jī)來解漢諾塔問題，恐怕也需要很長(zhǎng)的時(shí)間，因此要想得到結(jié)果 ，在運(yùn)行程序時(shí)，輸入的 N 可不能太大。（答案： 1534） 有 5人坐在一起，問第 5 個(gè)人多少歲？他說比第 4個(gè)人大 2歲，問第 4 個(gè)人多少歲？他說比第 3 個(gè)人大 2 歲，依此下去，問第一個(gè)人多少歲，他說他 10 歲，問第 5 個(gè)人多少歲？如果所圍的不是 5 人而是 n 人，寫出第 n 個(gè)人的年齡表達(dá)式。 begin l:=length(b)。 規(guī)模較小的問題用回溯解決比較自然。 end else if (i=j) then work(i1,j) else begin work(i1,j,s)。 遞歸習(xí)題 : 一 . 一 . 九連環(huán)問題 : 有 N(2=N=9)個(gè)環(huán) ,拆裝這些環(huán)的規(guī)則 :第一個(gè)環(huán)可以隨意拆裝 ,第二個(gè)環(huán)只有在第一環(huán)已裝上時(shí)可以拆裝 。對(duì)于每一公共汽車線路，輸出其起始時(shí)刻（第一次到達(dá)本站）和到達(dá)本站的時(shí)間間隔。如圖所示，一個(gè)皇后放在棋盤 4行 3列位置上，棋盤打 ?● ?的位置就不能再放置皇后。 {輸入皇后數(shù)目 } m:=0。 橫向。,m1)不等式成立： (col[k]+k)(col[m]+m)。 writeln(39。 PROCEDURE extend。 counts:integer。共有 (2n1)條這樣的對(duì)角線。為了防止存取不存在的 col[0]，給數(shù)組 col增設(shè)一個(gè)元素 col[0]，它的初值為 0。設(shè)數(shù)組名為 col, 對(duì)于圖有 col[3]=4。若有多個(gè)等價(jià)解，僅需輸出其中一個(gè)。只是要求去掉所有多余括號(hào)，不要求對(duì)表達(dá)式化簡(jiǎn)。 方案二： procedure search(v,w,last:byte)。附帶說一下，用遞歸來處理打印方案的問題還是很方便的。 end。 給出一棵二叉樹的中序與后序排列。 begin if n 3 then fb := 1 else fb := fb(n 1) + fb(n 2)。B39。 var a,b,c:char。 例 3 相傳在古印度的布拉瑪婆羅門圣廟的僧侶在進(jìn)行一種被稱為漢諾塔的游戲，其裝置是一塊銅板，上面有三根桿（編號(hào) A、 B、 C）， A 桿上自下而上、由大到小按順序串上 64 個(gè)金盤（如圖 3）。readln(n)。 例如當(dāng) N=5 時(shí)， find(5)的值變?yōu)?5*find(4)， 求 find( 4)又變?yōu)?4*find(3)，?，當(dāng) N= 1 時(shí)遞歸停止，逐步返回到第一次調(diào)用的初始處，返回結(jié)果 5*4*3*2*1，即 5!。 var n:byte。 begin read(n)。k:=p。而根椐該數(shù)列的形成規(guī)則，其有一個(gè)的公式即 Ｕ n＝Ｕ n1＋Ｕ n2 表明了相鄰的數(shù)據(jù)項(xiàng)之間的明顯關(guān)系。 x:=x1+1。求根可以直接從方程出發(fā)，逐步縮小根的存在區(qū)間，把根的近似值逐步精確到要以滿足具體實(shí)際問題的需要為止，該算法稱為迭代。 for i:=1 to m do begin readln(int,s)。h[w,2]:=y。 pic:array[1..50,1..79] of byte。ptb:=ptb^.link。 node=record val:integer。{設(shè)有 10 個(gè)人 ,報(bào)到 4 的人出列 } var a:array[1..n] of integer。 (4)重復(fù) (3)步驟，直到事件隊(duì)列中為空。x39。 end。x39。 write(39。 for i := 1 to n 1 do begin new(p^.nxt)。 39。, a[ta].zhi, 39。8)。x39。 readln(n)。由于計(jì)算機(jī)的運(yùn)行速度極快，所以，對(duì)于每個(gè)終端用戶來說，似乎計(jì)算機(jī)是單獨(dú)在為其服務(wù)。隊(duì)列中擁有的元素個(gè)數(shù)為 :L=tailhead現(xiàn)要讓排頭的元素出隊(duì)，則需將頭指針加１。最近該實(shí)驗(yàn)室收到了某公司所委托的一個(gè)任務(wù)：需要在該公司某型號(hào)的計(jì)算器上加上解一元一次方程的功能。 end。 t := copy(s, j, i j)。 + s + 39。*39。: number[p] := number[p] * number[p + 1]。 s, t: string。編譯程序自左向右掃描表達(dá)式直至語句結(jié)束，其處理原則是：