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

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

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

3、；2、退棧（POP）算法若TOPW0，則給出下溢信息，作出錯(cuò)處理（退棧前先檢查是否已為空棧，空則下溢；不空則 作）；X=S（SOP），（退棧后的元素賦給X）；TOP=TOP-1,結(jié)束（棧指針減1，指向棧頂）。進(jìn)棧、出棧的Pascal實(shí)現(xiàn)過(guò)程程序：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;對(duì)于出棧運(yùn)算中的“下溢”，程序中僅給出了一個(gè)標(biāo)志信息，而在實(shí)際應(yīng)用中，下溢可用來(lái)作為 控制程序轉(zhuǎn)移的判斷標(biāo)志，是十分有用的。對(duì)于入棧運(yùn)算中的“上溢”則是一種致命的錯(cuò)誤，將使 程序無(wú)法繼續(xù)運(yùn)行，所以要設(shè)法避免。堆棧的數(shù)組模擬十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是實(shí)現(xiàn)計(jì)算的基本問(wèn)題，解決方法很多，下面給出一中算法原理： N=（N div d）Xd+N mod d （其中div為整除運(yùn)算，mo

5、d為求余運(yùn)算）。例如：（1348）10=（2504）8運(yùn)算過(guò)程如下：NN div 8N mod 894131、1、填空:NN div 8N mod 8134816841682102125202（9413）=（）=（）=（）1081622、下面的程序?qū)崿F(xiàn)這個(gè)轉(zhuǎn)換過(guò)程，請(qǐng)補(bǔ)充完整。數(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、火車(chē)站列車(chē)調(diào)度示意圖如下，假設(shè)調(diào)度站兩側(cè)的軌道為單向 行駛軌道。1、1、如果進(jìn)站的車(chē)廂序列為123,則可能的出戰(zhàn)車(chē)廂序列是 什么？2、2、如果進(jìn)展進(jìn)站的車(chē)廂序列為123456，問(wèn)能否得到135426 和435612的出站序列。棧的用途極為廣泛，在源程序編譯中表達(dá)式的計(jì)算、過(guò)程的嵌套調(diào)用和遞歸調(diào)用等都要用到棧，下面以表達(dá)式計(jì)算為

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

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

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

10、許含括號(hào))，輸出算術(shù)表達(dá)式的值。設(shè)輸入的表達(dá)式串是合法的。分析:建立兩個(gè)棧，一個(gè)是 操作數(shù)棧(number)，一個(gè)是運(yùn)算符棧(symbol)，根據(jù)運(yùn)算符的優(yōu)先級(jí)對(duì)兩個(gè)棧進(jìn)行相應(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; 算符入棧運(yùn)算begininc(p);symbolp := si;end;procedure pop; 運(yùn)算符棧頂元素出棧，并

11、取出操作數(shù)棧元素完成相應(yīng)的運(yùn)算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ùn)算符的優(yōu)先級(jí)別，建立標(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 左括號(hào)處理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 右括號(hào)處理beginwhile

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

14、型error 2其他非法字符錯(cuò)誤類(lèi)型error 3如輸入：It is 12!輸出：error 1 2 3輸入： i am ,a student輸出：42、2、編碼解碼：從鍵盤(pán)輸入一個(gè)英文句子，設(shè)計(jì)一個(gè)編碼、解碼程序。（string）編碼過(guò)程：先鍵入一個(gè)正整數(shù)N（1=N 0) and (tb 0) do 當(dāng)兩個(gè)表均不空時(shí)begin 比較兩表指針指向的項(xiàng)指數(shù)，輸出指數(shù)小的項(xiàng)系數(shù)和指數(shù)，同時(shí)改變?cè)摫碇羔榠f 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 若兩表指針指向的項(xiàng)指數(shù)相等,則兩系數(shù)相加輸出，兩表指針同時(shí)改變if btb.xi + ata.xi 0 thenbeginif btb.xi + ata.xi 0 do 若有一表空，則輸出另一表的剩余項(xiàng)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àng)式相加的鏈表實(shí)現(xiàn)program ex11_5b;typelink = Mode;node = recordzhi, xi: integer;nxt: link;end;vara, b: link;n: integer;procedure createfifo(var c: link); 建立多項(xiàng)式系數(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; 直至隊(duì)空為止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.迭代與遞推本次我們想與大家共同探討一下迭代與遞推。在計(jì)算機(jī)數(shù)值程序設(shè)計(jì)中，迭代與遞推是兩個(gè)重 要的基礎(chǔ)算法。一、迭代許多的實(shí)際問(wèn)題都能轉(zhuǎn)化為解方程F(x)=0的實(shí)數(shù)解的問(wèn)題。求根可以直接從方程出發(fā)，逐步縮 小根的存在區(qū)間，把根的近似值逐步精確到要以滿(mǎn)足具體實(shí)際問(wèn)題的需要為止，該算法稱(chēng)為迭代。 迭代的一般原則可以用一個(gè)數(shù)學(xué)模型來(lái)描述，現(xiàn)要求出方程F(x)=0的解：先設(shè)F(x)=G(x)

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

22、列)， 因?yàn)橹挥羞@樣才能使根的存在范圍越來(lái)越小，從而為根的取得創(chuàng)造條件。例1求2的算術(shù)平方根(不使用內(nèi)部函數(shù))。分析:使用迭代算法來(lái)解決這個(gè)問(wèn)題，使用迭代法可以先設(shè)X=SQRT(2)-1，則求2的算術(shù)平方 根的近似值就可以轉(zhuǎn)化為求X(X+2)=1的正根。列出等價(jià)方程X=1/(X+2)，以1/(X+2)為迭代函數(shù)，以0為初始近似值X0，誤差值設(shè)定為0.0000001，則程序可寫(xiě)成：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開(kāi)始時(shí)，迭代函數(shù)的根的近似值設(shè)定在0,0.5之間，由于區(qū)間寬度大于給定誤差許可值，于是 再進(jìn)行迭代運(yùn)算，產(chǎn)生下一個(gè)區(qū)間0.4,0.5；其寬度仍然大于誤差許可值，再產(chǎn)生下一個(gè)區(qū)間；如此反復(fù)，直到區(qū)間的寬度小于誤差給定 值時(shí)，則表明在該區(qū)間中，任意選擇一個(gè)數(shù)都可以滿(mǎn)足根的近似值要求了。為方便起見(jiàn)，取下該區(qū) 間的邊界置作為近似值。這就是迭代算法的一般原則的體現(xiàn)了。二、.遞推對(duì)于一個(gè)的序列來(lái)說(shuō)，如果已知它的通項(xiàng)公式

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

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

26、值、K取P值， 為下次遞推作準(zhǔn)備；如此反復(fù)，經(jīng)過(guò)N-2次的遞推，P就是第N項(xiàng)的值(第1次產(chǎn)生的是3 項(xiàng)的值)。源程序如下：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è)計(jì)的一般原則，即遞推公式取得。1 例3數(shù)字三角形。如下所示為一個(gè)數(shù)字三角形。請(qǐng)編一個(gè)程序計(jì)算從頂?shù)降? 8的某處的一條路徑，使該路徑所經(jīng)過(guò)的數(shù)字總和最大。只

27、要求輸出總和。1、一步可沿左斜線(xiàn)向下或右斜線(xiàn)向下走；2、角形行數(shù)小于等于100；3、三角形中的數(shù)字為0，1,，99；45265測(cè)試數(shù)據(jù)通過(guò)鍵盤(pán)逐行輸入，如上例數(shù)據(jù)應(yīng)以如下所示格式輸入：573 88 1 07 4 44 5 2 6 5分析：此題解法有多種，從遞推的思想出發(fā)，可以設(shè)想，當(dāng)從頂層沿某條路徑走到第I層向第 I+1層前進(jìn)時(shí)，我們的選擇一定是沿其下兩條可行路徑中最大數(shù)字的方向前進(jìn)，為此，我們可以采用 倒推的手法，設(shè)ai，j存放從i，j出發(fā)到達(dá) 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.遞歸在(四)中，我們了解了迭代與遞推。與迭代、遞推相對(duì)應(yīng)的算法為遞歸，本趣談數(shù)據(jù)結(jié)構(gòu)， 我們就來(lái)談一談

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

30、整個(gè)遞歸過(guò)程的執(zhí)行，得到相 應(yīng)的執(zhí)行結(jié)果。遞歸過(guò)程的程序設(shè)計(jì)的核心就是參照這種執(zhí)行流程，設(shè)計(jì)出一種適合逐步深入，而 后又逐步返回的遞歸調(diào)用模型，以解決實(shí)際問(wèn)題。利用遞歸調(diào)用程序設(shè)計(jì)技術(shù)可以解決很復(fù)雜但規(guī)律性很強(qiáng)的問(wèn)題，并且可以使程序變得十分簡(jiǎn) 短。例1利用遞歸調(diào)用手段編程計(jì)算N!。分析：根據(jù)數(shù)學(xué)知識(shí)，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.在過(guò)程find中，當(dāng)N1時(shí)，又調(diào)用過(guò)程find，參數(shù)為N-1，這種操作一直持續(xù)到N=1為止。例如當(dāng)N=5時(shí)，find(5)的值變?yōu)?*find(4)，求find( 4)又變?yōu)?*find(3)，當(dāng)N= 1時(shí)遞歸停止，逐步返回到第一次調(diào)用的初始處，返回結(jié)果 5*4*3*2*1，即 5!。例2利用遞歸調(diào)用技術(shù)求菲波納葜?jǐn)?shù)列的第N項(xiàng)。分析：我們已經(jīng)知道菲波納葜?jǐn)?shù)

32、列的各數(shù)列的產(chǎn)生可用下列公式表示：U1=0 U2=l Un=Un-1 + Un-2 (當(dāng) n2 時(shí))因此當(dāng)N大于2時(shí)，求第N項(xiàng)值可轉(zhuǎn)化為求第N-1項(xiàng)值與第N-2項(xiàng)值的和；而求第N-1項(xiàng)又可轉(zhuǎn)化為求N-2項(xiàng)值與N-3項(xiàng)的和，相應(yīng)地，求N-2項(xiàng)值可轉(zhuǎn)化為求N-3項(xiàng)值和N-4項(xiàng)值的和；如此反復(fù)，直至轉(zhuǎn)化為求第1項(xiàng)或第2項(xiàng)值，而第1項(xiàng)與第2項(xiàng)為已 知值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í)行流程的二叉樹(shù)行式，大家可參照?qǐng)D2來(lái)理解這個(gè)執(zhí)行過(guò)程。為方便起見(jiàn)，設(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ù)的二叉樹(shù)執(zhí)行流程遞歸調(diào)用技術(shù)的運(yùn)用，是在犧牲計(jì)算機(jī)內(nèi)存空間和程序執(zhí)行速度的基礎(chǔ)上得到的。因?yàn)樵谶f歸 調(diào)用的執(zhí)行過(guò)程中，系統(tǒng)必須花費(fèi)時(shí)間與空間以棧的方式記下每次調(diào)用的返回位置地址及每一次過(guò) 程執(zhí)行的中間結(jié)果，以便當(dāng)遞歸調(diào)用終止條件成立時(shí)，能沿著逐步深入的路線(xiàn)逐步返回，取得這 些數(shù)據(jù)，最終準(zhǔn)確地回到初始調(diào)用處。比如，同是解決菲波納葜?jǐn)?shù)列問(wèn)題的程序，使用遞推就比使 用遞歸算法設(shè)計(jì)的程序執(zhí)行速度快了許多。當(dāng)一個(gè)問(wèn)題蘊(yùn)含著遞歸關(guān)系且結(jié)構(gòu)比較復(fù)雜時(shí)，采用一般的算法，不僅給程序的設(shè)計(jì)帶來(lái)許多困 難，而且也會(huì)給設(shè)計(jì)出的程序帶來(lái)篇幅大、可讀性差的缺點(diǎn)，這時(shí)采用遞歸調(diào)用技術(shù)來(lái)設(shè)計(jì)程序則 會(huì)帶來(lái)

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

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

37、與 HANOI(N-1,B,A,B)其中HANOI中的參數(shù)分別表示需移動(dòng)的盤(pán)數(shù)、起始盤(pán)、臨時(shí)盤(pán)與終止盤(pán)，這種轉(zhuǎn)換直至轉(zhuǎn)入 的盤(pán)數(shù)為0為止，因?yàn)檫@時(shí)已無(wú)盤(pán)可移了。這就是需要找的遞歸調(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.如果說(shuō)例1與例題的無(wú)法體現(xiàn)遞歸算法的獨(dú)特優(yōu)點(diǎn)，那么，例3的解法則很能說(shuō)明問(wèn)題，因?yàn)橐?般的算法是很難解決這個(gè)問(wèn)題的，而過(guò)程HONOI只用了 4個(gè)語(yǔ)句就解決這個(gè)難題。不過(guò)要說(shuō)明的 是，按照漢諾塔的移動(dòng)原則，將N個(gè)盤(pán)從A桿移動(dòng)到C桿需要移動(dòng)盤(pán)的次數(shù)是2的N次幕減1 ， 那么64個(gè)盤(pán)移動(dòng)次數(shù)就是 18446744073709511615,近19億億次。這是一個(gè)天文數(shù)字，即使一臺(tái)功能很強(qiáng)的現(xiàn)代計(jì)算機(jī)來(lái)解 漢諾塔問(wèn)題，恐怕也需要很長(zhǎng)的時(shí)間，因

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

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

41、歸無(wú)法再進(jìn)行下去，這就是遞歸結(jié)束的邊界條件。由此可見(jiàn)，遞歸算法中常常 隱含了分治思想。程序如下：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 遞歸前進(jìn)段Write(bl);s:=pos(bl,a);if s-10 then find(copy(a,1,s-1),copy(b,1,s-1); 遞歸左子樹(shù)if l-s0 then find(copy(a,s+1,l-s),co

42、py(b,s,l-s); 遞歸右子樹(shù) end;end;beginReadln(z);Readln(h);Find(z,h);Readln;end.遞歸的應(yīng)用經(jīng)典遞歸例如hanoi塔問(wèn)題：經(jīng)典的遞歸，原問(wèn)題包含子問(wèn)題。有些問(wèn)題或者數(shù)據(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ī)劃動(dòng)態(tài)規(guī)劃的子問(wèn)題重疊性質(zhì)與

43、遞歸有某種相似之處。遞歸+動(dòng)態(tài)修改查表是一種不錯(cuò)的建立動(dòng)態(tài) 規(guī)劃模型的方法。其他其他么，就是不好歸類(lèi)。例如表達(dá)式處理，排列組合等。附帶說(shuō)一下，用遞歸來(lái)處理打印方案 的問(wèn)題還是很方便的。求把一個(gè)整數(shù)n無(wú)序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。分析這是一道動(dòng)態(tài)規(guī)劃題，動(dòng)態(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)來(lái)實(shí)現(xiàn)遞推，也可以考慮用遞歸求解。主過(guò)程如下：方案一：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;可以看出，方案一的程序較為冗長(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í)都要為局部變量、返回地址分配棧

46、空間，這就降低了運(yùn)行效率，也 限制了遞歸的深度。因此，在必要的時(shí)候可以只使用遞歸的思想來(lái)求解，而程序則轉(zhuǎn)用非遞歸的方 式書(shū)寫(xiě)。遞歸習(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)只有在第i-1環(huán)已裝上，且第i-2，第i-3.第1環(huán)都拆下時(shí)可以裝拆. 編程序描述拆下N個(gè)環(huán)的過(guò)程.打印0一N(0=N=9)的所有路徑：1- 3 5 - 7 - 90 2- 4 6 - 8剔除多余括號(hào)鍵盤(pán)輸入一個(gè)含有括號(hào)的四則運(yùn)算表達(dá)式，可能含有多余的括號(hào)，編程整理該表達(dá)式，去掉所 有多余的括號(hào)，原表達(dá)式中所有變量和運(yùn)算符相對(duì)位置保持

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

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

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

50、可以利用搜索與回溯的技術(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皇

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

52、個(gè)一維數(shù)組來(lái)表示。數(shù)組 的每一個(gè)元素代表棋盤(pán)的一列，該元素的值是皇后在該列上的行位置。設(shè)數(shù)組名為col,對(duì)于圖有 col3=4。它表示第3列的第4行有一個(gè)皇后。為找到一個(gè)解，必須從空布局開(kāi)始，每放置一個(gè)皇后要檢查布局是否合理。在合理的情況下，試 探找下一個(gè)皇后的位置；如果布局不合理，就改變布局。重復(fù)檢查、試探或檢查、改變位置，直到 找到最后一個(gè)皇后的合理位置，這時(shí)就找到一個(gè)合理的布局。重復(fù)以上過(guò)程直到無(wú)法再改變皇后位 置為止，就可找到所有合理的布局。通過(guò)以上討論，得到程序的第一層描述如下：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 搜索到一個(gè)解BEGINprint;打印change改變布局，繼續(xù)找解ENDELSEextend 繼續(xù)試探下一個(gè)皇后位置ELSEchange;check檢查布局是否合理UNTIL m=0皇后位置不能再改變END.子過(guò)程change改變布局就是試探當(dāng)前皇后m的下一個(gè)位置，即試著放在下一列上 (colm:=colm+1)。如果colm=n，說(shuō)明當(dāng)前皇后m無(wú)位置可放，必

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

55、colkcolm是否成立。左高右低對(duì)角線(xiàn)。共有(2n-1)條這樣的對(duì)角線(xiàn)。同一條對(duì)角線(xiàn)上的不同位置它們的行號(hào)值與列號(hào)值之 差相等。所謂檢查m列上的皇后配置是否與前面的皇后在同一條左高右低對(duì)角線(xiàn)上，就是檢查對(duì)所 有k(k=1,2,.,m 1)不等式成立：(colk-k)(colm-m)。左低右高對(duì)角線(xiàn)。類(lèi)似3,檢查m列上的皇后配置是否與前面的皇后在同一條左低右高對(duì)角線(xiàn)上，就 是檢查對(duì)所有的k(k=1,2,.,m-1)不等式成立：(colk+k)(colm+m)?！驹闯绦颉?n皇后問(wè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ù)與二叉樹(shù)有了前面的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，這一講開(kāi)始，我們談點(diǎn)較深入的數(shù)據(jù)結(jié)構(gòu)知識(shí)。本講，我們先來(lái)談 談樹(shù)，建立樹(shù)的基本概念與基本的處理方式。樹(shù)是

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

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