信息技術(shù)競賽培訓(xùn)教程

1、信息學(xué)奧林匹克競賽培訓(xùn)教程目錄第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)（一）棧（二）一一隊列（三）鏈表（四）一一迭代與遞推（五）一一遞歸（六）一一搜索與回溯（七） 樹與二叉樹（八）一一排序算法（九）一一查找算法（十）圖論基礎(chǔ)知識廣度優(yōu)先搜索深度優(yōu)先搜索第二部分算法和數(shù)據(jù)結(jié)構(gòu)（一）棧說到學(xué)習(xí)和掌握數(shù)據(jù)結(jié)構(gòu)，很容易讓人想到的就是其最本的數(shù)據(jù)結(jié)構(gòu)模式：棧、隊這一講，我 們就來談?wù)劇皸！??！皸！钡膽?yīng)用很廣泛，大家在PASCAL程序設(shè)計中，常遇的一種錯誤就是“棧” 超界，那么，“棧”為何物呢？棧是只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進來的壓在底下，隨后一件一件往堆。取走時，只能從上面一件一件取。堆和 取都在頂

2、部進行，底部一般是不動的。棧就是一種類似桶堆積物品的數(shù)據(jù)結(jié)構(gòu)，進行刪除和插入的一端稱棧頂，另一堆稱棧底。插入 一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進先出表（LIFO表）。一個棧可以用定長為N的數(shù)組S來表示，用一個棧指針TOP指向棧頂。若TOP=0，表示棧空， TOP=N時棧滿。進棧時TOP加1。退棧時TOP減1。當(dāng)TOP0時為下溢。棧指針在運算中永遠(yuǎn) 指向棧頂。1、進棧（PUSH）算法若TOPn時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則 作）；置TOP=TOP+1 （棧指針加1，指向進棧地址）；S（TOP）=X，結(jié)束（X為新進棧的元素）

3、；2、退棧（POP）算法若TOPW0，則給出下溢信息，作出錯處理（退棧前先檢查是否已為空棧，空則下溢；不空則 作）；X=S（SOP），（退棧后的元素賦給X）；TOP=TOP-1,結(jié)束（棧指針減1，指向棧頂）。進棧、出棧的Pascal實現(xiàn)過程程序：CONST n=100;TYPEstack=ARRAY1.n OF integer;PROCEDURE PUSH（VAR s:stack;VAR top,x:integer）;入 棧BEGINIF top=n THENwriteln（overflow）ELSE BEGINtop:=top+1;stop:=x;END;END;PROCEDURE POP（

4、VAR s:stack;VAR y,top:integer）;出 棧BEGINIF top=0 THEN writeln（underflow） ELSE BEGINy:=stop;top:=top-1;ENDEND;對于出棧運算中的“下溢”，程序中僅給出了一個標(biāo)志信息，而在實際應(yīng)用中，下溢可用來作為 控制程序轉(zhuǎn)移的判斷標(biāo)志，是十分有用的。對于入棧運算中的“上溢”則是一種致命的錯誤，將使 程序無法繼續(xù)運行，所以要設(shè)法避免。堆棧的數(shù)組模擬十進制數(shù)N和其它d進制數(shù)的轉(zhuǎn)換是實現(xiàn)計算的基本問題，解決方法很多，下面給出一中算法原理： N=（N div d）Xd+N mod d （其中div為整除運算，mo

5、d為求余運算）。例如：（1348）10=（2504）8運算過程如下：NN div 8N mod 894131、1、填空:NN div 8N mod 8134816841682102125202（9413）=（）=（）=（）1081622、下面的程序?qū)崿F(xiàn)這個轉(zhuǎn)換過程，請補充完整。數(shù)制轉(zhuǎn)化程序【xoi00_07.pas】program xoi00_07;const size=100;var a:array1.size of integer;n,d,i,j:integer;beginwriteln;write(Please enter a number(N) base 10:);readln(n);

6、write(please enter a number(d):);readln(d);repeatai:=n mod d;n:=n div d;inc(i);until n=0;for j:=i-1 downto 1 do write(aj:5); end.i:=1;2、火車站列車調(diào)度示意圖如下，假設(shè)調(diào)度站兩側(cè)的軌道為單向 行駛軌道。1、1、如果進站的車廂序列為123,則可能的出戰(zhàn)車廂序列是 什么？2、2、如果進展進站的車廂序列為123456，問能否得到135426 和435612的出站序列。棧的用途極為廣泛，在源程序編譯中表達式的計算、過程的嵌套調(diào)用和遞歸調(diào)用等都要用到棧，下面以表達式計算為

7、例子加以說明。源程序編譯中，若要把一個含有表達式的賦值語句翻譯成正確求值的機器語言，首先應(yīng)正確地 解釋表達式。例如，對賦值語句X:=4+8X23;（式 11.1）其正確的計算結(jié)果應(yīng)該是17,但若在編譯程序中簡單地按自左向右掃描的原則進行計算，則為：X= 12X2-3=24-3=21這結(jié)果顯然是錯誤的。因此，為了使編譯程序能夠正確地求值，必須事先規(guī)定求值的順序和規(guī)則。 通常采用運算符優(yōu)先數(shù)法。一般表達式中會遇到操作數(shù)、運算符和語句結(jié)束符等，以算術(shù)運算符為例，對每種運算賦予一 個優(yōu)先數(shù)，如：運算符：X ： + 優(yōu)先數(shù)：2211（語句結(jié)束符“；”的優(yōu)先數(shù)為零）在運算過程中，優(yōu)先數(shù)高的運算符應(yīng)先進行運

8、算（但遇到括號時，應(yīng)另作處理）。按這樣的規(guī)定， 對式（11.1）自左向右進行運算時，其計算順序就被唯一地確定下來了。計算順序確定后，在對表 達式進行編譯時，一般設(shè)立兩個棧，一個稱為運算符棧（OPS），另一個稱為操作數(shù)棧（OVS），以 便分別存放表達式中的運算符和操作數(shù)。編譯程序自左向右掃描表達式直至語句結(jié)束，其處理原則 是：凡遇到操作數(shù)，一律進入操作數(shù)棧；當(dāng)遇到運算符時，則將運算符的優(yōu)先數(shù)與運算符棧中的棧頂元素的優(yōu)先數(shù)相比較；若該運算 符的優(yōu)先數(shù)大，則進棧；反之，則取出棧頂?shù)倪\算符，并在操作數(shù)棧中連續(xù)取出兩個棧頂元素作為 運算對象進行運算，并將運算結(jié)果存入操作數(shù)棧，然后繼續(xù)比較該運算符與棧頂元

9、素的優(yōu)先數(shù)。例如式(11.1)中，當(dāng)掃描到“ + ”和“X”時都要將運算符入棧。接著掃描到“一”號，其 優(yōu)先數(shù)小于乘號所以乘號退棧，并執(zhí)行8X2，將結(jié)果16再存入操作數(shù)棧。再將“一”號的優(yōu)先 數(shù)與運算符棧的棧頂元素“+”號的優(yōu)先數(shù)相比較，兩者相等，所以再將加號退棧，進行4+16, 結(jié)果為2 0，再入棧，接著，由于運算棧已空，所以減號入棧。當(dāng)掃描到“3”時，操作數(shù)入棧。 當(dāng)掃描到“；”時，其優(yōu)先數(shù)最低，所以減號退棧并執(zhí)行2 0-3，結(jié)果為17并入棧。因已掃描 到語句結(jié)束符，所以表達式的求值結(jié)束，結(jié)果為17。例題模擬計算機處理算術(shù)表達式過程。從鍵盤上輸入算術(shù)表達式串(只含+、一、x、：運算 符，充

10、許含括號)，輸出算術(shù)表達式的值。設(shè)輸入的表達式串是合法的。分析:建立兩個棧，一個是 操作數(shù)棧(number)，一個是運算符棧(symbol)，根據(jù)運算符的優(yōu)先級對兩個棧進行相應(yīng)的操作。 源程序program ex11_4;constmax = 100;varnumber: array0.max of integer;symbol: array1.max of char;s, t: string;i, p, j, code: integer;procedure push; 算符入棧運算begininc(p);symbolp := si;end;procedure pop; 運算符棧頂元素出棧，并

11、取出操作數(shù)棧元素完成相應(yīng)的運算begindec(p);case symbolp + 1 of+: inc(numberp, numberp + 1);-: dec(numberp, numberp + 1);*: numberp := numberp * numberp + 1;/: numberp := numberp div numberp + 1;end;end;function can: boolean; 判斷運算符的優(yōu)先級別，建立標(biāo)志函數(shù)begincan := true;if (si in +, -) and (symbolp () then exit;if (si in *, /)

12、 and (symbolp in *, /) then exit;can := false;end;beginwrite(String :);readln(s);s := ( + s + );:= 1;p := 0;while i = length(s) dobeginwhile si = ( do 左括號處理beginpush;inc(i);end;j := i;repeat 取數(shù)入操作數(shù)棧inc(i);until (si 9);t ：= copy(s, j, i - j);val(t, numberp, code);repeatif si = ) then 右括號處理beginwhile

13、symbolp ( dopop;dec(p);numberp := numberp + 1;endelsebegin 根據(jù)標(biāo)志函數(shù)值作運算符入棧或出棧運算處理while can dopop;push;end;inc(i);until (i length(s) or (si - 1 );end;write(Result=, number0);readln;end.練習(xí)題：1、讀入一英文句子，單詞之間用空格或逗號隔開，統(tǒng)計其中單詞個數(shù)，并輸出各個字母出現(xiàn)的頻率。 （句子末尾不一定用”.”結(jié)束）如果含有其他的字符，則只要求輸出錯誤信息及錯誤類型。含有大寫字母錯誤類型error 1數(shù)字（0-9）錯誤類

14、型error 2其他非法字符錯誤類型error 3如輸入：It is 12!輸出：error 1 2 3輸入： i am ,a student輸出：42、2、編碼解碼：從鍵盤輸入一個英文句子，設(shè)計一個編碼、解碼程序。（string）編碼過程：先鍵入一個正整數(shù)N（1=N 0) and (tb 0) do 當(dāng)兩個表均不空時begin 比較兩表指針指向的項指數(shù)，輸出指數(shù)小的項系數(shù)和指數(shù)，同時改變該表指針if ata.zhi btb.zhi thenbeginif ata.xi 0 then write(#8 #8);write(ata.xi, x, ata.zhi, +);dec(ta);endel

15、seif ata.zhibeginif btb.xi 0 then write(#8 #8);write(btb.xi, x, btb.zhi, +);dec(tb);endelsebegin 若兩表指針指向的項指數(shù)相等,則兩系數(shù)相加輸出，兩表指針同時改變if btb.xi + ata.xi 0 thenbeginif btb.xi + ata.xi 0 do 若有一表空，則輸出另一表的剩余項beginif ata.xi 0 dobeginif btb.xi 0 then write(#8 #8);write(btb.xi, x, btb.zhi, +);dec(tb);end;writeln

16、(#8 #8);readln;end.源程序二：多項式相加的鏈表實現(xiàn)program ex11_5b;typelink = Mode;node = recordzhi, xi: integer;nxt: link;end;vara, b: link;n: integer;procedure createfifo(var c: link); 建立多項式系數(shù)、指數(shù)鏈表 varp: link;i: integer;beginnew(p);readln(pA.xi, pA.zhi);c ：= p;for i := 1 to n - 1 dobeginnew(pA.nxt);p := pA.nxt;rea

17、dln(pA.xi, pA.zhi);end;pA.nxt := nil;end;beginwrite(One :);readln(n);createfifo(a);write(Two :);readln(n);createfifo(b);write(Result is );while (a nil) and (b nil) dobeginif aA.zhi bA.zhi thenbeginif aA.xi 0 then write(#8 #8);write(aA.xi, x, aA.zhi, +);a := aA.nxt;endelseif aA.zhibeginif bA.xi 0 the

18、n write(#8#8);write(bA.xi, x, bA.zhi, +);b := bA.nxt;endelsebeginif bA.xi + aA.xi 0 thenbeginif bA.xi + aA.xi 0 then write(#8 #8);write(bA.xi + aA.xi, x, bA.zhi, +);end;b := bA.nxt;a := aA.nxt;end;end;while a nil dobeginif aA.xi 0 then write(#8 #8);write(aA.xi, x, aA.zhi, +);a := aA.nxt;end;while b

19、nil dobeginif bA.xi 0) and (x0) and (yw; 直至隊空為止end;beginfillchar(bz,sizeof(bz),true);num:=0;write(input file:);readln(name);assign(int,name);reset(int);readln(int,m,n);for i:=1 to m dobegin readln(int,s);for j:=1 to n dobegin pici,j:=ord(sj)-ord(0);if pici,j=0 then bzi,j:=false;end;end;close(int);fo

20、r i:=1 to m dofor j:=1 to n do if bzi,j then doing(i,j);在 矩陣中尋找細(xì)胞 writeln(NUMBER of cells=,num);readln;end.迭代與遞推本次我們想與大家共同探討一下迭代與遞推。在計算機數(shù)值程序設(shè)計中，迭代與遞推是兩個重 要的基礎(chǔ)算法。一、迭代許多的實際問題都能轉(zhuǎn)化為解方程F(x)=0的實數(shù)解的問題。求根可以直接從方程出發(fā)，逐步縮 小根的存在區(qū)間，把根的近似值逐步精確到要以滿足具體實際問題的需要為止，該算法稱為迭代。 迭代的一般原則可以用一個數(shù)學(xué)模型來描述，現(xiàn)要求出方程F(x)=0的解：先設(shè)F(x)=G(x)

21、-x，則方 程 F(x)=0 可化為 x=G(x)，這就產(chǎn)生了一個迭代算法的數(shù)學(xué)模型：Xn+1 = G(Xn)從某一個數(shù)X0出發(fā)，按此迭代模型，求出一個序列：X0，X1，X2，X3，Xn-2，Xn-1，Xn當(dāng)Xn-Xn-1小于一個特定值(誤差許可值)時，XeXn-1eXn，這時可認(rèn)定x=G(x)。也就 是說，求出的Xn已經(jīng)可以作為原方程f(x)=0根的近似值了。設(shè)誤差許可值為A，則迭代算法的NS圖如圖1。圖1迭代算法NS框圖迭代算法的關(guān)鍵在于確定迭代函數(shù)G(x)。確定G(x)時需保證產(chǎn)生的迭代序列Xn 是否能使 兩個相鄰的數(shù)之間的差距越來越小(即兩數(shù)的差值越靠近誤差值，我們稱這樣的序列為收斂序

22、列)， 因為只有這樣才能使根的存在范圍越來越小，從而為根的取得創(chuàng)造條件。例1求2的算術(shù)平方根(不使用內(nèi)部函數(shù))。分析:使用迭代算法來解決這個問題，使用迭代法可以先設(shè)X=SQRT(2)-1，則求2的算術(shù)平方 根的近似值就可以轉(zhuǎn)化為求X(X+2)=1的正根。列出等價方程X=1/(X+2)，以1/(X+2)為迭代函數(shù)，以0為初始近似值X0，誤差值設(shè)定為0.0000001，則程序可寫成：program ex11_7;const a=0.0000001;var x0,x1,X:real;beginx0:=0;x1:=1/(x0+2);while abs(x1-x0)a dobeginx0:=x1;x1:

23、=1/(x0+2);end;x:=x1+1; 將X1的值轉(zhuǎn)為2的算術(shù)平方根writeln(sqrt(2)=,x);end.程序的輸出結(jié)果如下：SQRT(2)=1.4142135516E+00開始時，迭代函數(shù)的根的近似值設(shè)定在0,0.5之間，由于區(qū)間寬度大于給定誤差許可值，于是 再進行迭代運算，產(chǎn)生下一個區(qū)間0.4,0.5；其寬度仍然大于誤差許可值，再產(chǎn)生下一個區(qū)間；如此反復(fù)，直到區(qū)間的寬度小于誤差給定 值時，則表明在該區(qū)間中，任意選擇一個數(shù)都可以滿足根的近似值要求了。為方便起見，取下該區(qū) 間的邊界置作為近似值。這就是迭代算法的一般原則的體現(xiàn)了。二、.遞推對于一個的序列來說，如果已知它的通項公式

24、(即表達位置與位置上的數(shù)據(jù)的關(guān)系的公式)那 么，要求出數(shù)列中某項之值是十分容易的。但是，在許多情況下，要得到數(shù)列的通項公式是很困難 的，甚至無法得到。然而，一個有規(guī)律的數(shù)列的相鄰位置上的數(shù)項之間通常存在著一定的關(guān)系，我 們可以借助已知的項，利用特定的關(guān)系逐項推算出它的后繼項的值，如此反復(fù)，直到找到所 需的那一項為止，這樣的方法稱為遞推算法。遞推算法的首要問題是得到相鄰的數(shù)據(jù)項間的關(guān)系(即遞推關(guān)系)。遞推算法避開了求通項公項 的麻煩，把一個復(fù)雜的問題的求解，分解成了連續(xù)的若干步簡單運算。一般說來，可以將遞推算法 看成是一種特殊的迭代算法。例2著名的菲波納葜(Fibonacci)數(shù)列，其第一項為0

25、，第二項為1，從第三項開始，其每一項都是前兩項的和。編程求出該數(shù)列第N項數(shù)據(jù)。分析：按菲波納葜?jǐn)?shù)列的原則，數(shù)列為：0 1 1 2 3 5 8 13 21 34 55無疑地，尋找其項數(shù)位置與項值的關(guān)系(即通項公式)是非常困難的。而根據(jù)該數(shù)列的形成規(guī) 則，其有一個的公式即Un=Un-1 + Un-2表明了相鄰的數(shù)據(jù)項之間的明顯關(guān)系。因此，可以其作為遞推公式，以已知項0與1為起點，逐項 產(chǎn)生第3項、第4項、，直到取得需要的第N項為止。在其遞推算法的語言實現(xiàn)上，可取J、K、P三個變量，分別表示前二項、前一項與當(dāng)前項，J、K 分別取初值0與1。第一次通過遞推公式P=J+K得到第三項，并進行移位，即J取K

26、值、K取P值， 為下次遞推作準(zhǔn)備；如此反復(fù)，經(jīng)過N-2次的遞推，P就是第N項的值(第1次產(chǎn)生的是3 項的值)。源程序如下：program ex11_8;varn,i,j,k,p:longint;beginwrite(N=);readln(n);i:=2;j:=0;k:=1;repeatinc(i);p:=j+k;j:=k;k:=p;until i=n;writeln(F(,n,)=,p);end.菲波納葜?jǐn)?shù)列的遞推明確地體現(xiàn)了遞推算法程序設(shè)計的一般原則，即遞推公式取得。1 例3數(shù)字三角形。如下所示為一個數(shù)字三角形。請編一個程序計算從頂?shù)降? 8的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字總和最大。只

27、要求輸出總和。1、一步可沿左斜線向下或右斜線向下走；2、角形行數(shù)小于等于100；3、三角形中的數(shù)字為0，1,，99；45265測試數(shù)據(jù)通過鍵盤逐行輸入，如上例數(shù)據(jù)應(yīng)以如下所示格式輸入：573 88 1 07 4 44 5 2 6 5分析：此題解法有多種，從遞推的思想出發(fā)，可以設(shè)想，當(dāng)從頂層沿某條路徑走到第I層向第 I+1層前進時，我們的選擇一定是沿其下兩條可行路徑中最大數(shù)字的方向前進，為此，我們可以采用 倒推的手法，設(shè)ai，j存放從i，j出發(fā)到達 n 層的最大值，則 ai，j=maxai，j+ai+1, j，ai，j+ai+1, j+1，a1, 1即為所求的 數(shù)字總和的最大值。源程序如下：pr

28、ogram ex11_9;var n,j,i:integer;a:array1.100,1.100 of integer;beginread(n);for i:=1 to n dofor j:=1 to i doread(ai,j);for i:=n-1 downto 1 dofor j:=1 to i dobeginif ai+1,j=ai+1,j+1 then ai,j:= ai,j+ai+1,jelse ai,j:=ai,j+ai+1,j+1;end;writeln(a1,1);end.遞歸在(四)中，我們了解了迭代與遞推。與迭代、遞推相對應(yīng)的算法為遞歸，本趣談數(shù)據(jù)結(jié)構(gòu)， 我們就來談一談

29、遞歸算法。遞歸算法作為計算機程序設(shè)計中的一種重要的算法，是較難理解的算法之一。簡單地說，遞歸 就是編寫這樣的一個特殊的過程，該過程體中有一個語句用于調(diào)用過程自身(稱為遞歸調(diào)用)遞歸 過程由于實現(xiàn)了自我的嵌套執(zhí)行，使這種過程的執(zhí)行變得復(fù)雜起來，其執(zhí)行的流程可以用圖1所示。圖1遞歸過程的執(zhí)行流程從圖1可以看出，遞歸過程的執(zhí)行總是一個過程體未執(zhí)行完，就帶著本次執(zhí)行的結(jié)果又進入另 一輪過程體的執(zhí)行，如此反復(fù)，不斷深入，直到某次過程的執(zhí)行遇到終止遞歸調(diào)用的條件成 立時，則不再深入，而執(zhí)行本次的過程體余下的部分，然后又返回到上一次調(diào)用的過程體中，執(zhí)行 其余下的部分，如此反復(fù)，直到回到起始位置上，才最終結(jié)束

30、整個遞歸過程的執(zhí)行，得到相 應(yīng)的執(zhí)行結(jié)果。遞歸過程的程序設(shè)計的核心就是參照這種執(zhí)行流程，設(shè)計出一種適合逐步深入，而 后又逐步返回的遞歸調(diào)用模型，以解決實際問題。利用遞歸調(diào)用程序設(shè)計技術(shù)可以解決很復(fù)雜但規(guī)律性很強的問題，并且可以使程序變得十分簡 短。例1利用遞歸調(diào)用手段編程計算N!。分析：根據(jù)數(shù)學(xué)知識，1!=1,正整數(shù)N的階乘為：N*(N-1)*(N-2)*2*1，該階乘序列可轉(zhuǎn)換 為求N*(N-1)!，而(N-1)!以可轉(zhuǎn)換為(N-1)*(N-2)!，直至轉(zhuǎn)換為2*1!，而1!=1。源程序如下：program ex11_10;varn:byte;t:extended;procedure fin

31、d(n:byte);beginif n=1 then t:=1elsebeginfind(n-1);t:=t*n;end;end;beginwrite(N=);readln(n);find(n);writeln(N!=,t:1:0);end.在過程find中，當(dāng)N1時，又調(diào)用過程find，參數(shù)為N-1，這種操作一直持續(xù)到N=1為止。例如當(dāng)N=5時，find(5)的值變?yōu)?*find(4)，求find( 4)又變?yōu)?*find(3)，當(dāng)N= 1時遞歸停止，逐步返回到第一次調(diào)用的初始處，返回結(jié)果 5*4*3*2*1，即 5!。例2利用遞歸調(diào)用技術(shù)求菲波納葜?jǐn)?shù)列的第N項。分析：我們已經(jīng)知道菲波納葜?jǐn)?shù)

32、列的各數(shù)列的產(chǎn)生可用下列公式表示：U1=0 U2=l Un=Un-1 + Un-2 (當(dāng) n2 時)因此當(dāng)N大于2時，求第N項值可轉(zhuǎn)化為求第N-1項值與第N-2項值的和；而求第N-1項又可轉(zhuǎn)化為求N-2項值與N-3項的和，相應(yīng)地，求N-2項值可轉(zhuǎn)化為求N-3項值和N-4項值的和；如此反復(fù)，直至轉(zhuǎn)化為求第1項或第2項值，而第1項與第2項為已 知值1和2。源程序:program ex11_11;varn:byte;a:array1.100 of longint;function f(n:byte):longint;var i:longint;beginif an-10 then i:=an-1el

33、se i:=f(n-1);if an-20 then i:=i+an-2else i:=i+f(n-2);an:=i;f:=i;end;beginwrite(N=);readln(n);fillchar(a,sizeof(a),0);a1:=1;a2:=1;writeln(F(,n,)=,f(n);end.本程序采用了函數(shù)遞歸，函數(shù)F的執(zhí)行比較復(fù)雜。函數(shù)F由于存在著兩次的遞歸調(diào)用，使遞歸調(diào)用產(chǎn)生執(zhí)行流程的二叉樹行式，大家可參照圖2來理解這個執(zhí)行過程。為方便起見，設(shè)定N=5，圖中的數(shù)碼表示遞歸執(zhí)行的順序。F 0)1F(4) + F(3)11F(3) + F(2)F+F1 | 1 |F+F11 1

34、1010圖2 F函數(shù)的二叉樹執(zhí)行流程遞歸調(diào)用技術(shù)的運用，是在犧牲計算機內(nèi)存空間和程序執(zhí)行速度的基礎(chǔ)上得到的。因為在遞歸 調(diào)用的執(zhí)行過程中，系統(tǒng)必須花費時間與空間以棧的方式記下每次調(diào)用的返回位置地址及每一次過 程執(zhí)行的中間結(jié)果，以便當(dāng)遞歸調(diào)用終止條件成立時，能沿著逐步深入的路線逐步返回，取得這 些數(shù)據(jù)，最終準(zhǔn)確地回到初始調(diào)用處。比如，同是解決菲波納葜?jǐn)?shù)列問題的程序，使用遞推就比使 用遞歸算法設(shè)計的程序執(zhí)行速度快了許多。當(dāng)一個問題蘊含著遞歸關(guān)系且結(jié)構(gòu)比較復(fù)雜時，采用一般的算法，不僅給程序的設(shè)計帶來許多困 難，而且也會給設(shè)計出的程序帶來篇幅大、可讀性差的缺點，這時采用遞歸調(diào)用技術(shù)來設(shè)計程序則 會帶來

35、相反的效果。例3相傳在古印度的布拉瑪婆羅門圣廟的僧侶在進行一種被稱為漢諾塔的游戲，其裝置是一 塊銅板，上面有三根桿(編號A、B、C)，A桿上自下而上、由大到小按順序串上64個金盤(如圖 3)。游戲的目標(biāo)是把【演示程序：DEM00_02.rar】A桿上的金盤全部移到C桿上，并仍原有順序疊好。條件是每次只能移動一個盤，并且在每次 移動都不允許大盤移到小盤之上。現(xiàn)要求利用遞歸調(diào)用技術(shù)給出N個盤從A桿移到C桿的移動過程。 TOC o 1-5 h z rlhIIIII1IIIIHHIIIIHH IIIIHH IIIIA桿B桿匚桿圖3N階漢諾塔分析：這個移動過程很復(fù)雜與煩瑣，但規(guī)律性卻很強。使用遞歸調(diào)用技

36、術(shù)來解決這個移動過程， 先得找到一個遞歸調(diào)用模型。想要得到漢諾塔問題的簡單解法，著眼點應(yīng)該是移動A桿最底部的大 盤，而不是其頂部的小盤。不考慮64個盤而考慮N個盤的一般情況。要想將A桿上的N個盤移至 C桿，我們可以這樣設(shè)想：以C盤為臨時桿，從A桿將1至N-1號盤移至B桿。將A桿中剩下的第N號盤移至C桿。以A桿為臨時桿，從B桿將1至N-1號盤移至C桿。我們看到，步驟2只需移動一次就可以完成；步驟1與3的操作則完全相同，唯一區(qū)別僅在于各 桿的作用有所不同。這樣，原問題被轉(zhuǎn)換為與原問題相同性質(zhì)的、規(guī)模小一些的新問題(圖4)。即： HANOI(N,A,B,C)可轉(zhuǎn)化為 HANOI(N-1,A,C,B)

37、與 HANOI(N-1,B,A,B)其中HANOI中的參數(shù)分別表示需移動的盤數(shù)、起始盤、臨時盤與終止盤，這種轉(zhuǎn)換直至轉(zhuǎn)入 的盤數(shù)為0為止，因為這時已無盤可移了。這就是需要找的遞歸調(diào)用模型。 TOC o 1-5 h z IIIIIIIIrIHIIIII1IIIIHHIIIIHH III1A桿B桿匚桿圖4 N-1階漢諾塔源程序如下：program ex11_12;vara,b,c:char;n:byte;procedure hanoi(n:byte;a,b,c:char);beginif n0 thenbeginhanoi(n-1,a,c,b);writeln(Move ,a, to ,c);ha

38、noi(n-1,b,a,c);end;end;begina:=A;b:=B;c:=C;write(N=);readln(n);hanoi(n,a,b,c);end.如果說例1與例題的無法體現(xiàn)遞歸算法的獨特優(yōu)點，那么，例3的解法則很能說明問題，因為一 般的算法是很難解決這個問題的，而過程HONOI只用了 4個語句就解決這個難題。不過要說明的 是，按照漢諾塔的移動原則，將N個盤從A桿移動到C桿需要移動盤的次數(shù)是2的N次幕減1 ， 那么64個盤移動次數(shù)就是 18446744073709511615,近19億億次。這是一個天文數(shù)字，即使一臺功能很強的現(xiàn)代計算機來解 漢諾塔問題，恐怕也需要很長的時間，因

39、此要想得到結(jié)果，在運行程序時，輸入的N可不能太大。 據(jù)說布拉瑪婆羅門圣廟的僧侶聲稱，漢諾塔游戲結(jié)束就標(biāo)志著世界末日的到來，現(xiàn)在看來確實是有道理的。因為如果每秒移動一次，64 個盤則大約需近5800億年，而據(jù)科學(xué)家以能源角度推算，太陽系的壽命只不過150億年而已。(1)非波那契(Fibonacci)數(shù)列.數(shù)列的遞歸公式如下：F = 11F =12(n=1)(n=2)F =七1+ 七 2 (n Z 3)PASCAL程序按照上面的遞歸公式，可寫出如下program fibonacci;varn: integer;Funtion fb(n: integer): integer; beginif n 0

40、g(m -1,2n) + nm 0,n 0遞歸的描述一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當(dāng)邊界條件不滿足時，遞歸前進; 當(dāng)邊界條件滿足時，遞歸返回。因此，在考慮使用遞歸算法編寫程序時，應(yīng)滿足兩點：1)該問題能 夠被遞歸形式描述；2)存在遞歸結(jié)束的邊界條件。遞歸的能力在于用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易 懂。給出一棵二叉樹的中序與后序排列。求出它的先序排列。分析通過對比二叉樹的中序與后序排列，我們可以找出根節(jié)點及左右子樹。同樣的，有可以通過 對比左子樹的中序與后序排列，找出左子樹的根節(jié)點可見，該問題能夠被遞歸描述。當(dāng)找到最 后一個根節(jié)點時，遞

41、歸無法再進行下去，這就是遞歸結(jié)束的邊界條件。由此可見，遞歸算法中常常 隱含了分治思想。程序如下：program chu01_3;var z,h: string;procedure find(a,b:string);vars,l : integer;beginl:=length(b);if l=1 then Write(b) (邊界條件及遞歸返回段elsebegin 遞歸前進段Write(bl);s:=pos(bl,a);if s-10 then find(copy(a,1,s-1),copy(b,1,s-1); 遞歸左子樹if l-s0 then find(copy(a,s+1,l-s),co

42、py(b,s,l-s); 遞歸右子樹 end;end;beginReadln(z);Readln(h);Find(z,h);Readln;end.遞歸的應(yīng)用經(jīng)典遞歸例如hanoi塔問題：經(jīng)典的遞歸，原問題包含子問題。有些問題或者數(shù)據(jù)結(jié)構(gòu)本來就是遞歸描 述的，用遞歸做很自然。遞歸與遞推利用遞歸的思想建立遞推關(guān)系，如由兔子生崽而來的fibonacci數(shù)列。但遞推由于沒有返回段， 因此更為簡單，有時可以直接用循環(huán)實現(xiàn)。分治不少分治方法是源于遞歸思想，或是遞歸分解+合并處理?；厮菀?guī)模較小的問題用回溯解決比較自然。注意遞歸前后要保證現(xiàn)場的保存和恢復(fù)，即正確的轉(zhuǎn)化 問題。動態(tài)規(guī)劃動態(tài)規(guī)劃的子問題重疊性質(zhì)與

43、遞歸有某種相似之處。遞歸+動態(tài)修改查表是一種不錯的建立動態(tài) 規(guī)劃模型的方法。其他其他么，就是不好歸類。例如表達式處理，排列組合等。附帶說一下，用遞歸來處理打印方案 的問題還是很方便的。求把一個整數(shù)n無序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。分析這是一道動態(tài)規(guī)劃題，動態(tài)方程如下：fi-1,j+fi,j-i+1(j mod0) and (j div1)fi,j:= fi-1,j (i=j)fi-1,j+fi,j-i (else)s:=f(k,n-k)本題可以用循環(huán)來實現(xiàn)遞推，也可以考慮用遞歸求解。主過程如下：方案一：Procedure work(I,j:longint; var s:longi

44、nt);Var t:longint;BeginIf (i=1) or (j=1) then s:=1Else if (i=0) or (j=0) then s:=0Else beginif (j mod i=0) and (j div i=1) thenbeginwork(i-1,j,s);t:=s;work(i,j-1,s);s:=s+t+1;endelse if (i=j) thenwork(i-1,j)else beginwork(i-1,j,s);t:=s;work(I,j-1,s);s:=s+t;end;End;方案二：procedure search(v,w,last:byte);

45、var i:byte;beginif w=0 then inc(count)elseif w=1 thenif v=last then search(0,0,0) elseelse for i:=last to v-1 do search(v-i,w-1,i);end;可以看出，方案一的程序較為冗長，消耗棧空間較大；而方案二較為簡潔明了，所用的棧空間 也較小，效率較高。因此，使用遞歸算法也有一個優(yōu)化問題。算法的簡潔與否直接制約了程序的可 行性和效率?？偨Y(jié)遞歸使一些復(fù)雜的問題處理起來簡單明了，尤其在學(xué)習(xí)算法設(shè)計、數(shù)據(jù)結(jié)構(gòu)時更能體會到這一 點。但是，遞歸在每一次執(zhí)行時都要為局部變量、返回地址分配棧

46、空間，這就降低了運行效率，也 限制了遞歸的深度。因此，在必要的時候可以只使用遞歸的思想來求解，而程序則轉(zhuǎn)用非遞歸的方 式書寫。遞歸習(xí)題：一.九連環(huán)問題：有N(2=N=9)個環(huán)，拆裝這些環(huán)的規(guī)則：第一個環(huán)可以隨意拆裝,第二個環(huán)只有在第一環(huán)已裝上 時可以拆裝;第I個環(huán)只有在第i-1環(huán)已裝上，且第i-2，第i-3.第1環(huán)都拆下時可以裝拆. 編程序描述拆下N個環(huán)的過程.打印0一N(0=N=9)的所有路徑：1- 3 5 - 7 - 90 2- 4 6 - 8剔除多余括號鍵盤輸入一個含有括號的四則運算表達式，可能含有多余的括號，編程整理該表達式，去掉所 有多余的括號，原表達式中所有變量和運算符相對位置保持

47、不變，并保持與原表達式等價。例：輸入表達式應(yīng)輸出表達式a+(b+c)a+b+c(a*b)+c/da*b+c/da+b/(c-d)a+b/(c-d)注意輸入a+b時不能輸出b+a。表達式以字符串輸入，長度不超過255。輸入不要判錯。所有變量為單個小寫字母。只是要求去掉所有多余括號，不要求對表達式化簡。汽車問題有一個人在一個公共汽車站上，從12:00到12:59觀察公共汽車到達本站的情況，該站被多條 公共汽車線路所公用，他記下了公共汽車到達本站的時刻。在12:00-12:59這個期間內(nèi)，同一條線路上的公共汽車以相同的時間間隔到站。時間單位用“分”表示，從0到59。每條公共汽車線路上的車至少到達本站

48、兩次。在本例的公共汽線路數(shù)一定W17。來自不同線路的公共汽車可能在同一時刻到達本站。不同公共汽車線路的車首次到站時間和(或)(and/or )時間間隔(到站的)可能相同。如果 兩條公共汽車線路的車有相同的開始時間和相同的時間間隔，它們必須分開表示出來。請為公共汽車線路編一個調(diào)度表，目標(biāo)是：公共汽車線路數(shù)目最少的情況下，使公共汽車到達 本站的時刻滿足輸入數(shù)據(jù)的要求。對于每一公共汽車線路，輸出其起始時刻(第一次到達本站)和 到達本站的時間間隔。輸入數(shù)據(jù)：輸入文件INPUT.TXT首先給出觀察者所看到的駛進本站的公共汽車數(shù)n （nW300）,下面以遞增 順序給出各公共汽車到達本站的時刻。我們的例子是

49、： 17 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53 輸出數(shù)據(jù)：在輸出文件OUTPUT.TXT中列一個表，每一行表示一條公共汽車線路。行中第一個數(shù)字表示該線 路上的公共汽車的首次到達本站的時刻；第二個數(shù)字表示該線路上的公共汽車兩次到達本站的時間 間隔。時間的單位是分。各公共汽車線路在表中出現(xiàn)的先后順序沒有重要性（次序可任意）。若 有多個等價解，僅需輸出其中一個。我們例子的輸出文件的內(nèi)容為：0 133 125 8（六）一一搜索與回溯本講，我們來談?wù)勊阉髋c回溯。搜索與回溯是計算機解題中常用的算法，有很多問題無法根據(jù) 某種確定的計算法則來求解，此時

50、可以利用搜索與回溯的技術(shù)求解?；厮菔撬阉魉惴ㄖ械囊环N控制 策略。它的基本思想是：為了求得問題的解，先選擇某一種可能情況向前探索，在探索過程中，一 旦發(fā)現(xiàn)原來的選擇是錯誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進行，直至得到解或 證明無解。如迷宮問題：進入迷宮后，先隨意選擇一個前進方向，一步步向前試探前進，如果碰到 死胡同，說明前進方向已無路可走，這時，首先看其它方向是否還有路可走，如果有路可走，則沿 該方向再向前試探；如果已無路可走，則返回一步，再看其它方向是否還有路可走；如果有路可走， 則沿該方向再向前試探。按此原則不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無 解為止。n皇

51、后問題【演示程序：DEM00_03exe，源程序：xoi00_11.pas】（1）問題描述：求出在一個nxn的棋盤上，放置n個不能互相捕捉的“皇后”的所有布局。（2）算法分析：這是來源于國際象棋的一個問題?；屎罂梢郧?、后、左、右和沿著對角線方向相互捕捉。如圖所 示，一個皇后放在棋盤4行3列位置上，棋盤打的位置就不能再放置皇后。一個皇后的捕捉位置示意圖上圖提示我們，一個合適的解應(yīng)是在每列、每行確實有一個皇后，且在一條對角線上最多只有一 個皇后。在開發(fā)程序之前，設(shè)定表示棋盤的數(shù)據(jù)結(jié)構(gòu)是一個nxn數(shù)組。每一個位置代表棋盤上的一個方格。 然而考慮到一個合理的解中每列、每行只能放置一個皇后，棋盤也可用一

52、個一維數(shù)組來表示。數(shù)組 的每一個元素代表棋盤的一列，該元素的值是皇后在該列上的行位置。設(shè)數(shù)組名為col,對于圖有 col3=4。它表示第3列的第4行有一個皇后。為找到一個解，必須從空布局開始，每放置一個皇后要檢查布局是否合理。在合理的情況下，試 探找下一個皇后的位置；如果布局不合理，就改變布局。重復(fù)檢查、試探或檢查、改變位置，直到 找到最后一個皇后的合理位置，這時就找到一個合理的布局。重復(fù)以上過程直到無法再改變皇后位 置為止，就可找到所有合理的布局。通過以上討論，得到程序的第一層描述如下：VARn, m : 0.MAXSIZE; n為皇后總數(shù)目，m為當(dāng)前已放置的皇后數(shù)good : boolea

53、n;布局合理與否col : ARRAY 0.MAXSIZE OF 0.MAXSIZE; 解BEGINread(n);輸入皇后數(shù)目m:=0;good:=true; 空布局是合理的REPEATIF good THENIF m=n THEN 搜索到一個解BEGINprint;打印change改變布局，繼續(xù)找解ENDELSEextend 繼續(xù)試探下一個皇后位置ELSEchange;check檢查布局是否合理UNTIL m=0皇后位置不能再改變END.子過程change改變布局就是試探當(dāng)前皇后m的下一個位置，即試著放在下一列上 (colm:=colm+1)。如果colm=n，說明當(dāng)前皇后m無位置可放，必

54、須返回到上一個皇后的狀態(tài)，改 變第m-1個皇后位置。為了防止存取不存在的col0，給數(shù)組col增設(shè)一個元素col0，它的初值為0。PROCEDURE change;BEGINIF colm=n THENm :=m-1;colm:=colm+1END;子過程extend就是試探下一個皇后的位置，這時要盡可能試探完所有的位置，即從第一列放起：PROCEDURE extend;BEGINm :=m+1;colm:=1END;主要的困難是過程check。見圖中，在nxn棋盤上對m列上的皇后配置是檢查四個方向；縱向。由問題的數(shù)據(jù)結(jié)構(gòu)保證一列只放一個皇后。橫向。對所有k(k=1,2,-,m-1)檢查不等式

55、colkcolm是否成立。左高右低對角線。共有(2n-1)條這樣的對角線。同一條對角線上的不同位置它們的行號值與列號值之 差相等。所謂檢查m列上的皇后配置是否與前面的皇后在同一條左高右低對角線上，就是檢查對所 有k(k=1,2,.,m 1)不等式成立：(colk-k)(colm-m)。左低右高對角線。類似3,檢查m列上的皇后配置是否與前面的皇后在同一條左低右高對角線上，就 是檢查對所有的k(k=1,2,.,m-1)不等式成立：(colk+k)(colm+m)?！驹闯绦颉?n皇后問題程序xoi00_11.pasPROGRAM xoi00_11(input, output);CONSTmaxsiz

56、e=25;VARm,n: 0.maxsize;good: boolean;col: ARRAY 0.maxsize OF 0.maxsize;counts:integer;PROCEDURE print;VARi , j : 0.maxsize;BEGIN (轉(zhuǎn)置輸出FOR j:=1 TO n DO BEGINi:=colj;writeln(i, :(3+i*5),Q);writelnEND;writeln(腭,*);writelnEND;PROCEDURE extend;BEGINm:=m+1;colm:=1END;PROCEDURE change;BEGINIF colm=n THEN m

57、:=m-1;colm:=colm+1END;PROCEDURE check;VARk,upd,downd:integer;BEGIN downd:=colm-m; upd:=colm+m;k:=1;good:=true;WHILE good AND (km) DOBEGINgood:=(colkcolm) AND(colk-k)downd)AND(colk+k)upd);k:=k+1ENDEND;BEGINwriteln(Input n (Maxsize=25):);read(n);Writeln;IF (nmaxsize) THENwriteln(INVALID BOARD SIZE)ELS

58、EBEGINcounts:=0;m:=0;col0:=0;good:=true;REPEATIF good THENIF m=n THENBEGINcounts := counts+1;print;changeENDELSEextendELSEchange;checkUNTIL m=0;writeln;writeln(SEARCHING COMPLETED.);writeln(There are ,counts, layouts found.)ENDEND.樹與二叉樹有了前面的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，這一講開始，我們談點較深入的數(shù)據(jù)結(jié)構(gòu)知識。本講，我們先來談 談樹，建立樹的基本概念與基本的處理方式。樹是

59、一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素(在樹中稱為結(jié)點)按分支關(guān)系組織起 來的結(jié)構(gòu)，很象自然界中的樹那樣。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種社會 組織機構(gòu)都可用樹形象表示。樹在計算機領(lǐng)域中也得到廣泛應(yīng)用，如在編譯源程序如下時，可用樹 表示源源程序如下的語法結(jié)構(gòu)。又如在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)也是信息的重要組織形式之一。一 切具有層次關(guān)系的問題都可用樹來描述。一、樹的概述樹結(jié)構(gòu)的特點是：它的每一個結(jié)點都可以有不止一個直接后繼，除根結(jié)點外的所有結(jié)點都有且只 有一個直接前趨。以下具體地給出樹的定義及樹的數(shù)據(jù)結(jié)構(gòu)表示。樹的定義樹是由一個或多個結(jié)點組成的有限集合，其中：1.必有一

60、個特定的稱為根(ROOT )的結(jié)點；2.剩下的結(jié)點被分成n=0個互不相交的集合T1、T2、.Tn,而且，這些集合的每一個又都是 樹。樹T1、T2、.Tn被稱作根的子樹（Subtree）。例如，一個集團公司，可以描述如下：它很象一株倒懸著的樹，從樹根到大分枝、小分枝、直到葉子把數(shù)據(jù)聯(lián)系起來，這種數(shù)據(jù)結(jié)構(gòu) 就叫做樹結(jié)構(gòu)，簡稱樹。樹中每個分叉點稱為結(jié)點，起始結(jié)點稱為樹根，任意兩個結(jié)點間的連接關(guān) 系稱為樹枝，結(jié)點下面不再有分枝稱為樹葉。結(jié)點的前趨結(jié)點稱為該結(jié)點的雙親，結(jié)點的后趨結(jié) 點稱為該結(jié)點的子女或孩子，同一結(jié)點的子女之間互稱兄弟。（二）樹的表示樹中每個結(jié)點的內(nèi)容分兩部分表示：1.結(jié)點的性質(zhì)；2.結(jié)