導(dǎo)入練習(xí)例1，N!。N!=N*(N-1)!，因此求N!轉(zhuǎn)化為求(N-1)!。這就是一個(gè)遞歸的描述。例2：裴波那契數(shù)列的定義：遞歸的概念由函數(shù)或者過程調(diào)用引起。一個(gè)對(duì)象部分地由它自己組成，或者是按它自己定義，我們稱之是遞歸。例3：漢諾塔問題：有n個(gè)半徑各不相同的圓盤，按半徑從大到小，自下而上依次套在A柱上，另外還有B、C兩根空柱。要求將A柱上的n個(gè)圓盤全部搬到C柱上去，每次只能搬動(dòng)一個(gè)盤子，且必需始終保持每根柱子上是小盤在上，大盤在下。輸出總共移動(dòng)的次數(shù)。ABC分析：在移動(dòng)盤子的過程當(dāng)中發(fā)覺要搬動(dòng)n個(gè)盤子，必需先將n-1個(gè)盤子從A柱搬到B柱去，再將A柱上的最終一個(gè)盤子搬到C柱，最終從B柱上將n-1個(gè)盤子搬到C柱去。搬動(dòng)n個(gè)盤子和搬動(dòng)n-1個(gè)盤子時(shí)的方法是一樣的，當(dāng)盤子搬到只剩一個(gè)時(shí)，遞歸結(jié)束。programhannuota;varn:integer;procedurehnt(a,b,c,n:integer);beginifn=1thenwriteln(a,'->',c)elsebeginhnt(a,c,b,n-1);writeln(a,'->',c);hnt(b,a,c,n-1);end;end;beginwrite('pleaseinputn:');read(n);hnt(1,2,3,n);end.漢諾塔問題的遞推解法設(shè)f(n)為n個(gè)盤子從1柱移到3柱所需移動(dòng)的最少盤次。

當(dāng)n=1時(shí)，f(1)=1。當(dāng)n=2時(shí)，f(2)=3。以此類推，當(dāng)1柱上有n(n>2)個(gè)盤子時(shí)，我們可以利用下列步驟：第一步：先借助3柱把1柱上面的n-1個(gè)盤子移動(dòng)到2柱上，所需的移動(dòng)次數(shù)為f(n-1)。其次步：然后再把1柱最下面的一個(gè)盤子移動(dòng)到3柱上，只須要1次盤子。第三步：再借助1柱把2柱上的n-1個(gè)盤子移動(dòng)到3上，所需的移動(dòng)次數(shù)為f(n-1)。由以上3步得出總共移動(dòng)盤子的次數(shù)為：f(n-1)+1+f(n-1)。所以：f(n)=2f(n-1)+1{現(xiàn)在就可以用遞推做了}f(1)=1f(2)=3f(3)=7f(4)=15f(n)=2n-1現(xiàn)在可以用數(shù)學(xué)方法做了練習(xí)1：簡(jiǎn)潔背包問題。有一個(gè)背包涵量為s，現(xiàn)有n件物品，重量分別為s1、s2、s3。。。Si（1<=i<=n）,假設(shè)si均為正數(shù)，從這n件物品中選擇若干件物品放入背包，使得放入總重量恰好為s，請(qǐng)輸出一種解，若無解輸出“NOANSWER”。練習(xí)2快速排序vara:array[1..10000]oflongint;n,i:longint;procedureqsort(s,t:longint);vari,j,x:longint;begini:=s;j:=t;x:=a[i];while(i<j)dobeginwhile(i<j)and(x<=a[j])dodec(j);a[i]:=a[j];while(i<j)and(a[i]<=x)doinc(i);a[j]:=a[i];end;a[i]:=x;ifs<i-1thenqsort(s,i-1);ifj+1<tthenqsort(j+1,t);end;回溯法的基本思想為：在按某種搜尋策略的搜尋過程中，在某種狀態(tài)，接著往前搜尋已經(jīng)確定不會(huì)得到正確答案的狀況下，我們可以返回上一搜尋狀態(tài)，去沿新的可能性接著搜尋。要回溯到上一狀態(tài)，則說明我們?cè)谇斑M(jìn)中的狀態(tài)必需保存下來，我們接受“?！眮泶娣拧；厮菖cdfs的關(guān)系在我們的實(shí)際生活和信息學(xué)奧賽當(dāng)中很多問題是不能用數(shù)學(xué)公式去解決的，解決問題的過程，往往是通過一系列的步驟，在每一步中依據(jù)條件的不同，又有多種可能性，為了達(dá)到問題最終的要求，在解決過程中須要遵循某種限制策略。對(duì)于此類問題，我們往往接受搜尋的方法來解決，而我們要探討的回溯法就是搜尋的限制策略之一。參考結(jié)構(gòu)：proceduretry(i:integer);varbeginifi>nthen輸出結(jié)果elseforj:=下界to上界dobeginx[i]:=h[j];if可行{滿足限界函數(shù)和約束條件}thenbegin置值；try(i+1);取消置值；end;end;end;例4：N皇后問題

在N*N的棋盤上放置N個(gè)皇后而彼此不受攻擊（即在棋盤的任一行，任一列和任一對(duì)角線上不能放置2個(gè)皇后），編程求解全部的擺放方法。八皇后的兩組解分析：由于皇后的擺放位置不能通過某種公式來確定，因此對(duì)于每個(gè)皇后的擺放位置都要進(jìn)行摸索和訂正，這就是“回溯”的思想。在N個(gè)皇后未放置完成前，擺放第I個(gè)皇后和第I+1個(gè)皇后的摸索方法是相同的，因此完全可以接受遞歸的方法來處理。下面是放置第I個(gè)皇后的的遞歸算法：ProcedureTry(I:integer)；{搜尋第I行皇后的位置}var j:integer;beginifI=n+1then輸出方案；forj:=1tondo if皇后能放在第I行第J列的位置thenbegin放置第I個(gè)皇后；對(duì)放置皇后的位置進(jìn)行標(biāo)記；Try（I+1）對(duì)放置皇后的位置釋放標(biāo)記； End;End;N皇后問題的遞歸算法的程序如下：programN_Queens;constMaxN=100; {最多皇后數(shù)}varA:array[1..MaxN]ofBoolean; {同列-豎線被限制標(biāo)記}B:array[2..MaxN*2]ofBoolean;{i+j和相等-左下到右上斜線被限制標(biāo)記}C:array[1–MaxN..MaxN–1]ofBoolean;{j-i差相等-左上到右下斜線被限制標(biāo)記}X:array[1..MaxN]ofInteger; {記錄皇后的解}Total:Longint; {解的總數(shù)}N:Integer; {皇后個(gè)數(shù)}procedureOut; {輸出方案}varI:Integer;beginInc(Total);Write(Total:3,‘:’);forI:=1toNdoWrite(X[I]:3);Writeln;end;procedureTry(I:Integer); {搜尋第I個(gè)皇后的可行位置}varJ:Integer;beginifI=N+1thenOut;{N個(gè)皇后都放置完畢，則輸出解}forJ:=1toNdoifA[J]andB[J+I]andC[J–I]thenbeginX[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;beginWrite(‘QueensNumbers=‘);Readln(N);FillChar(A,Sizeof(A),True);FillChar(B,Sizeof(B),True);FillChar(C,Sizeof(C),True);Try(1);Writeln(‘Total=‘,Total);end.上機(jī)練習(xí)題1.添加自然數(shù)問題。（add.pas）要求找出具有下列性質(zhì)的數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n)：先輸入一個(gè)自然數(shù)n(n<=500),然后對(duì)此自然數(shù)依據(jù)如下方法進(jìn)行處理:①.不作任何處理;②.在它的左邊加上一個(gè)自然數(shù),但該自然數(shù)不能超過原數(shù)的一半;③.加上數(shù)后,接著按此規(guī)則進(jìn)行處理,直到不能再加自然數(shù)為止.輸入文件：add.in,一行，n的值。輸出文件：add.out，一行，依據(jù)規(guī)則可產(chǎn)生的自然數(shù)個(gè)數(shù)。樣例：輸入文件：6滿足條件的數(shù)為

6

16

26

126

36

136輸出文件6varn,i:integer;s:real;procedureqiu(x:integer);vark:integer;beginifx<>0thenbegins:=s+1;fork:=1toxdiv2doqiu(k)endend;beginreadln(n);s:=0;qiu(n);writeln(s)end.2.跳馬問題。（jump.pas）在5*5格的棋盤上，有一個(gè)國(guó)際象棋的馬，它可以朝8個(gè)方向跳，但不允許出界或跳到已跳過的格子上，要求求出跳遍整個(gè)棋盤后的不同的路徑條數(shù)。輸出文件：jump.out，一行，路徑條數(shù)。programjump;varh:array[-1..7,-1..7]ofinteger;a,b:array[1..8]ofinteger;i,j,num:integer;procedureprint;vari,j:integer;beginnum:=num+1;{ifnum<=5thenbeginfori:=1to5dobeginforj:=1to5dowrite(h[i,j]:4);writeln;end;writeln;end;}end;

proceduretry(x,y,i:integer);varj,u,v:integer;beginforj:=1to8dobeginu:=x+a[j];v:=y+b[j];ifh[u,v]=0thenbeginh[u,v]:=i;ifi<25thentry(u,v,i+1)elseprint;h[u,v]:=0end;end;end;

beginfori:=-1to7doforj:=-1to7doif(i>=1)and(i<=5)and(j>=1)and(j<=5)thenh[i,j]:=0elseh[i,j]:=1;a[1]:=2;b[1]:=1;a[2]:=1;b[2]:=2;a[3]:=-1;b[3]:=2;a[4]:=-2;b[4]:=1;a[5]:=-2;b[5]:=-1;a[6]:=-1;b[6]:=-2;a[7]:=1;b[7]:=-2;a[8]:=2;b[8]:=-1;num:=0;h[1,1]:=1;try(1,1,2);writeln(num);end.深度優(yōu)先搜尋在信息學(xué)奧賽中，有的試題能在有限的時(shí)間內(nèi)，用簡(jiǎn)明的數(shù)學(xué)模型揭示問題的本質(zhì)，對(duì)于這類問題我們盡量用解析法求解；但也有些問題，很難建立數(shù)學(xué)模型，對(duì)于這類問題，我們只能接受模擬或搜尋求解，盡管搜尋的困難度一般都是指數(shù)級(jí)的，但在缺乏解決問題的有效模型時(shí)，搜尋卻是一種最行之有效的解決問題的方法，而且在用搜尋解決問題時(shí)，在實(shí)現(xiàn)過程中存在很大的優(yōu)化空間，在信息學(xué)奧賽中考察搜尋算法，除了考察選手的算法運(yùn)用實(shí)力，更重要的是考察選手的算法優(yōu)化實(shí)力，下面我們將介紹一些常用的搜尋策略。二：深度優(yōu)先搜尋1.算法思想深度優(yōu)先搜尋的搜尋策略是：盡可能“深”的搜尋某一分支。在深度優(yōu)先搜尋中，對(duì)于最先發(fā)覺的結(jié)點(diǎn)，假如還有以此為起點(diǎn)的未搜尋邊，則沿此邊接著搜尋下去。當(dāng)結(jié)點(diǎn)V的全部邊都已經(jīng)被探尋過，搜尋將回溯到發(fā)覺點(diǎn)V的那條邊的始結(jié)點(diǎn)。重復(fù)此過程直至源結(jié)點(diǎn)可到達(dá)的全部結(jié)點(diǎn)為止。2.深度優(yōu)先搜尋的基本算法結(jié)構(gòu)（1）遞歸實(shí)現(xiàn)。Proceduredfs_try(i);Fori:=1tomaxrdobeginif子結(jié)點(diǎn)mr符合條件thenbegin產(chǎn)生的子結(jié)點(diǎn)mr入棧；if子結(jié)點(diǎn)mr是目標(biāo)結(jié)點(diǎn)then輸出；elsedfs_try(i+1);棧頂元素出棧；End;End;例5、[問題描述]迷宮問題設(shè)有一個(gè)N*N方格的迷宮，入口和出口分別在左上角和右上角。迷宮格子中分別放有0和1，0表示可通，1表示不能，迷宮走的規(guī)則如下圖所示：即從某點(diǎn)起先，有八個(gè)方向可走，前進(jìn)方格中數(shù)字為0時(shí)表示可通過，為1時(shí)表示不行通過，要另找路徑。輸入例子：（從文件中讀取數(shù)據(jù)）80001101010110110010010010011010101000110011111010011101111000000輸出要求：找出一條從入口（左上角）到出口（右上角）的路徑(不能重復(fù))。(1,1)->(2,1)->(3,1)->(2,2)->(3,3)->(4,3)->(5,2)->(6,3)->(7,3)->(8,2)->(8,1)分析:a:array[1..maxn,1..maxn]of0..1;{記錄迷宮坐標(biāo)}c:array[1..maxn,1..maxn]of0..1;{訪問標(biāo)記:0:沒走;1:已走}b:array[0..maxn*maxn]ofinteger;{記錄路徑方向}dx,dy:array[1..8]ofinteger;{方向位移}8個(gè)方向的位移:

dx[1]:=0;dy[1]:=-1;dx[2]:=1;dy[2]:=-1;dx[3]:=1;dy[3]:=0;dx[4]:=1;dy[4]:=1;dx[5]:=0;dy[5]:=1;dx[6]:=-1;dy[6]:=1;dx[7]:=-1;dy[7]:=0;dx[8]:=-1;dy[8]:=-1;讀入數(shù)據(jù):{坐標(biāo)}procedurereaddata;beginassign(input,'a.in');reset(input);readln(n);fori:=1tondoforj:=1tondobegin

read(a[j,i]);{i:縱坐標(biāo);j:橫坐標(biāo)}

c[j,i]:=0;end;close(input);遞歸算法:proceduretry(i:integer);{搜尋第i步應(yīng)到達(dá)的位置}vark:integer;beginfork:=1to8dobeginif(x+dx[k]>=1)and(x+dx[k]<=n)and(y+dy[k]>=1)and(y+dy[k]<=n)and(a[x+dx[k],y+dy[k]]=0)and(c[x+dx[k],y+dy[k]]=0)thenbeginx:=x+dx[k];y:=y+dy[k];c[x,y]:=1;b[i]:=k;if(x=n)and(y=1)thenbeginprint(i);halt;endelsetry(i+1);c[x,y]:=0;x:=x-dx[k];y:=y-dy[k];end;end;end;輸出一組解:procedureprint(i:integer);varj:integer;beginx:=1;y:=1;write(‘(’,x,‘,’,y,‘)’);{初始位置}forj:=1toido{輸出路途}beginx:=x+dx[b[j]];y:=y+dy[b[j]];write('->','(',x,',',y,')');end;writeln;end;主程序:beginreaddata;x:=1;y:=1;try(1);end.1.由鍵盤輸入正整數(shù)N，生成1到N的全排列。（1<=N<=9）

例如：輸入2時(shí)，輸出：

11

12

21

22應(yīng)用之一：排列組合問題2.由鍵盤輸入正整數(shù)N，生成1到N的不重復(fù)全排列。（1<=N<=9）

例如：輸入2時(shí)，輸出：

12

21

3.輸出從N個(gè)元素中選取M個(gè)元素的各種排列（1≤N、M≤9）。例如：N=3M=2輸出：1213212331324.輸出從N個(gè)元素中選取M個(gè)元素的各種組合（1≤N、M≤9）。例如：N=3M=2輸出：1213235.已知兩個(gè)自然數(shù)n和k（n,k<=100），從1，2，……，n中任取k個(gè)數(shù)，要求所取的k個(gè)數(shù)中，隨意兩個(gè)數(shù)不能相差1。編程求有多少種取法。如：n=6，k=3,，從1，2，3，4，5，6中取3個(gè)數(shù)，隨意兩個(gè)數(shù)不能相差1，取法如下：（135）（136）（146）（246）共有4種取法。提示：（135）和（315）屬于一種取法。輸入（b.in）：一行，n和k，中間用空格隔開。輸出（b.out）：一行，取法的種數(shù)。樣例：輸入：63輸出：4過河卒

棋盤上A點(diǎn)有一個(gè)過河卒，須要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同時(shí)在棋盤上C點(diǎn)有一個(gè)對(duì)方的馬，該馬所在的點(diǎn)和全部跳動(dòng)一步可達(dá)的點(diǎn)稱為對(duì)方馬的限制點(diǎn)。因此稱之為“馬攔過河卒”。棋盤用坐標(biāo)表示，A點(diǎn)(0,

0)、B點(diǎn)(n,

m)(n,

m為不超過20的整數(shù))，同樣馬的位置坐標(biāo)是須要給出的?，F(xiàn)在要求你計(jì)算出卒