【導(dǎo)讀】“?！钡膽?yīng)用很廣泛，大家在PASCAL程序設(shè)計(jì)中，常。遇的一種錯(cuò)誤就是“棧”超界，那么，“?！睘楹挝锬?？棧是只能在某一端插入和刪除的特殊線性表。取走時(shí)，只能從上面一件一件取。進(jìn)行，底部一般是不動(dòng)的。和插入的一端稱棧頂，另一堆稱棧底。棧，刪除則稱為退棧。棧也稱為后進(jìn)先出表。一個(gè)棧可以用定長(zhǎng)為Ｎ的數(shù)組Ｓ來(lái)表示，用一個(gè)棧指針TOP指向棧頂。0，表示棧空，TOP=N時(shí)棧滿。棧指針在運(yùn)算中永遠(yuǎn)指向棧頂。出；不滿則作②）；溢可用來(lái)作為控制程序轉(zhuǎn)移的判斷標(biāo)志，是十分有用的。則是一種致命的錯(cuò)誤，將使程序無(wú)法繼續(xù)運(yùn)行，所以要設(shè)法避免。軌道為單向行駛軌道。①凡遇到操作數(shù)，一律進(jìn)入操作數(shù)棧；較該運(yùn)算符與棧頂元素的優(yōu)先數(shù)。號(hào)，其優(yōu)先數(shù)小于乘號(hào)所以乘號(hào)退棧，并執(zhí)行８×２，將結(jié)果１６再存入操作數(shù)棧。減號(hào)退棧并執(zhí)行２０－３，結(jié)果為１７并入棧。求值結(jié)束，結(jié)果為１７。×、÷運(yùn)算符，充許含括號(hào)），輸出算術(shù)表達(dá)式的值。

　　

【正文】 據(jù)結(jié)構(gòu)本來(lái)就是遞歸描述的，用遞歸做很自然。 利用遞歸的思想建立遞推關(guān)系，如由兔子生崽而來(lái)的 fibonacci 數(shù)列。但遞推由于沒(méi)有返回段，因此更為簡(jiǎn)單，有時(shí)可以直接用循環(huán)實(shí)現(xiàn)。 不少分治方法是源于遞歸思想，或是遞歸分解 +合并處理。 規(guī)模較小的問(wèn)題用回溯解決比較自然。注意遞歸前后要保證現(xiàn)場(chǎng)的保存和恢復(fù)，即正確的轉(zhuǎn)化問(wèn)題。 動(dòng)態(tài)規(guī)劃的子問(wèn)題重疊性質(zhì)與遞歸有某種相似之處。遞歸 +動(dòng)態(tài)修改查表是一種不錯(cuò)的建立動(dòng)態(tài)規(guī) 劃模型的方法。 其他么，就是不好歸類。例如表達(dá)式處理，排列組合等。附帶說(shuō)一下，用遞歸來(lái)處理打印方案的問(wèn)題還是很方便的。 求把一個(gè)整數(shù) n 無(wú)序劃分成 k 份互不相同的正整數(shù)之和的方法總數(shù)。 [分析 ] 這是一道動(dòng)態(tài)規(guī)劃題，動(dòng)態(tài)方程如下： f[i1,j]+f[i,ji]+1 (j mod i=0) and (j div i=1)） f[i,j]:= f[i1,j] (i=j) f[i1,j]+f[i,ji] （ else） s:=f(k,nk) 本題可以用循環(huán)來(lái)實(shí)現(xiàn)遞推 ,也可以考慮用遞 歸求解。主過(guò)程如下： 方案一： Procedure work(I,j:longint。 var s:longint)。 Var t:longint。 Begin If (i=1) or (j=1) then s:=1 Else if (i=0) or (j=0) then s:=0 Else begin if (j mod i=0) and (j div i=1) then begin work(i1,j,s)。 t:=s。 work(i,j1,s)。 s:=s+t+1。 end else if (i=j) then work(i1,j) else begin work(i1,j,s)。 t:=s。 work(I,j1,s)。 s:=s+t。 end。 End。 方案二： procedure search(v,w,last:byte)。 var i:byte。 begin if w=0 then inc(count) else if w=1 then if v=last then search(0,0,0) else else for i:=last to v1 do search(vi,w1,i)。 end。 可以 看出，方案一的程序較為冗長(zhǎng)，消耗?？臻g較大；而方案二較為簡(jiǎn)潔明了，所用的?？臻g也較小，效率較高。因此，使用遞歸算法也有一個(gè)優(yōu)化問(wèn)題。算法的簡(jiǎn)潔與否直接制約了程序的可行性和效率。 [總結(jié) ] 遞歸使一些復(fù)雜的問(wèn)題處理起來(lái)簡(jiǎn)單明了，尤其在學(xué)習(xí)算法設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)時(shí)更能體會(huì)到這一點(diǎn)。但是，遞歸在每一次執(zhí)行時(shí)都要為局部變量、返回地址分配?？臻g，這就降低了運(yùn)行效率，也限制了遞歸的深度。因此，在必要的時(shí)候可以只使用遞歸的思想 來(lái)求解，而程序則轉(zhuǎn)用非遞歸的方式書寫。 遞歸習(xí)題 : 一 . 一 . 九連環(huán)問(wèn)題 : 有 N(2=N=9)個(gè)環(huán) ,拆裝這些環(huán)的規(guī)則 :第一個(gè)環(huán)可以隨意拆裝 ,第二個(gè)環(huán)只有在第一環(huán)已裝上時(shí)可以拆裝 。第 I個(gè)環(huán)只有在第 i1環(huán)已裝上 ,且第 i2，第 i3…… 第 1環(huán)都拆下時(shí)可以裝拆 .編程序描述拆下 N個(gè)環(huán)的過(guò)程 . 二 .打印 0—N（ 0=N=9）的所有路徑 : 三 .剔除多余括號(hào) 鍵盤輸入一個(gè)含有括號(hào)的四則運(yùn)算表達(dá)式，可能含有多余的括號(hào)，編程整理該表達(dá)式，去掉所有多余的括號(hào)，原表達(dá)式中所有變量和運(yùn)算符相對(duì)位置保持不變，并保持與原表達(dá)式等價(jià)。 例：輸入表達(dá)式 應(yīng)輸出表達(dá)式 a+(b+c) a+b+c (a*b)+c/d a*b+c/d a+b/(cd) a+b/(cd) 注意輸入 a+b時(shí)不能輸出 b+a。 表達(dá)式以字符串輸入，長(zhǎng)度不超過(guò)２５５。輸入不要判錯(cuò)。 所有變量為單個(gè)小寫字母。只是要求去掉所有多余括號(hào)，不要求對(duì)表達(dá)式化簡(jiǎn)。 四 .汽車問(wèn)題 有一個(gè)人在一個(gè)公共汽車站上，從 12:00到 12:59觀察公共汽車到達(dá)本站的情況，該站被多條公共汽車線路所公用，他 記下了公共汽車到達(dá)本站的時(shí)刻。 ●在 12:00─ 12:59這個(gè)期間內(nèi)，同一條線路上的公共汽車以相同的時(shí)間間隔到站。 ●時(shí)間單位用“分”表示，從 0到 59。 ●每條公共汽車線路上的車至少到達(dá)本站兩次。 ●在本例的公共汽線路數(shù)一定≤ 17。 ●來(lái)自不同線路的公共汽車可能在同一時(shí)刻到達(dá)本站。 ●不同公共汽車線路的車首次到站時(shí)間和（或）（ and／ or ）時(shí)間間隔（到站的）可能相同。如果兩條公共汽車線路的車有相同的開(kāi)始時(shí)間和相同的時(shí)間間隔，它們必須分開(kāi)表示出來(lái)。 請(qǐng)為公共汽車線路編一個(gè)調(diào)度表，目標(biāo)是：公共 汽車線路數(shù)目最少的情況下，使公共汽車到達(dá)本站的時(shí)刻滿足輸入數(shù)據(jù)的要求。對(duì)于每一公共汽車線路，輸出其起始時(shí)刻（第一次到達(dá)本站）和到達(dá)本站的時(shí)間間隔。 輸入數(shù)據(jù)： 輸入文件 n（ n≤ 300），下面以遞增順序給出各公共汽車到達(dá)本站的時(shí)刻。我們的例子是： 17 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53 輸出數(shù)據(jù)： 在輸出文件 中列一個(gè)表，每一行表示一條公共汽車線路。行中第一個(gè)數(shù)字 表示該線路上的公共汽車的首次到達(dá)本站的時(shí)刻；第二個(gè)數(shù)字表示該線路上的公共汽車兩次到達(dá)本站的時(shí)間間隔。時(shí)間的單位是‘分’。各公共汽車線路在表中出現(xiàn)的先后順序沒(méi)有重要性（次序可任意）。若有多個(gè)等價(jià)解，僅需輸出其中一個(gè)。我們例子的輸出文件的內(nèi)容為： 0 13 3 12 5 8 （六）―― 搜索與回溯 本講，我們來(lái)談?wù)勊阉髋c回溯。 搜索與回溯是計(jì)算機(jī)解題中常用的算法，有很多問(wèn)題無(wú)法根據(jù)某種確定的計(jì)算法則來(lái)求解，此時(shí)可以利用搜索與回溯的技術(shù)求解?；厮菔撬阉魉惴ㄖ械囊环N控制策略。它的基本 思想是：為了求得問(wèn)題的解，先選擇某一種可能情況向前探索，在探索過(guò)程中，一旦發(fā)現(xiàn)原來(lái)的選擇是錯(cuò)誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至得到解或證明無(wú)解。如迷宮問(wèn)題：進(jìn)入迷宮后，先隨意選擇一個(gè)前進(jìn)方向，一步步向前試探前進(jìn)，如果碰到死胡同，說(shuō)明前進(jìn)方向已無(wú)路可走，這時(shí)，首先看其它方向是否還有路可走，如果有路可走，則沿該方向再向前試探；如果已無(wú)路可走，則返回一步，再看其它方向是否還有路可走；如果有路可走，則沿該方向再向前試探。按此原則不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無(wú)解為止。 n 皇后問(wèn)題【演示程序： ，源程序： 】 （ 1）問(wèn)題描述： 求出在一個(gè) nn的棋盤上，放置 n個(gè)不能互相捕捉的 “皇后 ”的所有布局。 （ 2） 算法分析 ： 這是來(lái)源于國(guó)際象棋的一個(gè)問(wèn)題?；屎罂梢郧?、后、左、右和沿著對(duì)角線方向相互捕捉。如圖所示，一個(gè)皇后放在棋盤 4行 3列位置上，棋盤打 ?● ?的位置就不能再放置皇后。 上圖提示我們，一個(gè)合適的解應(yīng)是在每列、每行確實(shí)有一個(gè)皇后，且在一條對(duì)角線上最多只有一個(gè)皇后。 在開(kāi)發(fā)程序之前，設(shè)定表示棋盤的數(shù)據(jù)結(jié)構(gòu)是一個(gè) nn數(shù)組。每一個(gè)位置代表棋盤上的一個(gè)方格。然而考慮到一個(gè)合理的解中每列、每行只能放置一個(gè)皇后，棋盤也可用一個(gè)一維數(shù)組來(lái)表示。數(shù)組的每一個(gè)元素代表棋盤的一列，該元素的值是皇后在該列上的行位置。設(shè)數(shù)組名為 col, 對(duì)于圖有 col[3]=4。它表示第 3列的第 4行有一個(gè)皇后。 為找到一個(gè)解，必須從空布局開(kāi)始，每放置一個(gè)皇后要檢查布 局是否合理。在合理的情況下，試探找下一個(gè)皇后的位置；如果布局不合理，就改變布局。重復(fù)檢查、試探或檢查、改變位置，直到找到最后一個(gè)皇后的合理位置，這時(shí)就找到一個(gè)合理的布局。重復(fù)以上過(guò)程直到無(wú)法再改變皇后位置為止，就可找到所有合理的布局。通過(guò)以上討論，得到程序的第一層描述如下： VAR n, m : 0..MAXSIZE。 {n為皇后總數(shù)目 ， m為當(dāng)前已放置的皇后數(shù) } good : boolean。 {布局合理與否 } col : ARRAY [0..MAXSIZE] OF 0..MAXSIZE。 {解 } BEGIN read(n)。 {輸入皇后數(shù)目 } m:=0。 good:=true。 {空布局是合理的 ｝ REPEAT IF good THEN IF m=n THEN {搜索到一個(gè)解 } BEGIN print。 {打印 } change {改變布局 ， 繼續(xù)找解 } END ELSE extend {繼續(xù)試探下一個(gè)皇后位置 } ELSE change。 check {檢查布局是否合理 } UNTIL m=0 {皇后位置不能再改變 } END. 子過(guò)程 change改變布局就是試探當(dāng)前皇后 m的下一個(gè)位置 ， 即試著放在下一列上(col[m]:=col[m]+1)。如果 col[m]=n，說(shuō)明當(dāng)前皇后 m無(wú)位置可放，必須返回到上一個(gè)皇后的狀態(tài)，改變第 m1個(gè)皇后位置。為了防止存取不存在的 col[0]，給數(shù)組 col增設(shè)一個(gè)元素 col[0]，它的初值為 0。 PROCEDURE change。 BEGIN IF col[m]=n THEN m :=m1。 col[m]:=col[m]+1 END。 子過(guò)程 extend就是試探下一個(gè)皇后的位置，這時(shí)要盡可能試探完所有的位置，即從第一列放起： PROCEDURE extend。 BEGIN m :=m+1。 col[m]:=1 END。 主要的困難是過(guò)程 check。見(jiàn)圖中，在 nn棋盤 上對(duì) m列上的皇后配置是檢查四個(gè)方向； 縱向。由問(wèn)題的數(shù)據(jù)結(jié)構(gòu)保證一列只放一個(gè)皇后。 橫向。對(duì)所有 k(k=1,2,,m1)檢查不等式 col[k]col[m]是否成立。 左高右低對(duì)角線。共有 (2n1)條這樣的對(duì)角線。同一條對(duì)角線上的不同位置它們的行號(hào)值與列號(hào)值之差相等。所謂檢查 m列上的皇后配置是否與前面的皇后在同一條左高右低對(duì)角線上，就是檢查對(duì)所有 k(k=1,2,,m－ 1)不等式成立： (col[k]k)(col[m]m)。 左低右高對(duì)角線。類似 3，檢查 m列上的皇后配置是否與前 面的皇后在同一條左低右高對(duì)角線上，就是檢查對(duì)所有的 k(k=1,2,,m1)不等式成立： (col[k]+k)(col[m]+m)。 【源程序】 {n 皇后問(wèn)題程序 } PROGRAM xoi00_11(input, output)。 CONST maxsize=25。 VAR m,n: 0..maxsize。 good: boolean。 col: ARRAY [0..maxsize] OF 0..maxsize。 counts:integer。 PROCEDURE print。 VAR i , j : 0..maxsize。 BEGIN {轉(zhuǎn)置輸出 } FOR j:=1 TO n DO BEGIN i:=col[j]。 writeln(i,39。 39。:(3+i*5),39。Q39。)。 writeln END。 writeln(39。 39。:8,39。********************39。)。 writeln END。 PROCEDURE extend。 BEGIN m:=m+1。 col[m]:=1 END。 PROCEDURE change。 BEGIN IF col[m]=n THEN m:=m1。