高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 遞歸與回溯法

1、遞歸與回溯法課題：遞歸與回溯目標(biāo)：知識(shí)目標(biāo)：遞歸概念與利用遞歸進(jìn)行回溯能力目標(biāo)：回溯算法的應(yīng)用重點(diǎn)：回溯算法難點(diǎn)：回溯算法的理解板書(shū)示意：1） 遞歸的理解2） 利用遞歸回溯解決實(shí)際問(wèn)題（例14、例15、例16、例17、例18）3） 利用回溯算法解決排列問(wèn)題（例19）授課過(guò)程：什么是遞歸？先看大家都熟悉的一個(gè)民間故事：從前有座山，山上有座廟，廟里有一個(gè)老和尚在給小和尚講故事，故事里說(shuō)，從前有座山，山上有座廟，廟里有一個(gè)老和尚在給小和尚講故事，故事里說(shuō)。象這樣，一個(gè)對(duì)象部分地由它自己組成，或者是按它自己定義，我們稱之是遞歸。例如，我們可以這樣定義N!，N!=N*(N-1)!，因此求N!轉(zhuǎn)化為求 (

2、N-1)!。這就是一個(gè)遞歸的描述。因此，可以編寫(xiě)如下遞歸程序：program Factorial; var N: Integer; T: Longint; function Fac(N: Integer): Longint; begin if N = 0 then Fac := 1 else Fac := N * Fac(N - 1) end; begin Write('N = '); Readln(N); T := Fac(N); Writeln('N! = ',T); end.圖13 遞歸調(diào)用示例圖圖13展示了N=3的執(zhí)行過(guò)程。由上述程序可以看出，遞歸是一個(gè)

3、反復(fù)執(zhí)行直到遞歸終止的過(guò)程。設(shè)一個(gè)未知函數(shù)f，用其自身構(gòu)成的已知函數(shù)g來(lái)定義：為了定義f(n)，必須先定義f(n-1)，為了定義f(n-1)，又必須先定義f(n-2) ，上述這種用自身的簡(jiǎn)單情況來(lái)定義自己的方式稱為遞歸定義。遞歸有如下特點(diǎn)：它直接或間接的調(diào)用了自己。一定要有遞歸終止的條件，這個(gè)條件通常稱為邊界條件。與遞推一樣，每一個(gè)遞推都有其邊界條件。但不同的是，遞推是由邊界條件出發(fā)，通過(guò)遞推式求f(n)的值，從邊界到求解的全過(guò)程十分清楚；而遞歸則是從函數(shù)自身出發(fā)來(lái)達(dá)到邊界條件，在通過(guò)邊界條件的遞歸調(diào)用過(guò)程中，系統(tǒng)用堆棧把每次調(diào)用的中間結(jié)果（局部變量和返回地址）保存起來(lái)，直至求出遞歸邊界值f(

4、0)=a。然后返回調(diào)用函數(shù)。返回的過(guò)程中，中間結(jié)果相繼出棧恢復(fù)，f(1)=g(1,a)àf(2)=g(2,f(1)àà直至求出f(n)=g(n,f(n-1)。遞歸按其調(diào)用方式分直接遞歸遞歸過(guò)程P直接自己調(diào)用自己；間接遞歸即P包含另一過(guò)程D，而D又調(diào)用P；由此可見(jiàn)，遞歸算法的效率往往很低，費(fèi)時(shí)和費(fèi)內(nèi)存空間。但是遞歸也有其長(zhǎng)處，它能使一個(gè)蘊(yùn)含遞歸關(guān)系且結(jié)構(gòu)復(fù)雜的程序簡(jiǎn)潔精煉，增加可讀性。特別是在難于找到從邊界到解的全過(guò)程的情況下，如果把問(wèn)題進(jìn)一步，其結(jié)果仍維持原問(wèn)題的關(guān)系，則采用遞歸算法編程比較合適。遞歸算法適用的一般場(chǎng)合為： 數(shù)據(jù)的定義形式按遞歸定義。如裴波那契數(shù)列

5、的定義： 對(duì)應(yīng)的遞歸程序?yàn)閒unction fib(n: Integer): Integer; begin if n = 0 then fib := 1 遞歸邊界 else if n = 1 then fib := 2遞歸邊界 else fib := fib(n 2) + fib(n 1);遞歸 end;這類(lèi)遞歸問(wèn)題可轉(zhuǎn)化為遞推算法，遞歸邊界為遞推的邊界條件。例如上例轉(zhuǎn)化為遞推算法即為function fib(n: Integer): Integer; begin f0 := 1; f1 := 2;遞推邊界 for I := 2 to n do fI := fI 1 + fI 2; fib :

6、= f(n); end; 數(shù)據(jù)之間的關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）按遞歸定義。如樹(shù)的遍歷，圖的搜索等。 問(wèn)題解法按遞歸算法實(shí)現(xiàn)。例如回溯法等。對(duì)于和，可以用堆棧結(jié)構(gòu)將其轉(zhuǎn)換為非遞歸算法，以提高算法的效率以及減少內(nèi)存空間的浪費(fèi)。下面以經(jīng)典的N皇后問(wèn)題為例，看看遞歸法是怎樣實(shí)現(xiàn)的，以及比較遞歸算法和非遞歸算法效率上的差別。例15：N皇后問(wèn)題圖14 八皇后的兩組解在N*N的棋盤(pán)上放置N個(gè)皇后而彼此不受攻擊（即在棋盤(pán)的任一行，任一列和任一對(duì)角線上不能放置2個(gè)皇后），編程求解所有的擺放方法。分析：由于皇后的擺放位置不能通過(guò)某種公式來(lái)確定，因此對(duì)于每個(gè)皇后的擺放位置都要進(jìn)行試探和糾正，這就是“回溯”的思想。在N個(gè)皇后

7、未放置完成前，擺放第I個(gè)皇后和第I+1個(gè)皇后的試探方法是相同的，因此完全可以采用遞歸的方法來(lái)處理。下面是放置第I個(gè)皇后的的遞歸算法：Procedure Try(I:integer)；搜索第I行皇后的位置var j:integer;begin if I=n+1 then 輸出方案； for j:=1 to n do if 皇后能放在第I行第J列的位置 then begin 放置第I個(gè)皇后； 對(duì)放置皇后的位置進(jìn)行標(biāo)記； Try（I+1） 對(duì)放置皇后的位置釋放標(biāo)記；End;End;N皇后問(wèn)題的遞歸算法的程序如下：program N_Queens; const MaxN = 100;最多皇后數(shù) var

8、 A:array 1.MaxN of Boolean; 豎線被控制標(biāo)記 B:array 2.MaxN * 2 of Boolean; 左上到右下斜線被控制標(biāo)記 C:array 1MaxN.MaxN1 of Boolean;左下到右上斜線被控制標(biāo)記 X: array 1 . MaxN of Integer; 記錄皇后的解 Total: Longint;解的總數(shù) N: Integer;皇后個(gè)數(shù) procedure Out;輸出方案 var I: Integer; begin Inc(Total); Write(Total: 3, :); for I := 1 to N do Write(XI: 3

9、); Writeln; end; procedure Try(I: Integer);搜索第I個(gè)皇后的可行位置 var J: Integer; begin if I = N + 1 then Out; N個(gè)皇后都放置完畢，則輸出解 for J := 1 to N do if AJ and BJ + I and CJ I then begin XI := J; AJ := False; BJ + I := False; CJ I := False; Try(I + 1);搜索下一皇后的位置 AJ := True; BJ + I := True; CJ I := True; end; end; b

10、egin Write(Queens Numbers = ); Readln(N); FillChar(A, Sizeof(A), True); FillChar(B, Sizeof(B), True); FillChar(C, Sizeof(C), True); Try(1); Writeln(Total = , Total); end.N皇后問(wèn)題的非遞歸算法的程序：program N_Queens;const MaxN = 100; 最多皇后數(shù) var A:array 1.MaxN of Boolean; 豎線被控制標(biāo)記 B:array 2.MaxN * 2 of Boolean; 左上到右

11、下斜線被控制標(biāo)記 C:array 1MaxN.MaxN1 of Boolean;左下到右上斜線被控制標(biāo)記 X: array 1 . MaxN of Integer; 記錄皇后的解 Total: Longint;解的總數(shù) N: Integer;皇后個(gè)數(shù)procedure Out;輸出方案 var I: Integer; begin Inc(Total); Write(Total: 3, :); for I := 1 to N do Write(XI: 3); Writeln; end;procedure Main;var K: Integer;begin X1 := 0; K := 1; whi

12、le K > 0 do begin if XK <> 0 then begin AXK := True; BXK + K := True; CXK K := True; end; Inc(XK);while(XK<=N)and not(AXKand BXK+Kand CXKK)do Inc(XK);尋找一個(gè)可以放置的位置 if XK <= N then if K = N then Out else begin AXK := False; BXK + K := False; CXK K := False; Inc(K); XK := 0;繼續(xù)放置下一個(gè)皇后 end

13、else Dec(K);回溯 end;end; begin Write(Queens Number = ); Readln(N); FillChar(A, Sizeof(A), True); FillChar(B, Sizeof(B), True); FillChar(C, SizeofI, True); Main; Writeln(Total = , Total); end.使用遞歸可以使蘊(yùn)含復(fù)雜關(guān)系的問(wèn)題，結(jié)構(gòu)變得簡(jiǎn)潔精煉?？纯聪旅娴睦}。例16:新漢諾（hanoi）塔問(wèn)題設(shè)有n各大小不等的中空?qǐng)A盤(pán)，按從小到大的順序從1到n編號(hào)。將這n個(gè)圓盤(pán)任意的迭套在三根立柱上，立柱的編號(hào)分別為A、B、

14、C，這個(gè)狀態(tài)稱之為初始狀態(tài)。問(wèn)題要求找到一種步數(shù)最少的移動(dòng)方案，使得從初始狀態(tài)轉(zhuǎn)變?yōu)槟繕?biāo)狀態(tài)。移動(dòng)時(shí)有如下要求： 一次只移動(dòng)一個(gè)盤(pán)； 不允許把大盤(pán)移到小盤(pán)上邊；輸入：輸入文件第1行是狀態(tài)中圓盤(pán)總數(shù)；第24行是分別是初始狀態(tài)中A、B、C柱上的圓盤(pán)個(gè)數(shù)和從上到下每個(gè)圓盤(pán)的編號(hào)；第57行是分別是目標(biāo)狀態(tài)A、B、C柱上的圓盤(pán)個(gè)數(shù)和從上到下每個(gè)圓盤(pán)的編號(hào)。輸出：每行寫(xiě)一步的移動(dòng)方案，格式為：Move I圓盤(pán) form P柱 to Q柱。最后輸出最少步數(shù)。輸入樣例（如圖）：63 1 2 32 4 51 606 1 2 3 4 5 6 0樣例所描述的狀態(tài)如圖15所示。圖15 樣例圖=輸出樣例：分析：要從初始

15、狀態(tài)移動(dòng)到目標(biāo)狀態(tài)，就是把每個(gè)圓盤(pán)分別移動(dòng)到自己的目標(biāo)狀態(tài)。而問(wèn)題的關(guān)鍵一步就是：首先考慮把編號(hào)最大的圓盤(pán)移動(dòng)到自己的目標(biāo)狀態(tài)，而不是最小的，因?yàn)榫幪?hào)最大的圓盤(pán)移到目標(biāo)位置之后就可以不再移動(dòng)了，而在編號(hào)最大的圓盤(pán)未移到目標(biāo)位置之前，編號(hào)小的圓盤(pán)可能還要移動(dòng)，編號(hào)最大的圓盤(pán)一旦固定，對(duì)以后的移動(dòng)將不會(huì)造成影響。根據(jù)上面的分析可設(shè)計(jì)如下過(guò)程 Move(K, W);表示把編號(hào)K的圓盤(pán)從當(dāng)前所在柱移動(dòng)到W柱的過(guò)程。下面對(duì)樣例進(jìn)行分析。圖16 樣例移動(dòng)過(guò)程將6號(hào)盤(pán)移動(dòng)到B柱，在此之前一定將經(jīng)歷如圖16所示的狀態(tài)要移動(dòng)6號(hào)盤(pán)首先要把15號(hào)盤(pán)全部移開(kāi)，也就是說(shuō)，既不能移動(dòng)到6號(hào)盤(pán)的初始立柱上，也不能移動(dòng)到6

16、號(hào)盤(pán)的目標(biāo)立柱上。顯然這里要將它們移動(dòng)到A柱。然后再將6號(hào)盤(pán)移到位。此時(shí)狀態(tài)如圖17所示。圖17 樣例移動(dòng)過(guò)程同時(shí)我們注意到：把15盤(pán)移動(dòng)到目標(biāo)的過(guò)程和將6號(hào)盤(pán)移動(dòng)到B柱的過(guò)程，從形式上是一樣的，只是盤(pán)的編號(hào)不同而已。顯然這是個(gè)遞歸過(guò)程，可以采用遞歸法實(shí)現(xiàn)。算法設(shè)計(jì)如下:procedure Move(K, W)；編號(hào)K的圓盤(pán)從當(dāng)前所在柱移動(dòng)到W柱 begin if K號(hào)盤(pán)已經(jīng)在W立柱上 then Exit；遞歸邊界 for I := K - 1 downto 1 do Move(I, 過(guò)渡立柱);將編號(hào)小于K的盤(pán)都移到過(guò)渡立柱上去 輸出當(dāng)前移動(dòng)方案; 將K號(hào)盤(pán)移到W立柱上; Inc(Step)

17、;累計(jì)步數(shù) end;程序設(shè)計(jì)如下： program New_Hanoi; const Inp = hanoi.in; Outp = hanoi.out; MaxN = 64; 最大圓盤(pán)數(shù) Stake: array 1 . 3 of Char =(A, B, C); type Tnode = array 1 . MaxN of Byte; 記錄圓盤(pán)所處的立柱編號(hào) var N: Integer;圓盤(pán)數(shù) Now,當(dāng)前狀態(tài) Goal: Tnode;目標(biāo)狀態(tài) Step: Longint;步數(shù) procedure Init;讀入數(shù)據(jù) var I, J, L, X: Integer; begin Assig

18、n(Input, Inp); Reset(Input); Readln(N);讀入圓盤(pán)數(shù) for I := 1 to 3 do begin 讀入初始狀態(tài) Read(L); for J := 1 to L do begin Read(X); NowX := I; end; Readln; end; for I := 1 to 3 do begin 讀入目標(biāo)狀態(tài) Read(L); for J := 1 to L do begin Read(X); GoalX := I; end; Readln; end; Close(Input); end; procedure Main; varI: Integ

19、er; procedure Move(K: Integer; W: Byte); var I, J: Word; begin if NowK = W then Exit; 若達(dá)到目標(biāo)，則退出 J := 6 NowK W;計(jì)算過(guò)渡立柱編號(hào) for I := K 1 downto 1 do將圓盤(pán)移動(dòng)到過(guò)渡立柱 Move(I, J); Write(Move,K, From ,StakeNowK, to ,StakeW);Writeln(.); NowK := W;將K號(hào)盤(pán)移動(dòng)到目標(biāo)位置 Inc(Step);累計(jì)步數(shù) end; begin Assign(Output, Outp); Rewrite(O

20、utput); for I := N downto 1 do從大到小對(duì)每一個(gè)圓盤(pán)進(jìn)行處理 Move(I, GoalI); Writeln(Step);輸出總步數(shù) Close(Output); end; Begin Init; Main; End.例17背包問(wèn)題：已知一個(gè)容量大小為M重量的背包和N種物品，每種物品的重量為Wi。若將物品放入背包將得到Pi的效益，求怎樣選取物品將得到效益最大分析：本題可以用遞歸求解：設(shè)當(dāng)前有N個(gè)物品，容量為M；因?yàn)檫@些物品要么選，要么不選，我們假設(shè)選的第一個(gè)物品編號(hào)為I（1I-1號(hào)物品不選），問(wèn)題又可以轉(zhuǎn)化為有N-I個(gè)物品（即第I+1N號(hào)物品），容量為M-Wi的子問(wèn)

21、題如此反復(fù)下去，然后在所有可行解中選一個(gè)效益最大的便可。另外，為了優(yōu)化程序，我們定義一個(gè)函數(shù)如下：FI表示選第IN個(gè)物品能得到的總效益。不難推出：FN=PnFI=FI+1+Pi（I=1N-1）假設(shè)當(dāng)前已選到第I號(hào)物品，如果當(dāng)前搜索的效益值+FI+1的值仍然比當(dāng)前的最優(yōu)值小，則沒(méi)有必要繼續(xù)搜索下去。參考程序：Program exam17;Var W,P :Array 1.50 Of Integer; F :Array 1.50 Of Integer;Ou,Out :Array 1.50 Of Boolean; Ou，Out數(shù)組記錄選擇物品的具體方案 M :Integer; N,U :Byte;

22、Ans,Now :Integer; Ans記錄最優(yōu)解，Now記錄當(dāng)前效益值Procedure Init; 初始化Var I :Byte;Begin Fillchar(Out,Sizeof(Out),False); Ou:=Out; Assign(Input,'Input.txt'); Reset(Input); Readln(M,N); For I:=1 To N Do Readln(WI,PI); Close(Input);讀入數(shù)據(jù) FN+1:=0; For I:=N Downto 1 Do FI:=FI+1+PI;計(jì)算函數(shù)F的值 Ans:=0; Now:=0;End;Pro

23、cedure Search(I:Integer; J:Byte);遞歸求解Var K :Byte;Begin If Now+FJ<=Ans Then Exit; 如果沒(méi)有必要搜索下去，則返回到上一級(jí) If Now>Ans Then Begin 修改最優(yōu)解 Ans:=Now; Out:=Ou; End; For K:=J To N Do 選取物品 If WK<=I Then Begin Now:=Now+PK; OuK:=True; Search(I-WK,K+1); Now:=Now-PK; OuK:=False; End;End;Begin Init; Search(M,1

24、); Assign(Output,'Output.txt');輸出 Rewrite(Output); Writeln(Ans); For U:=1 To N Do If OutU Then Write(U,' '); Writeln; Close(Output);End.例18尋找國(guó)都名給出一個(gè)矩陣及一些國(guó)都名：o k d u b l i n dublina l p g o c e v tokyor a s m u s m b londono s l o n d o n romey i b l g l r c bonn圖18k r z u r i c h par

25、iso a i b x m u z oslot p q g l a m v lima要求從這個(gè)矩陣中找出這些國(guó)都名，并輸出它們的起始位置及方向。輸入：在文本文件input.txt中的第一行有一個(gè)整數(shù)M和N，表示該字符矩陣的長(zhǎng)和寬。接下來(lái)就是M*N的字符矩陣。字符矩陣后有一個(gè)整數(shù)K，表示國(guó)家都名的個(gè)數(shù)，接下來(lái)的K行，每一行都是一個(gè)國(guó)都名。輸出：在文本文件output.txt中共有K行，第I行寫(xiě)入第I個(gè)國(guó)都名的起始位置及方向。起始位置用坐標(biāo)表示，方向定義見(jiàn)圖18。如沒(méi)有找到國(guó)都名，輸出No found。分析：將字符矩陣讀入到二維數(shù)組，然后對(duì)每一個(gè)國(guó)都名進(jìn)行搜索，首先需要在矩陣中找到國(guó)都名的第一個(gè)字

26、符，然后沿八個(gè)方向進(jìn)行搜索。直到找到國(guó)都名為止。若在矩陣中沒(méi)有找到，則輸出相應(yīng)的信息。在搜索過(guò)程時(shí)，類(lèi)似八皇后問(wèn)題，建立一個(gè)標(biāo)志數(shù)組，標(biāo)識(shí)已經(jīng)搜索過(guò)的方向，在對(duì)八個(gè)方向搜索時(shí)，可以建立一個(gè)方向數(shù)組，使得程序更加簡(jiǎn)潔明了。參考程序如下：program exam18;Const Fx : Array1.8,1.2 Of Shortint 定義八個(gè)方向 =(0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1); max = 100; 最大字符矩陣 Finp = 'Input.Txt' 輸入文件名 Fout = 'Output

27、.Txt' 輸出文件名VarA :Array0.max+1,0.max+1 of Char;為了節(jié)約邊界條件的判斷，故增加邊界范圍 B :Array1.max,1.max Of Boolean; 標(biāo)志數(shù)組，標(biāo)志已經(jīng)搜索過(guò)的路徑 S, W :String; N,M,I,J,K :Integer; printed :Boolean;Procedure Init;Var I,J :Integer; Begin Assign(Input,Finp); Reset(Input); 采用重定向的手段，將輸入文件與標(biāo)準(zhǔn)輸入聯(lián)系起來(lái)，這樣對(duì)標(biāo)準(zhǔn)輸入（鍵盤(pán)）的操作，相當(dāng)對(duì)輸入文件的操作 Assign(O

28、utput,Fout);Rewrite(Output);采用重定向的手段，將輸出文件與標(biāo)準(zhǔn)輸出聯(lián)系起來(lái)， 這樣對(duì)標(biāo)準(zhǔn)輸出（屏幕）的操作，相當(dāng)對(duì)輸出文件的操作 Readln(M,N); For I:=1 To M Do Begin For J:=1 To N Do Read(AI,J); Readln; End;End;Procedure Out;Begin write('(',J,',',k,')'); 輸出起始位置的坐標(biāo) Writeln('':5,W); 輸出路徑 printed:=True 置已經(jīng)打印的標(biāo)志End;Proced

29、ure Work(T,X,Y:Integer);搜索路徑，T為國(guó)都名的字符位置，X，Y為當(dāng)前搜索的坐標(biāo)Var I : Integer;Begin If T=Length(S)+1 Then begin 搜索完，打印輸出 Out; exit end; For I:=1 To 8 Do 八個(gè)方向進(jìn)行搜索 Begin X:=X+FxI,1; Y:=Y+FxI,2; 坐標(biāo)變化 If (AX,Y=ST)And(BX,Y) Then Begin W:=W+Chr(I+48); 記錄路徑 BX,Y:=False; 設(shè)置已經(jīng)搜索 Work(T+1,X,Y); 繼續(xù)搜索下一個(gè) Delete(W,Length(W

30、),1);恢復(fù)原路徑 BX,Y:=True; 恢復(fù)標(biāo)志 End; X:=X-FxI,1; Y:=Y-FxI,2; 返回后，坐標(biāo)恢復(fù) End;End;Begin Init; Readln(N); For I:=1 To N Do 對(duì)所有的國(guó)都名進(jìn)行處理 Begin Readln(S); 讀入第I個(gè)國(guó)都名 printed:=False; Fillchar(B,Sizeof(B),True);未搜索之前清標(biāo)志數(shù)組 For J:=1 To N Do begin 對(duì)字符矩陣進(jìn)行搜索 For K:=1 To N Do Begin If printed Then Break; 已經(jīng)打印了，跳出內(nèi)循環(huán) If AJ,K=S1 Then Work(2,J,K);從第一個(gè)字符開(kāi)始搜 End; If printed Then Break; 已經(jīng)打印了，跳出外循環(huán) end; If Not