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

1、信息技術(shù)競(jìng)賽培訓(xùn)教程目錄第二部分 數(shù)據(jù)結(jié)構(gòu)（一）棧（二）隊(duì)列（三）鏈表（四）迭代與遞推（五）遞歸（六）搜索與回溯（七）樹與二叉樹（八）排序算法（九）查找算法（十）圖論基礎(chǔ)知識(shí)l l 廣度優(yōu)先搜索l l 廣度優(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ò)誤就是“?！背?，那么，“棧”為何物呢？棧是只能在某一端插入和刪除的特殊線性表。用桶堆積物品，先堆進(jìn)來(lái)的壓在底下，隨后一件一件往堆。取走時(shí)，只能從上面一件一件取。堆和取都在頂部進(jìn)行，底部一般是

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

3、出下溢信息，作出錯(cuò)處理(退棧前先檢查是否已為空棧， 空則下溢；不空則作)；X=S(SOP)，（退棧后的元素賦給X）；TOP=TOP-1，結(jié)束（棧指針減，指向棧頂）。進(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 THEN writeln(overflow) ELSE BEGINtop:=top+1;stop:=x;END;END;PROCEDURE POP(VAR s:stack;VAR y,top

4、:integer);出棧BEGINIF top=0 THEN writeln(underflow) ELSE BEGIN y:=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)dN mod d （其中 div 為整除運(yùn)算，mod為求余運(yùn)算）。例如：(1348)10(25

5、04)8運(yùn)算過(guò)程如下：NN div 8N mod 8134816841682102125202NN div 8N mod 894131、 1、 填空：(9413)10=( )8=( )16=( )22、下面的程序?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;begin writeln; write(Please enter a number(N) base 10:); readln(n); write(please

6、enter a number(d):); readln(d); i:=1; repeat ai:=n mod d; n:=n div d; inc(i); until n=0; for j:=i-1 downto 1 do write(aj:5);end.出站進(jìn)站2、火車站列車調(diào)度示意圖如下，假設(shè)調(diào)度站兩側(cè)的軌道為單向行駛軌道。1、 1、 如果進(jìn)站的車廂序列為123，則可能的出戰(zhàn)車廂序列是什么？2、 2、 如果進(jìn)展進(jìn)站的車廂序列為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:4823; (式 11.1)其正確的計(jì)算結(jié)果應(yīng)該是，但若在編譯程序中簡(jiǎn)單地按自左向右掃描的原則進(jìn)行計(jì)算，則為：X122324321這結(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)算符：優(yōu)先數(shù)：（語(yǔ)句結(jié)束符“；”的優(yōu)先數(shù)為零）在運(yùn)算過(guò)程中，優(yōu)先數(shù)高的運(yùn)算符應(yīng)先進(jìn)行運(yùn)算（但遇到括號(hào)時(shí)，應(yīng)另作處理）。按這樣的規(guī)定，對(duì)式

8、（11.1）自左向右進(jìn)行運(yùn)算時(shí)，其計(jì)算順序就被唯一地確定下來(lái)了。計(jì)算順序確定后，在對(duì)表達(dá)式進(jìn)行編譯時(shí)，一般設(shè)立兩個(gè)棧，一個(gè)稱為運(yùn)算符棧（OPS），另一個(gè)稱為操作數(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)算符與棧頂元素的優(yōu)先數(shù)。例如式（11.1）中，當(dāng)掃描到“”和“”時(shí)都要將運(yùn)

9、算符入棧。接著掃描到“”號(hào)， 其優(yōu)先數(shù)小于乘號(hào)所以乘號(hào)退棧，并執(zhí)行，將結(jié)果再存入操作數(shù)棧。再將“”號(hào)的優(yōu)先數(shù)與運(yùn)算符棧的棧頂元素“”號(hào)的優(yōu)先數(shù)相比較，兩者相等，所以再將加號(hào)退棧，進(jìn)行，結(jié)果為，再入棧，接著，由于運(yùn)算棧已空，所以減號(hào)入棧。當(dāng)掃描到“”時(shí)，操作數(shù)入棧。當(dāng)掃描到“；”時(shí)，其優(yōu)先數(shù)最低， 所以減號(hào)退棧并執(zhí)行，結(jié)果為并入棧。因已掃描到語(yǔ)句結(jié)束符，所以表達(dá)式的求值結(jié)束，結(jié)果為。例題模擬計(jì)算機(jī)處理算術(shù)表達(dá)式過(guò)程。從鍵盤上輸入算術(shù)表達(dá)式串（只含、運(yùn)算符，充許含括號(hào)），輸出算術(shù)表達(dá)式的值。設(shè)輸入的表達(dá)式串是合法的。分析:建立兩個(gè)棧，一個(gè)是操作數(shù)棧（number），一個(gè)是運(yùn)算符棧（symbol），

10、根據(jù)運(yùn)算符的優(yōu)先級(jí)對(duì)兩個(gè)棧進(jìn)行相應(yīng)的操作。源程序program ex11_4;const max = 100;var number: array0.max of integer; symbol: array1.max of char; s, t: string; i, p, j, code: integer;procedure push; 算符入棧運(yùn)算begin inc(p); symbolp := si;end;procedure pop; 運(yùn)算符棧頂元素出棧,并取出操作數(shù)棧元素完成相應(yīng)的運(yùn)算begin dec(p); case symbolp + 1 of +: inc(numberp,

11、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ù)begin can := true; if (si in +, -) and (symbolp () then exit; if (si in *, /) and (symbolp in *, /) then exit; can := false;end;begi

12、n write(String : ); readln(s); s := ( + s + ); i := 1; p := 0; while i = length(s) do begin while si = ( do 左括號(hào)處理 begin push; inc(i); end; j := i; repeat 取數(shù)入操作數(shù)棧 inc(i); until (si 9); t := copy(s, j, i - j); val(t, numberp, code); repeat if si = ) then 右括號(hào)處理 begin while symbolp ( do pop; dec(p); num

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

14、字符 錯(cuò)誤類型 error 3如 輸入： It is 12!輸出： error 1 2 3輸入： i am ,a student輸出： 42、 2、 編碼解碼：從鍵盤輸入一個(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è)摫碇羔?if ata.zhi btb.zhi then begin if ata.xi 0 then write(#8 #8); write(ata.xi, x, ata.zhi, +); dec(ta); e

15、nd else if ata.zhi begin if btb.xi 0 then write(#8 #8); write(btb.xi, x, btb.zhi, +); dec(tb); endelse begin 若兩表指針指向的項(xiàng)指數(shù)相等,則兩系數(shù)相加輸出, 兩表指針同時(shí)改變 if btb.xi + ata.xi 0 then begin if btb.xi + ata.xi 0 do 若有一表空,則輸出另一表的剩余項(xiàng) begin if ata.xi 0 do begin if btb.xi 0 then write(#8 #8); write(btb.xi, x, btb.zhi, +

16、); dec(tb); end;writeln(#8 #8);readln;end.源程序二：多項(xiàng)式相加的鏈表實(shí)現(xiàn)program ex11_5b;type link = node; node = record zhi, xi: integer; nxt: link; end;var a, b: link; n: integer;procedure createfifo(var c: link); 建立多項(xiàng)式系數(shù)、指數(shù)鏈表var p: link; i: integer;begin new(p); readln(p.xi, p.zhi); c := p; for i := 1 to n - 1 d

17、o begin new(p.nxt); p := p.nxt; readln(p.xi, p.zhi); end; p.nxt := nil;end;begin write(One : ); readln(n); createfifo(a); write(Two : ); readln(n); createfifo(b); write(Result is ); while (a nil) and (b nil) do begin if a.zhi b.zhi then begin if a.xi 0 then write(#8 #8); write(a.xi, x, a.zhi, +); a

18、:= a.nxt; end else if a.zhi begin if b.xi 0 then write(#8 #8); write(b.xi, x, b.zhi, +); b := b.nxt; endelse begin if b.xi + a.xi 0 then begin if b.xi + a.xi 0 then write(#8 #8); write(b.xi + a.xi, x, b.zhi, +); end; b := b.nxt; a := a.nxt; end;end;while a nil do begin if a.xi 0 then write(#8 #8); w

19、rite(a.xi, x, a.zhi, +); a := a.nxt; end;while b nil do begin if b.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

20、 pici,j=0 then bzi,j:=false;end;end;close(int);for 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ū)間，把根的近似值逐步精確到要以滿足具體實(shí)際問(wèn)題的需要為止，該算法稱為迭代

21、。迭代的一般原則可以用一個(gè)數(shù)學(xué)模型來(lái)描述，現(xiàn)要求出方程F(x)=0的解：先設(shè)F(x)=G(x)-x，則方程F(x)=0可化為x=G(x)， 這就產(chǎn)生了一個(gè)迭代算法的數(shù)學(xué)模型：n+1=（n）從某一個(gè)數(shù)0出發(fā)，按此迭代模型，求出一個(gè)序列：0，1，2，3，n-2，n-1，n當(dāng)nn-1小于一個(gè)特定值（誤差許可值）時(shí)，n-1n，這時(shí)可認(rèn)定x=G(x)。也就是說(shuō)，求出的n已經(jīng)可以作為原方程f(x)=0根的近似值了。 設(shè)誤差許可值為A，則迭代算法的NS圖如圖1。 圖1 迭代算法NS框圖迭代算法的關(guān)鍵在于確定迭代函數(shù)G(x)。確定G(x)時(shí)需保證產(chǎn)生的迭代序列n 是否能使兩個(gè)相鄰的數(shù)之間的差距越來(lái)越?。磧蓴?shù)

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為初始近似值0，誤差值設(shè)定為0.0000001， 則程序可寫成：program ex11_7;const a=0.0000001;var x0,x1,X:real;beginx0:=0;x1:=1/(x0+2);while abs(x1

23、-x0)a dobeginx0:=x1;x1:=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ù)的根的近似值設(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ù)都可以滿足根的近似值要求了。為方便起見，取下該區(qū)間的邊界置作為近似值。這就是迭代算法的一般原則的體現(xiàn)了。二、.

24、遞推對(duì)于一個(gè)的序列來(lái)說(shuō)，如果已知它的通項(xiàng)公式（即表達(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)為止，這樣的方法稱為遞推算法。遞推算法的首要問(wèn)題是得到相鄰的數(shù)據(jù)項(xiàng)間的關(guān)系（即遞推關(guān)系）。遞推算法避開了求通項(xiàng)公項(xiàng)的麻煩，把一個(gè)復(fù)雜的問(wèn)題的求解，分解成了連續(xù)的若干步簡(jiǎn)單運(yùn)算。一般說(shuō)來(lái)，可以將遞推算法看成是一種特殊的迭代算法。例2 著名的菲波納葜(F

25、ibonacci)數(shù)列，其第一項(xiàng)為0，第二項(xiàng)為1， 從第三項(xiàng)開始，其每一項(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)公式）是非常困難的。而根椐該數(shù)列的形成規(guī)則，其有一個(gè)的公式即nn-1n-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)

26、，并進(jìn)行移位，即J取K值、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ì)的一般原則，即遞推公式取得。例3 數(shù)字三角形。如下所示為一個(gè)數(shù)字三角形。請(qǐng)編一個(gè)程序計(jì)算從頂?shù)降椎哪程幍囊粭l路徑，使該路徑所經(jīng)過(guò)的數(shù)字

27、總和最大。只要求輸出總和。1、 一步可沿左斜線向下或右斜線向下走； 2、 角形行數(shù)小于等于100； 3、 三角形中的數(shù)字為0，1，99； 測(cè)試數(shù)據(jù)通過(guò)鍵盤逐行輸入，如上例數(shù)據(jù)應(yīng)以如下所示格式輸入：573 88 1 02 7 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ù)字總和的最大值。源程序如下：p

28、rogram 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)，我們就

29、來(lái)談一談遞歸算法。遞歸算法作為計(jì)算機(jī)程序設(shè)計(jì)中的一種重要的算法，是較難理解的算法之一。簡(jiǎn)單地說(shuō)，遞歸就是編寫這樣的一個(gè)特殊的過(guò)程，該過(guò)程體中有一個(gè)語(yǔ)句用于調(diào)用過(guò)程自身（稱為遞歸調(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ù)，直到回到起始位置上，才最終

30、結(jié)束整個(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!。分析：根椐數(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)知道菲波納葜

32、數(shù)列的各數(shù)列的產(chǎn)生可用下列公式表示： 12 nn-1n-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-1else 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í)行流程的二叉樹行式，大家可參照?qǐng)D2 來(lái)理解這個(gè)執(zhí)行過(guò)程。為方便起見，設(shè)定N=5，圖中的數(shù)碼表示遞歸執(zhí)行的順序。 圖2 F函數(shù)的