遞歸回溯搜索課件

《遞歸回溯搜索課件》由會員分享，可在線閱讀，更多相關《遞歸回溯搜索課件（46頁珍藏版）》請在裝配圖網上搜索。

1、導入練習v例1，N!。N!=N*(N-1)!，因此求N!轉化為求(N-1)!。這就是一個遞歸的描述。010)!1(*!nnnnn例2：裴波那契數列的定義：2120121nffnnfnnn遞歸的概念v由函數或者過程調用引起。v一個對象部分地由它自己組成，或者是按它自己定義，我們稱之是遞歸。v例3：漢諾塔問題：有n個半徑各不相同的圓盤，按半徑從大到小，自下而上依次套在A柱上，另外還有B、C兩根空柱。要求將A柱上的n個圓盤全部搬到C柱上去，每次只能搬動一個盤子，且必須始終保持每根柱子上是小盤在上，大盤在下。輸出總共移動的次數。ABCv分析：在移動盤子的過程當中發現要搬動n個盤子，必須先將n-1個盤子

2、從A柱搬到B柱去，再將A柱上的最后一個盤子搬到C柱，最后從B柱上將n-1個盤子搬到C柱去。搬動n個盤子和搬動n-1個盤子時的方法是一樣的，當盤子搬到只剩一個時，遞歸結束。vprogram 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

3、,n);vend.漢諾塔問題的遞推解法v設設f(n)為為n 個盤子從個盤子從1柱移到柱移到3柱所需移動的最少盤次。柱所需移動的最少盤次。當當n=1時，時，f(1)=1。v當當n=2時，時，f(2)=3。v以此類推，當以此類推，當1柱上有柱上有n(n2)個盤子時，我們可以利用下列個盤子時，我們可以利用下列步驟：步驟：v第一步：先借助第一步：先借助3柱把柱把1柱上面的柱上面的n-1個盤子移動到個盤子移動到2柱上，柱上，所需的移動次數為所需的移動次數為f(n-1)。v第二步：然后再把第二步：然后再把1柱最下面的一個盤子移動到柱最下面的一個盤子移動到3柱上，只柱上，只需要需要1次盤子。次盤子。v第三步

4、：再借助第三步：再借助1柱把柱把2柱上的柱上的n-1個盤子移動到個盤子移動到3上，所需上，所需的移動次數為的移動次數為f(n-1)。v由以上由以上3步得出總共移動盤子的次數為：步得出總共移動盤子的次數為：f(n-1)+1+f(n-1)。v 所以：所以：f(n)=2 f(n-1)+1 現在就可以用遞推現在就可以用遞推做了做了vf(1)=1vf(2)=3vf(3)=7vf(4)=15f(n)=2n-1現在可以用數學方法做了現在可以用數學方法做了練習1：簡單背包問題。v有一個背包容量為s，現有n件物品，重量分別為s1、s2、s3。Si（1=i=n）,假設si均為正數，從這n件物品中選擇若干件物品放入

5、背包，使得放入總重量恰好為s，請輸出一種解，若無解輸出“NO ANSWER”。練習2v快速排序vvar a:array1.10000 of longint;vn,i:longint;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);v

6、if j+1n then 輸出結果velse for j:=下界 to 上界 dovbeginvxi:=hj;vif 可行滿足限界函數和約束條件 then begin 置值；try(i+1);取消置值；end;vend;vend;v例4：N皇后問題在N*N的棋盤上放置N個皇后而彼此不受攻擊（即在棋盤的任一行，任一列和任一對角線上不能放置2個皇后），編程求解所有的擺放方法。八皇后的兩組解v分析：v由于皇后的擺放位置不能通過某種公式來確定，因此對于每個皇后的擺放位置都要進行試探和糾正，這就是“回溯”的思想。在N個皇后未放置完成前，擺放第I個皇后和第I+1個皇后的試探方法是相同的，因此完全可以采用遞

7、歸的方法來處理。v下面是放置第I個皇后的的遞歸算法：vProcedure Try(I:integer)；v搜索第I行皇后的位置vvarv j:integer;vbeginv if I=n+1 then 輸出方案；v for j:=1 to n do v if 皇后能放在第I行第J列的位置 then beginv 放置第I個皇后；v 對放置皇后的位置進行標記；v Try（I+1）v 對放置皇后的位置釋放標記；vEnd;vEnd;vN皇后問題的遞歸算法的程序如下：vprogram N_Queens;v constv MaxN=100;最多皇后數v varv A:array 1.MaxN of Bo

8、olean;同列-豎線被控制標記v B:array 2.MaxN*2 of Boolean;i+j和相等-左下到右上斜線被控制標記v C:array 1MaxN.MaxN1 of Boolean;j-i差相等-左上到右下斜線被控制標記v X:array 1.MaxN of Integer;記錄皇后的解v Total:Longint;解的總數v N:Integer;皇后個數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 Writel

9、n;v end;vprocedure Try(I:Integer);v搜索第I個皇后的可行位置v varv 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 Num

10、bers=);v Readln(N);v 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上機練習題v1.添加自然數問題。（add.pas）v要求找出具有下列性質的數的個數(包含輸入的自然數n)：v先輸入一個自然數n(n=500),然后對此自然數按照如下方法進行處理:v.不作任何處理;v.在它的左邊加上一個自然數,但該自然數不能超過原數的一半;v.加上數后,繼續按此規則進行處理,直到不能再加自然

11、數為止.v 輸入文件：add.in,一行，n的值。v輸出文件：add.out，一行，按照規則可產生的自然數個數。v樣例：v輸入文件：v6v滿足條件的數為 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)ven

12、d.v2.跳馬問題。（jump.pas）v在5*5格的棋盤上，有一個國際象棋的馬，它可以朝8個方向跳，但不允許出界或跳到已跳過的格子上，要求求出跳遍整個棋盤后的不同的路徑條數。v輸出文件：jump.out，一行，路徑條數。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 do

13、v beginv 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)分析分析:

14、a:array1.maxn,1.maxnof 0.1;記錄迷宮坐標記錄迷宮坐標 c:array1.maxn,1.maxnof 0.1;訪問標志訪問標志: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;dx8:=-1;dy8:=-1;讀

15、入數據讀入數據:坐標坐標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:縱坐標;j:橫坐標 cj,i:=0;end;close(input);遞歸算法遞歸算法:procedure try(i:integer);搜索第搜索第i步應到達的位置步應到達的位置 var k:integer;begin for k:=1 to 8 do begin if(x+dxk=1)and(x+dxk=1)and(y+dyk,(

16、,x,y,);end;writeln;end;主程序主程序:begin readdata;x:=1;y:=1;try(1);end.1.由鍵盤輸入正整數N，生成1到N 的全排列。（1=N=9）例如：輸入2時，輸出：1 11 22 12 2 應用之一：排列組合問題v2.由鍵盤輸入正整數N，生成1到N 的不重復全排列。（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個元素中選取M個元素的各種組合（1N、M9）。v例如：N=3v M=2v輸出：v

17、1 2v1 3v2 3v5.已知兩個自然數n和k（n,k=100），從1，2，n中任取k個數，要求所取的k個數中，任意兩個數不能相差1。編程求有多少種取法。v如：n=6，k=3,，從1，2，3，4，5，6中取3個數，任意兩個數不能相差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）：）：一行，取法的種數。v樣例：v輸入：6 3v輸出：4過河卒v 棋盤上A點有一個過河卒，需要走到目標B點。卒行走的規則：可以向下、或者向右

18、。同時在棋盤上C點有一個對方的馬，該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。因此稱之為“馬攔過河卒”。v棋盤用坐標表示，A點(0,0)、B點(n,m)(n,m為不超過20的整數)，同樣馬的位置坐標是需要給出的?，F在要求你計算出卒從A點能夠到達B點的路徑的條數，假設馬的位置是固定不動的，并不是卒走一步馬走一步。v【輸入】【輸入】v 一行四個數據，分別表示B點坐標和馬的坐標。v【輸出】【輸出】v 一個數據，表示所有的路徑條數。v【樣例輸入】【樣例輸入】v6 6 3 2v【樣例輸出【樣例輸出1】v17v題目分析：v本題是一道典型的深度優先搜索題目。v需要處理好的細節有：v1.讀入“馬”的

19、坐標，控制好八個方向。v2.在（n,m）棋盤上控制好“馬”所能跳出的邊界。v3.按向下、向右兩個方向搜索，只要當前沒有走到（n,m）點且下一節點為訪問過，則搜索。vprogram zu;vconstv dx:array1.8 of shortint=(2,1,-1,-2,-2,-1,1,2);v dy:array1.8 of shortint=(1,2,2,1,-1,-2,-2,-1);vvar n,m,x,y:longint;v g:array-2.22,-2.22 of boolean;v i,ans:longint;vprocedure go(a,b:longint);vbeginv i

20、f(a=n)and(b=m)then inc(ans)else beginv if(a+1=n)and ga+1,b=truev then go(a+1,b);v if(b+1=m)and ga,b+1=truev then go(a,b+1);v end;vend;vbeginvassign(input,zu.in);reset(input);vassign(output,zu.out);rewrite(output);vreadln(n,m,x,y);vfillchar(g,sizeof(g),true);vgx,y:=false;vfor i:=1 to 8 dov gx+dxi,y+dyi:=false;vans:=0;vgo(0,0);vwriteln(ans);vclose(input);close(output);vend.