遞歸回溯搜索教學(xué)教材

1、遞歸回溯搜索遞歸的概念v由函數(shù)或者過程調(diào)用引起。v一個對象部分地由它自己組成，或者是按它自己定義，我們稱之是遞歸。 v例3：漢諾塔問題：有n個半徑各不相同的圓盤，按半徑從大到小，自下而上依次套在A柱上，另外還有B、C兩根空柱。要求將A柱上的n個圓盤全部搬到C柱上去，每次只能搬動一個盤子，且必須始終保持每根柱子上是小盤在上，大盤在下。輸出總共移動的次數(shù)。ABCv分析：在移動盤子的過程當(dāng)中發(fā)現(xiàn)要搬動n個盤子，必須先將n-1個盤子從A柱搬到B柱去，再將A柱上的最后一個盤子搬到C柱，最后從B柱上將n-1個盤子搬到C柱去。搬動n個盤子和搬動n-1個盤子時的方法是一樣的，當(dāng)盤子搬到只剩一個時，遞歸結(jié)束。v

2、program hannuota;vvarvn:integer;vprocedure hnt(a,b,c,n:integer);vbeginv if n=1 then writeln(a,-,c)v else begin hnt(a,c,b,n-1);writeln(a,-,c);hnt(b,a,c,n-1);end;vend;vbeginvwrite(please input n:);vread(n);vhnt(1,2,3,n);vend.漢諾塔問題的遞推解法v設(shè)設(shè)f(n)為為n 個盤子從個盤子從1柱移到柱移到3柱所需移動的最少盤次。柱所需移動的最少盤次。當(dāng)當(dāng)n=1時，時，f(1)=1。v當(dāng)

3、當(dāng)n=2時，時，f(2)=3。v以此類推，當(dāng)以此類推，當(dāng)1柱上有柱上有n(n2)個盤子時，我們可以利用下列個盤子時，我們可以利用下列步驟：步驟：v第一步：先借助第一步：先借助3柱把柱把1柱上面的柱上面的n-1個盤子移動到個盤子移動到2柱上，柱上，所需的移動次數(shù)為所需的移動次數(shù)為f(n-1)。v第二步：然后再把第二步：然后再把1柱最下面的一個盤子移動到柱最下面的一個盤子移動到3柱上，只柱上，只需要需要1次盤子。次盤子。v第三步：再借助第三步：再借助1柱把柱把2柱上的柱上的n-1個盤子移動到個盤子移動到3上，所需上，所需的移動次數(shù)為的移動次數(shù)為f(n-1)。v由以上由以上3步得出總共移動盤子的次數(shù)

4、為：步得出總共移動盤子的次數(shù)為：f(n-1)+1+ f(n-1)。v 所以：所以：f(n)=2 f(n-1)+1 現(xiàn)在就可以用遞推現(xiàn)在就可以用遞推做了做了vf(1)=1vf(2)=3vf(3)=7vf(4)=15f(n)= 2n-1現(xiàn)在可以用數(shù)學(xué)方法做了現(xiàn)在可以用數(shù)學(xué)方法做了練習(xí)1：簡單背包問題。v有一個背包容量為s，現(xiàn)有n件物品，重量分別為s1、s2、s3。Si（1=i=n）,假設(shè)si均為正數(shù)，從這n件物品中選擇若干件物品放入背包，使得放入總重量恰好為s，請輸出一種解，若無解輸出“NO ANSWER”。練習(xí)2v快速排序vvar a:array1.10000 of longint;vn,i:l

5、ongint;vprocedure qsort(s,t:longint);vvar i,j,x:longint;vbeginvi:=s;j:=t;x:=ai;vwhile (ij) do beginv while (ij) and (x=aj) do dec(j);v ai:=aj;v while (ij) and (ai=x) do inc(i);v aj:=ai;v end;vai:=x;vif si-1 then qsort(s,i-1);vif j+1n then 輸出結(jié)果velse for j:=下界 to 上界 dovbeginvxi:=hj;vif 可行滿足限界函數(shù)和約束條件 t

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

7、nteger;vbeginv if I=n+1 then 輸出方案；v for j:=1 to n do v if 皇后能放在第I行第J列的位置 then beginv 放置第I個皇后；v 對放置皇后的位置進行標(biāo)記；v Try（I+1） v 對放置皇后的位置釋放標(biāo)記；vEnd;vEnd;vN皇后問題的遞歸算法的程序如下：vprogram N_Queens;v constv MaxN = 100;最多皇后數(shù)v varv A:array 1.MaxN of Boolean; 同列-豎線被控制標(biāo)記v B:array 2.MaxN * 2 of Boolean;i+j和相等-左下到右上斜線被控制標(biāo)記v

8、 C:array 1MaxN.MaxN1 of Boolean;j-i差相等-左上到右下斜線被控制標(biāo)記v X: array 1 . MaxN of Integer; 記錄皇后的解v Total: Longint;解的總數(shù)v N: Integer;皇后個數(shù)v procedure Out;輸出方案v varv I: Integer;v beginv Inc(Total); Write(Total: 3, :);v for I := 1 to N do Write(XI: 3);v Writeln;v end;vprocedure Try(I: Integer);v搜索第I個皇后的可行位置v var

9、v J: Integer;v beginv if I = N + 1 then Out; N個皇后都放置完畢，則輸出解v for J := 1 to N dov if AJ and BJ + I and CJ I then beginv XI := J;v AJ := False;v BJ + I := False;v CJ I := False;v Try(I + 1);搜索下一皇后的位置v AJ := True;v BJ + I := True;v CJ I := True;v end;v end;vbeginv Write(Queens Numbers = );v Readln(N);v

10、 FillChar(A, Sizeof(A), True);v FillChar(B, Sizeof(B), True);v FillChar(C, Sizeof(C), True);v Try(1);v Writeln(Total = , Total);v end.v上機練習(xí)題v1.添加自然數(shù)問題。（add.pas） v要求找出具有下列性質(zhì)的數(shù)的個數(shù)(包含輸入的自然數(shù)n)：v先輸入一個自然數(shù)n(n=500),然后對此自然數(shù)按照如下方法進行處理:v. 不作任何處理;v. 在它的左邊加上一個自然數(shù),但該自然數(shù)不能超過原數(shù)的一半;v. 加上數(shù)后,繼續(xù)按此規(guī)則進行處理,直到不能再加自然數(shù)為止.v 輸

11、入文件：add.in,一行，n的值。v輸出文件：add.out，一行，按照規(guī)則可產(chǎn)生的自然數(shù)個數(shù)。v樣例：v輸入文件：v6v滿足條件的數(shù)為 6 v 16v 26v 126v 36v 136v輸出文件v6 vvar n,i:integer;v s:real;vprocedure qiu(x:integer);vvar k:integer;vbeginv if x0 thenv beginv s:=s+1;v for k:=1 to x div 2 do qiu(k)v endvend;vbeginv readln(n);v s:=0;v qiu(n);v writeln(s)vend.v2. 跳

12、馬問題。（jump.pas）v在5*5格的棋盤上，有一個國際象棋的馬，它可以朝8個方向跳，但不允許出界或跳到已跳過的格子上，要求求出跳遍整個棋盤后的不同的路徑條數(shù)。v輸出文件：jump.out，一行，路徑條數(shù)。 vprogram jump;v varv h:array-1.7,-1.7 of integer;v a,b:array1.8 of integer;v i,j,num:integer;v procedure print;v var i,j:integer;v beginv num:=num+1;v if num=5 thenv beginv for i:=1 to 5 dov beg

13、inv for j:=1 to 5 do write(hi,j:4);v writeln;v end;v writeln;v end; v end;v vprocedure try(x,y,i:integer);v var j,u,v:integer;v beginv for j:=1 to 8 dov beginv u:=x+aj;v v:=y+bj;v if hu,v=0 thenv begin hu,v:=i;v if i=1)and(i=1)and(j(2,1)-(3,1)-(2,2)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1)分析分析: a:a

14、rray1.maxn,1.maxnof 0.1; 記錄迷宮坐標(biāo)記錄迷宮坐標(biāo) c:array1.maxn,1.maxnof 0.1; 訪問標(biāo)志訪問標(biāo)志:0:沒走沒走;1:已走已走 b:array0.maxn*maxn of integer;記錄路徑方向記錄路徑方向 dx,dy:array1.8of integer; 方向位移方向位移 8個方向的位移個方向的位移: dx1:=0; dy1:=-1; dx2:=1; dy2:=-1; dx3:=1; dy3:=0; dx4:=1; dy4:=1; dx5:=0; dy5:=1; dx6:=-1; dy6:=1; dx7:=-1; dy7:=0; dx

15、8:=-1; dy8:=-1;讀入數(shù)據(jù)讀入數(shù)據(jù): 坐標(biāo)坐標(biāo)procedure readdata;begin assign(input,a.in); reset(input); readln(n); for i:=1 to n do for j:=1 to n do begin read(aj,i);i:縱坐標(biāo);j:橫坐標(biāo) cj,i:=0; end; close(input);遞歸算法遞歸算法:procedure try(i:integer);搜索第搜索第i步應(yīng)到達的位置步應(yīng)到達的位置 var k:integer; begin for k:=1 to 8 do begin if (x+dxk=1

16、)and(x+dxk=1)and(y+dyk,(,x,y,); end; writeln; end;主程序主程序:begin readdata; x:=1; y:=1; try(1);end.1.由鍵盤輸入正整數(shù)N，生成1到N 的全排列。（1= N =9）例如：輸入2時，輸出：1 11 22 12 2 應(yīng)用之一： 排列組合問題v2.由鍵盤輸入正整數(shù)N，生成1到N 的不重復(fù)全排列。（1= N =9）例如：輸入2時，輸出：1 22 1v3.輸出從N個元素中選取M個元素的各種排列（1N、M9）。v例如：N=3v M=2v輸出：v1 2v1 3v2 1v2 3v3 1v3 2 v4.輸出從N個元素中選

17、取M個元素的各種組合 （1N、M9）。v例如：N=3v M=2v輸出：v1 2v1 3v2 3v5.已知兩個自然數(shù)n和k（n,k=100），從1，2，n中任取k個數(shù)，要求所取的k個數(shù)中，任意兩個數(shù)不能相差1。編程求有多少種取法。v如：n=6 ，k=3,，從1，2，3，4，5，6中取3個數(shù)，任意兩個數(shù)不能相差1，取法如下：v（1 3 5） （1 3 6） （1 4 6） （2 4 6）v共有4種取法。v提示：（1 3 5）和（3 1 5）屬于一種取法。v輸入（輸入（b.in）：）：一行，n和k，中間用空格隔開。v輸出（輸出（b.out）：）：一行，取法的種數(shù)。v樣例：v輸入：6 3v輸出：4過河

18、卒v 棋盤上A點有一個過河卒，需要走到目標(biāo)B點。卒行走的規(guī)則：可以向下、或者向右。同時在棋盤上C點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。因此稱之為“馬攔過河卒”。v棋盤用坐標(biāo)表示，A點(0, 0)、B點(n, m)(n, m為不超過20的整數(shù))，同樣馬的位置坐標(biāo)是需要給出的?，F(xiàn)在要求你計算出卒從A點能夠到達B點的路徑的條數(shù)，假設(shè)馬的位置是固定不動的，并不是卒走一步馬走一步。v【輸入】【輸入】v 一行四個數(shù)據(jù)，分別表示B點坐標(biāo)和馬的坐標(biāo)。 v【輸出】【輸出】v 一個數(shù)據(jù)，表示所有的路徑條數(shù)。v【樣例輸入】【樣例輸入】v6 6 3 2v【樣例輸出【樣例輸出1】v17v題目分析：v本題是一道典型的深度優(yōu)先搜索題目。v需要處理好的細節(jié)有：v1.讀入“馬”的坐標(biāo)，控制好八個方向。v2.在（n,m）棋盤上控制好“馬”所能跳出的邊界。v3.按向下、向右兩個方向搜索，只要當(dāng)前沒有走到（n,m）點且下一節(jié)點為訪問過，則搜索。vprogram zu;vconstv dx:array1.8 of shortint=(2,1,-1,-2