第三講遞歸與回溯法

1、第三講 遞歸與回溯法一、遞歸的概念什么是遞歸？先看大家都熟悉的一個民間故事：從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事里說，從前有座山，山上有座廟，廟里有一個老和尚在給小和尚講故事，故事里說。象這樣，一個對象部分地由它自己組成，或者是按它自己定義，我們稱之是遞歸。例如，我們可以這樣定義N!，N!=N*(N-1)!，因此求N!轉(zhuǎn)化為求 (N-1)!。這就是一個遞歸的描述。因此，可以編寫如下遞歸程序：program Factorial; var N: Integer; T: Longint; function Fac(N: Integer): Longint; begin if

2、 N = 0 then Fac := 1 else Fac := N * Fac(N - 1) end; begin Write(N = ); Readln(N); T := Fac(N); Writeln(N! = ,T); end.圖3-1 遞歸調(diào)用示例圖圖3-1展示了N=3的執(zhí)行過程。由上述程序可以看出，遞歸是一個反復(fù)執(zhí)行直到遞歸終止的過程。設(shè)一個未知函數(shù)f，用其自身構(gòu)成的已知函數(shù)g來定義：為了定義f(n)，必須先定義f(n-1)，為了定義f(n-1)，又必須先定義f(n-2) ，一個函數(shù)、過程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說明內(nèi)部又直接或間接地出現(xiàn)有其本身的引用，則稱它們是遞歸的或者

3、是遞歸定義的。在程序設(shè)計中，過程或函數(shù)直接或者間接調(diào)用自己，就被稱為遞歸調(diào)用。遞歸過程是借助于一個遞歸工作棧來實(shí)現(xiàn)的，問題向一極推進(jìn)，這一過程叫做遞推；問題逐一解決，最后回到原問題，這一過程叫做回歸。遞歸的過程正是由遞推和回歸兩個過程組成。遞歸有如下特點(diǎn)：它直接或間接的調(diào)用了自己。一定要有遞歸終止的條件，這個條件通常稱為邊界條件。與遞推一樣，每一個遞推都有其邊界條件。但不同的是，遞推是由邊界條件出發(fā)，通過遞推式求f(n)的值，從邊界到求解的全過程十分清楚；而遞歸則是從函數(shù)自身出發(fā)來達(dá)到邊界條件，在通過邊界條件的遞歸調(diào)用過程中，系統(tǒng)用堆棧把每次調(diào)用的中間結(jié)果（局部變量和返回地址）保存起來，直至求

4、出遞歸邊界值f(0)=a。然后返回調(diào)用函數(shù)。返回的過程中，中間結(jié)果相繼出?；謴?fù)，f(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；由此可見，遞歸算法的效率往往很低，費(fèi)時和費(fèi)內(nèi)存空間。但是遞歸也有其長處，它能使一個蘊(yùn)含遞歸關(guān)系且結(jié)構(gòu)復(fù)雜的程序簡潔精煉，增加可讀性。特別是在難于找到從邊界到解的全過程的情況下，如果把問題進(jìn)一步，其結(jié)果仍維持原問題的關(guān)系，則采用遞歸算法編程比較合適。遞歸算法適用的一般場合為： 數(shù)據(jù)的定義形式按遞歸定義。如裴波那契數(shù)列的定義： 對應(yīng)的遞歸

5、程序?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;這類遞歸問題可轉(zhuǎn)化為遞推算法，遞歸邊界為遞推的邊界條件。例如上例轉(zhuǎn)化為遞推算法即為unction fib(n: Integer): Integer; begin f0 := 1; f1 := 2;遞推邊界 for I := 2 to n do fI := fI 1 + fI 2; fib := f(n); end

6、; 數(shù)據(jù)之間的關(guān)系（即數(shù)據(jù)結(jié)構(gòu)）按遞歸定義。如樹的遍歷，圖的搜索等。 問題解法按遞歸算法實(shí)現(xiàn)。例如回溯法等。對于和，可以用堆棧結(jié)構(gòu)將其轉(zhuǎn)換為非遞歸算法，以提高算法的效率以及減少內(nèi)存空間的浪費(fèi)。下面以經(jīng)典的N皇后問題為例，看看遞歸法是怎樣實(shí)現(xiàn)的，以及比較遞歸算法和非遞歸算法效率上的差別。二、應(yīng)用舉例例1、樓梯有N級臺階，上樓可以一步上一階，也可以一步上二階。編一遞歸程序，計算共有多少種不同走法？提示：如N級樓梯有S(N)種不同走法，則有：S(N)=S(N-2)+S(N-1)輸入：N輸出：所有的走法例2、新漢諾（hanoi）塔問題設(shè)有n各大小不等的中空圓盤，按從小到大的順序從1到n編號。將這n個圓

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

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

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

10、輸出當(dāng)前移動方案; 將K號盤移到W立柱上; Inc(Step);累計步數(shù) end;程序設(shè)計如下： 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,當(dāng)前狀態(tài) Goal: Tnode;目標(biāo)狀態(tài) Step: Longint;步數(shù) procedure Init;讀入數(shù)據(jù) var I

11、, 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); 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); e

12、nd; procedure Main; varI: Integer; procedure Move(K: Integer; W: Byte); var I, J: Word; begin if NowK = W then Exit; 若達(dá)到目標(biāo)，則退出 J := 6 NowK W;計算過渡立柱編號 for I := K 1 downto 1 do將圓盤移動到過渡立柱 Move(I, J); Write(Move,K, From ,StakeNowK, to ,StakeW);Writeln(.); NowK := W;將K號盤移動到目標(biāo)位置 Inc(Step);累計步數(shù) end; begin

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

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

15、的具體方案 M :Integer; N,U :Byte; 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;計算函數(shù)F的值 Ans

16、:=0; Now:=0;End;Procedure Search(I:Integer; J:Byte);遞歸求解Var K :Byte;Begin If Now+FJAns Then Begin 修改最優(yōu)解 Ans:=Now; Out:=Ou; End; For K:=J To N Do 選取物品 If WKm then begin for j:=1 to m do write(xj:5);writeln;輸出一組解 end else for j:=1 to n do if not usedj then begin usedj:=true;修改usedI xi:=j;記錄xi pailie(i

17、+1);繼續(xù)搜索排列的下一個 usedj:=false還原usedI end end;Begin init; pailie(1);End.（2）只需要將pailie過程中used標(biāo)志數(shù)組去掉即可，這樣，已經(jīng)取過的數(shù)據(jù)可以繼續(xù)取。修改如下：procedure pailie(i:integer);搜索xI var j :integer;begin if im then begin for j:=1 to m do write(xj:5);writeln;找到一組解，輸出 end else for j:=1 to n do begin枚舉xI xi:=j; 記錄xI pailie(i+1)繼續(xù)搜索x

18、I+1 end end;例6、N皇后問題圖3-6 八皇后的兩組解在N*N的棋盤上放置N個皇后而彼此不受攻擊（即在棋盤的任一行，任一列和任一對角線上不能放置2個皇后），編程求解所有的擺放方法。分析：由于皇后的擺放位置不能通過某種公式來確定，因此對于每個皇后的擺放位置都要進(jìn)行試探和糾正，這就是“回溯”的思想。在N個皇后未放置完成前，擺放第I個皇后和第I+1個皇后的試探方法是相同的，因此完全可以采用遞歸的方法來處理。下面是放置第I個皇后的的遞歸算法：Procedure Try(I:integer)；搜索第I行皇后的位置var j:integer;begin if I=n+1 then 輸出方案； f

19、or j:=1 to n do if 皇后能放在第I行第J列的位置 then begin 放置第I個皇后； 對放置皇后的位置進(jìn)行標(biāo)記； Try（I+1） 對放置皇后的位置釋放標(biāo)記；End;End;N皇后問題的遞歸算法的程序如下：program N_Queens; const MaxN = 100;最多皇后數(shù) var 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

20、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(XI: 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 AJ a

21、nd 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; 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; 豎線被控制標(biāo)記 B:array 2.MaxN * 2 of Boolean; 左上到右下斜線被控制標(biāo)記 C:array 1MaxN.MaxN1 of Boolean;左下到右上斜線被控制標(biāo)記 X: array 1 . Max