遞歸回溯搜索課件



《遞歸回溯搜索課件》由會員分享,可在線閱讀,更多相關《遞歸回溯搜索課件(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.
- 溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
5. 裝配圖網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。