2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞歸與回溯法.doc

《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞歸與回溯法.doc》由會員分享，可在線閱讀，更多相關《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞歸與回溯法.doc（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。

2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 遞歸與回溯法 課題：遞歸與回溯 目標： 知識目標：遞歸概念與利用遞歸進行回溯 能力目標：回溯算法的應用 重點：回溯算法 難點：回溯算法的理解 板書示意： 1） 遞歸的理解 2） 利用遞歸回溯解決實際問題（例14、例15、例16、例17、例18） 3） 利用回溯算法解決排列問題（例19） 授課過程： 什么是遞歸？先看大家都熟悉的一個民間故事：從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事里說，從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事里說……。象這樣，一個對象部分地由它自己組成，或者是按它自己定義，我們稱之是遞歸。 例如，我們可以這樣定義N!，N!=N*(N-1)!，因此求N!轉(zhuǎn)化為求 (N-1)!。這就是一個遞歸的描述。 因此，可以編寫如下遞歸程序： 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í)行過程。由上述程序可以看出，遞歸是一個反復執(zhí)行直到遞歸終止的過程。 設一個未知函數(shù)f，用其自身構成的已知函數(shù)g來定義： 為了定義f(n)，必須先定義f(n-1)，為了定義f(n-1)，又必須先定義f(n-2) ，…，上述這種用自身的簡單情況來定義自己的方式稱為遞歸定義。 遞歸有如下特點： ①它直接或間接的調(diào)用了自己。 ②一定要有遞歸終止的條件，這個條件通常稱為邊界條件。 與遞推一樣，每一個遞推都有其邊界條件。但不同的是，遞推是由邊界條件出發(fā)，通過遞推式求f(n)的值，從邊界到求解的全過程十分清楚；而遞歸則是從函數(shù)自身出發(fā)來達到邊界條件，在通過邊界條件的遞歸調(diào)用過程中，系統(tǒng)用堆棧把每次調(diào)用的中間結(jié)果（局部變量和返回地址）保存起來，直至求出遞歸邊界值f(0)=a。然后返回調(diào)用函數(shù)。返回的過程中，中間結(jié)果相繼出?；謴停琭(1)=g(1,a)f(2)=g(2,f(1))……直至求出f(n)=g(n,f(n-1))。 遞歸按其調(diào)用方式分 直接遞歸——遞歸過程P直接自己調(diào)用自己； 間接遞歸——即P包含另一過程D，而D又調(diào)用P； 由此可見，遞歸算法的效率往往很低，費時和費內(nèi)存空間。但是遞歸也有其長處，它能使一個蘊含遞歸關系且結(jié)構復雜的程序簡潔精煉，增加可讀性。特別是在難于找到從邊界到解的全過程的情況下，如果把問題進一步，其結(jié)果仍維持原問題的關系，則采用遞歸算法編程比較合適。 遞歸算法適用的一般場合為： ① 數(shù)據(jù)的定義形式按遞歸定義。 如裴波那契數(shù)列的定義： 對應的遞歸程序為 function 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; 這類遞歸問題可轉(zhuǎn)化為遞推算法，遞歸邊界為遞推的邊界條件。例如上例轉(zhuǎn)化為遞推算法即為 function fib(n: Integer): Integer; begin f[0] := 1; f[1] := 2; {遞推邊界} for I := 2 to n do f[I] := f[I – 1] + f[I – 2]; fib := f(n); end; ② 數(shù)據(jù)之間的關系（即數(shù)據(jù)結(jié)構）按遞歸定義。如樹的遍歷，圖的搜索等。 ③ 問題解法按遞歸算法實現(xiàn)。例如回溯法等。 對于②和③，可以用堆棧結(jié)構將其轉(zhuǎn)換為非遞歸算法，以提高算法的效率以及減少內(nèi)存空間的浪費。 下面以經(jīng)典的N皇后問題為例，看看遞歸法是怎樣實現(xiàn)的，以及比較遞歸算法和非遞歸算法效率上的差別。 例15：N皇后問題 圖14 八皇后的兩組解 在N*N的棋盤上放置N個皇后而彼此不受攻擊（即在棋盤的任一行，任一列和任一對角線上不能放置2個皇后），編程求解所有的擺放方法。 分析： 由于皇后的擺放位置不能通過某種公式來確定，因此對于每個皇后的擺放位置都要進行試探和糾正，這就是“回溯”的思想。在N個皇后未放置完成前，擺放第I個皇后和第I+1個皇后的試探方法是相同的，因此完全可以采用遞歸的方法來處理。 下面是放置第I個皇后的的遞歸算法： 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個皇后； 對放置皇后的位置進行標記； Try（I+1） 對放置皇后的位置釋放標記； End; End; N皇后問題的遞歸算法的程序如下： program N_Queens; const MaxN = 100; {最多皇后數(shù)} var A:array [1..MaxN] of Boolean; {豎線被控制標記} B:array [2..MaxN * 2] of Boolean; {左上到右下斜線被控制標記} C:array [1–MaxN..MaxN–1] of Boolean;{左下到右上斜線被控制標記} X: array [1 .. MaxN] of Integer; {記錄皇后的解} Total: Longint; {解的總數(shù)} N: Integer; {皇后個數(shù)} procedure Out; {輸出方案} var I: Integer; begin Inc(Total); Write(Total: 3, ‘:’); for I := 1 to N do Write(X[I]: 3); Writeln; end; procedure Try(I: Integer); {搜索第I個皇后的可行位置} var J: Integer; begin if I = N + 1 then Out; {N個皇后都放置完畢，則輸出解} for J := 1 to N do if A[J] and B[J + I] and C[J – I] then begin X[I] := J; A[J] := False; B[J + I] := False; C[J – I] := False; Try(I + 1); {搜索下一皇后的位置} A[J] := True; B[J + I] := True; C[J – I] := True; end; end; begin 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皇后問題的非遞歸算法的程序： program N_Queens; const MaxN = 100; {最多皇后數(shù)} var A:array [1..MaxN] of Boolean; {豎線被控制標記} B:array [2..MaxN * 2] of Boolean; {左上到右下斜線被控制標記} C:array [1–MaxN..MaxN–1] of Boolean;{左下到右上斜線被控制標記} X: array [1 .. MaxN] of Integer; {記錄皇后的解} Total: Longint; {解的總數(shù)} N: Integer; {皇后個數(shù) procedure Out; {輸出方案} var I: Integer; begin Inc(Total); Write(Total: 3, ‘:’); for I := 1 to N do Write(X[I]: 3); Writeln; end; procedure Main; var K: Integer; begin X[1] := 0; K := 1; while K > 0 do begin if X[K] <> 0 then begin A[X[K]] := True; B[X[K] + K] := True; C[X[K] – K] := True; end; Inc(X[K]); while(X[K]<=N)and not(A[X[K]]and B[X[K]+K]and C[X[K]–K])do Inc(X[K]); {尋找一個可以放置的位置} if X[K] <= N then if K = N then Out else begin A[X[K]] := False; B[X[K] + K] := False; C[X[K] – K] := False; Inc(K); X[K] := 0; {繼續(xù)放置下一個皇后} end 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. 使用遞歸可以使蘊含復雜關系的問題，結(jié)構變得簡潔精煉。看看下面的例題。 例16:新漢諾（hanoi）塔問題 設有n各大小不等的中空圓盤，按從小到大的順序從1到n編號。將這n個圓盤任意的迭套在三根立柱上，立柱的編號分別為A、B、C，這個狀態(tài)稱之為初始狀態(tài)。問題要求找到一種步數(shù)最少的移動方案，使得從初始狀態(tài)轉(zhuǎn)變?yōu)槟繕藸顟B(tài)。移動時有如下要求： ① 一次只移動一個盤； ② 不允許把大盤移到小盤上邊； 輸入：輸入文件第1行是狀態(tài)中圓盤總數(shù)；第2~4行是分別是初始狀態(tài)中A、B、C柱上的圓盤個數(shù)和從上到下每個圓盤的編號；第5~7行是分別是目標狀態(tài)A、B、C柱上的圓盤個數(shù)和從上到下每個圓盤的編號。 輸出：每行寫一步的移動方案，格式為： Move I圓盤 form P柱 to Q柱。 最后輸出最少步數(shù)。 輸入樣例（如圖）： 6 3 1 2 3 2 4 5 1 6 0 6 1 2 3 4 5 6 0 樣例所描述的狀態(tài)如圖15所示。 圖15 樣例圖 = 輸出樣例： 分析： 要從初始狀態(tài)移動到目標狀態(tài)，就是把每個圓盤分別移動到自己的目標狀態(tài)。而問題的關鍵一步就是：首先考慮把編號最大的圓盤移動到自己的目標狀態(tài)，而不是最小的，因為編號最大的圓盤移到目標位置之后就可以不再移動了，而在編號最大的圓盤未移到目標位置之前，編號小的圓盤可能還要移動，編號最大的圓盤一旦固定，對以后的移動將不會造成影響。 根據(jù)上面的分析可設計如下過程 Move(K, W); 表示把編號K的圓盤從當前所在柱移動到W柱的過程。 下面對樣例進行分析。 圖16 樣例移動過程 將6號盤移動到B柱，在此之前一定將經(jīng)歷如圖16所示的狀態(tài) 要移動6號盤首先要把1~5號盤全部移開，也就是說，既不能移動到6號盤的初始立柱上，也不能移動到6號盤的目標立柱上。顯然這里要將它們移動到A柱。然后再將6號盤移到位。此時狀態(tài)如圖17所示。 圖17 樣例移動過程 同時我們注意到：把1~5盤移動到目標的過程和將6號盤移動到B柱的過程，從形式上是一樣的，只是盤的編號不同而已。顯然這是個遞歸過程，可以采用遞歸法實現(xiàn)。 算法設計如下: procedure Move(K, W)； {編號K的圓盤從當前所在柱移動到W柱} begin if K號盤已經(jīng)在W立柱上 then Exit； {遞歸邊界} for I := K - 1 downto 1 do Move(I, 過渡立柱); {將編號小于K的盤都移到過渡立柱上去} 輸出當前移動方案; 將K號盤移到W立柱上; Inc(Step); {累計步數(shù)} end; 程序設計如下： program New_Hanoi; const Inp = ‘hanoi.in’; Outp = ‘hanoi.out’; MaxN = 64; {最大圓盤數(shù)} Stake: array [1 .. 3] of Char =(‘A’, ‘B’, ‘C’); type Tnode = array [1 .. MaxN] of Byte; {記錄圓盤所處的立柱編號} var N: Integer; {圓盤數(shù)} Now, {當前狀態(tài)} Goal: Tnode; {目標狀態(tài)} Step: Longint; {步數(shù)} procedure Init; {讀入數(shù)據(jù)} var I, J, L, X: Integer; begin Assign(Input, Inp); Reset(Input); Readln(N); {讀入圓盤數(shù)} for I := 1 to 3 do begin {讀入初始狀態(tài)} Read(L); for J := 1 to L do begin Read(X); Now[X] := I; end; Readln; end; for I := 1 to 3 do begin {讀入目標狀態(tài)} Read(L); for J := 1 to L do begin Read(X); Goal[X] := I; end; Readln; end; Close(Input); end; procedure Main; var I: Integer; procedure Move(K: Integer; W: Byte); var I, J: Word; begin if Now[K] = W then Exit; {若達到目標，則退出} J := 6 – Now[K] – W; {計算過渡立柱編號} for I := K – 1 downto 1 do {將圓盤移動到過渡立柱} Move(I, J); Write(‘Move‘,K,‘ From ‘,Stake[Now[K]],‘ to ‘,Stake[W]); Writeln(‘.’); Now[K] := W; {將K號盤移動到目標位置} Inc(Step); {累計步數(shù)} end; begin Assign(Output, Outp); Rewrite(Output); for I := N downto 1 do {從大到小對每一個圓盤進行處理} Move(I, Goal[I]); Writeln(Step); {輸出總步數(shù)} Close(Output); end; Begin Init; Main; End. 例17背包問題： 已知一個容量大小為M重量的背包和N種物品，每種物品的重量為Wi。若將物品放入背包將得到Pi的效益，求怎樣選取物品將得到效益最大 分析：本題可以用遞歸求解：設當前有N個物品，容量為M；因為這些物品要么選，要么不選，我們假設選的第一個物品編號為I（1~I-1號物品不選），問題又可以轉(zhuǎn)化為有N-I個物品（即第I+1~N號物品），容量為M-Wi的子問題……如此反復下去，然后在所有可行解中選一個效益最大的便可。 另外，為了優(yōu)化程序，我們定義一個函數(shù)如下： F[I]表示選第I~N個物品能得到的總效益。不難推出： F[N]=Pn F[I]=F[I+1]+Pi （I=1…N-1） 假設當前已選到第I號物品，如果當前搜索的效益值+F[I+1]的值仍然比當前的最優(yōu)值小，則沒有必要繼續(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; Ans,Now :Integer; {Ans記錄最優(yōu)解，Now記錄當前效益值} 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(W[I],P[I]); Close(Input); {讀入數(shù)據(jù)} F[N+1]:=0; For I:=N Downto 1 Do F[I]:=F[I+1]+P[I]; {計算函數(shù)F的值} Ans:=0; Now:=0; End; Procedure Search(I:Integer; J:Byte); {遞歸求解} Var K :Byte; Begin If Now+F[J]<=Ans Then Exit; {如果沒有必要搜索下去，則返回到上一級} If Now>Ans Then Begin {修改最優(yōu)解} Ans:=Now; Out:=Ou; End; For K:=J To N Do {選取物品} If W[K]<=I Then Begin Now:=Now+P[K]; Ou[K]:=True; Search(I-W[K],K+1); Now:=Now-P[K]; Ou[K]:=False; End; End; Begin Init; Search(M,1); Assign(Output,Output.txt); {輸出} Rewrite(Output); Writeln(Ans); For U:=1 To N Do If Out[U] Then Write(U, ); Writeln; Close(Output); End. 例18尋找國都名 給出一個矩陣及一些國都名： o k d u b l i n dublin a l p g o c e v tokyo r a s m u s m b london o s l o n d o n rome y i b l g l r c bonn 圖18 k r z u r i c h paris o a i b x m u z oslo t p q g l a m v lima 要求從這個矩陣中找出這些國都名，并輸出它們的起始位置及方向。 輸入：在文本文件input.txt中的第一行有一個整數(shù)M和N，表示該字符矩陣的長和寬。接下來就是M*N的字符矩陣。字符矩陣后有一個整數(shù)K，表示國家都名的個數(shù)，接下來的K行，每一行都是一個國都名。 輸出：在文本文件output.txt中共有K行，第I行寫入第I個國都名的起始位置及方向。起始位置用坐標表示，方向定義見圖18。如沒有找到國都名，輸出‘No found’。 分析：將字符矩陣讀入到二維數(shù)組，然后對每一個國都名進行搜索，首先需要在矩陣中找到國都名的第一個字符，然后沿八個方向進行搜索。直到找到國都名為止。若在矩陣中沒有找到，則輸出相應的信息。 在搜索過程時，類似八皇后問題，建立一個標志數(shù)組，標識已經(jīng)搜索過的方向，在對八個方向搜索時，可以建立一個方向數(shù)組，使得程序更加簡潔明了。 參考程序如下： program exam18; Const Fx : Array[1..8,1..2] Of Shortint {定義八個方向} =((0,1),(0,-1),(1,0),(-1,0),(1,-1),(-1,1),(1,1),(-1,-1)); max = 100; {最大字符矩陣} Finp = Input.Txt; {輸入文件名} Fout = Output.Txt; {輸出文件名} Var A :Array[0..max+1,0..max+1] of Char; {為了節(jié)約邊界條件的判斷，故增加邊界范圍} B :Array[1..max,1..max] Of Boolean; {標志數(shù)組，標志已經(jīng)搜索過的路徑} S, W :String; N,M,I,J,K :Integer; printed :Boolean; Procedure Init; Var I,J :Integer; Begin Assign(Input,Finp); Reset(Input); {采用重定向的手段，將輸入文件與標準輸入聯(lián)系起來， 這樣對標準輸入（鍵盤）的操作，相當對輸入文件的操作} Assign(Output,Fout);Rewrite(Output); {采用重定向的手段，將輸出文件與標準輸出聯(lián)系起來， 這樣對標準輸出（屏幕）的操作，相當對輸出文件的操作} Readln(M,N); For I:=1 To M Do Begin For J:=1 To N Do Read(A[I,J]); Readln; End; End; Procedure Out; Begin write((,J,,,k,)); {輸出起始位置的坐標} Writeln(:5,W); {輸出路徑} printed:=True {置已經(jīng)打印的標志} End; Procedure Work(T,X,Y:Integer); {搜索路徑，T為國都名的字符位置，X，Y為當前搜索的坐標} Var I : Integer; Begin If T=Length(S)+1 Then begin {搜索完，打印輸出} Out; exit end; For I:=1 To 8 Do {八個方向進行搜索} Begin X:=X+Fx[I,1]; Y:=Y+Fx[I,2]; {坐標變化} If (A[X,Y]=S[T])And(B[X,Y]) Then Begin W:=W+Chr(I+48); {記錄路徑} B[X,Y]:=False; {設置已經(jīng)搜索} Work(T+1,X,Y); {繼續(xù)搜索下一個} Delete(W,Length(W),1);{恢復原路徑} B[X,Y]:=True; {恢復標志} End; X:=X-Fx[I,1]; Y:=Y-Fx[I,2]; {返回后，坐標恢復} End; End; Begin Init; Readln(N); For I:=1 To N Do {對所有的國都名進行處理} Begin Readln(S); {讀入第I個國都名} printed:=False; Fillchar(B,Sizeof(B),True);{未搜索之前清標志數(shù)組} For J:=1 To N Do begin {對字符矩陣進行搜索} For K:=1 To N Do Begin If printed Then Break; {已經(jīng)打印了，跳出內(nèi)循環(huán)} If A[J,K]=S[1] Then Work(2,J,K);{從第一個字符開始搜} End; If printed Then Break; {已經(jīng)打印了，跳出外循環(huán)} end; If Not printed Then Writeln(No found); End; Close(Input); Close(Output); End. 例19采用遞歸方法，求N個元素中取出M個的排列，。 （1）每個元素只能取一次。 （2）每個元素可以取任意多次（即可重復的排列）。 分析：此題用簡單的遞歸搜索。設x[I]排列中的第I個元素，依次搜索每一個x[I]即可 program exam19; const finp =input.txt; fout =output.txt; maxn =10; var n,m :integer; x :array[1..maxn]of integer; { x數(shù)組記錄當前排列} used:array[1..maxn]of boolean; {used[I]=True時表明第I個元素在當前排列中，反之亦然} procedure init; {初始化輸入} var i :integer; begin write(‘input n, m:’); readln(n,m); fillchar(used,sizeof(used),false) end; procedure pailie(i:integer); {搜索} var j :integer; begin if i>m then begin for j:=1 to m do write(x[j]:5);writeln; {輸出一組解} end else for j:=1 to n do if not used[j] then begin used[j]:=true; {修改used[I]} x[i]:=j; {記錄x[i]} pailie(i+1); {繼續(xù)搜索排列的下一個} used[j]:=false {還原used[I]} end end; Begin init; pailie(1); End. （2）只需要將pailie過程中used標志數(shù)組 去掉即可，這樣，已經(jīng)取過的數(shù)據(jù)可以繼續(xù)取。 修改如下： procedure pailie(i:integer); {搜索x[I]} var j :integer; begin if i>m then begin for j:=1 to m do write(x[j]:5);writeln;{找到一組解，輸出} end else for j:=1 to n do begin {枚舉x[I]} x[i]:=j; {記錄x[I]} pailie(i+1) {繼續(xù)搜索x[I+1]} end end;