遞歸與回溯算法

會計學1遞歸與回溯算法2也就是說，求解N!的過程可以用以下遞歸方法來表示：在這里，為了定義n!，就必須先定義(n-1)!，為了定義(n-1)!，又必須先定義(n-2)!……，上述這種用自身的簡單情況來定義自己的方式稱為遞歸定義。一個遞歸定義必須是有確切含義的，也就是說，必須一步比一步簡單，最后是有終結(jié)的，決不允許無限循環(huán)下去。上面的例子中，當N=0時定義一個數(shù)1，是最簡單的情況，稱為遞歸的邊界，它本身不再使用遞歸定義。與遞推一樣，每一遞歸都有其邊界條件。但不同的是，遞推是由邊界條件出發(fā)，通過遞推式來求值，而遞歸則是從自身出發(fā)來達到邊界條件。第1頁/共50頁3遞歸的調(diào)用

在Pascal程序中，子程序可以直接自己調(diào)用自己或間接調(diào)用自己，則將這種調(diào)用形式稱之為遞歸調(diào)用。其中，我們將前者的調(diào)用方式稱為簡單遞歸，后者稱為間接遞歸。由于目前我們介紹、掌握的知識尚還無法實現(xiàn)間接遞歸，只有留待在以后的內(nèi)容中我們再作介紹。本節(jié)只介紹直接遞歸。遞歸調(diào)用時必須符合以下三個條件：

（1）可將一個問題轉(zhuǎn)化為一個新的問題，而新問題的解決方法仍與原問題的解法相同，只不過所處理的對象有所不同而已，即它們只是有規(guī)律的遞增或遞減。

（2）可以通過轉(zhuǎn)化過程使問題回到對原問題的求解。

（3）必須要有一個明確的結(jié)束遞歸的條件，否則遞歸會無止境地進行下去。

下面我們通過一些例子，來解釋遞歸程序的設計。第2頁/共50頁4programaa;vart:longint;n:integer;functionfac(n:integer):longint;beginifn=0thenfac:=1

elsefac:=fac(n-1)*n;end;例1：按照以上的分析，用遞歸的方法來求N！的解。程序如下：測試數(shù)據(jù)：輸入：inputn=5輸出：5!=120beginwrite('inputn=');read(n);ifn<0thenwriteln('n<0,dataerrer')elsebegint:=fac(n);writeln(n,'!=',t)endend.第3頁/共50頁5如圖展示了程序的執(zhí)行過程：

在這里，因為函數(shù)FAC的形參是值形參，因此每調(diào)用一次該函數(shù)，系統(tǒng)就為本次調(diào)用的值形參N開辟了一個存儲單元，以便存放它的實參的值。也就是說，對于遞歸函數(shù)或遞歸過程，每當對它調(diào)用一次時，系統(tǒng)都要為它的形式參數(shù)與局部變量（在函數(shù)或過程中說明的變量）分配存儲單元（這是一個獨立的單元，雖然名字相同，但實際上是互不相干的，只在本層內(nèi)有效），并記下返回的地點，以便返回后程序從此處開始執(zhí)行。第4頁/共50頁6例2：讀入一串字符倒序輸出，以字符’&’為結(jié)束標志，用過程來實現(xiàn)。分析：由題意可知，讀一串字符當然只能一個個地讀入，要倒序輸出，就要一直讀到字符’&’。如輸入的一段字符為ABCDEFGH&’，則倒序輸出的結(jié)果應該是’&HGFEDCBA’。（1）讀入一個字符；（2）讀（該字符后的）子串并倒序輸出；（3）然后輸出讀入字符（指（1）讀入的字符）（4）在（2）中若子串是空（即遇字符’&’），表示子串已完，不再處理子串。

以上（2）表示一操作依賴另一操作，所以需要用遞歸調(diào)用。（4）表示已知操作（遞歸的終止）。第5頁/共50頁7程序如下：programaa;procedurereverse;varch:char;beginread(ch);ifch<>'&'thenreverse;write(ch);end;beginreverse;writeln;end.測試數(shù)據(jù)：輸入：abcdefghijklmn&輸出：&nmlkjihgfedcba第6頁/共50頁8例3：利用遞歸，將一個十進制整數(shù)K轉(zhuǎn)化為N進制整數(shù)（N<=10）。測試數(shù)據(jù)：輸入：K和N的值193輸出：轉(zhuǎn)化后的N進制整數(shù)201programaa;varn,k:integer;proceduretentok(k,n:integer);varr:integer;beginr:=kmodn;

k:=kdivn;ifk<>0thententok(k,n);write(r);end;beginread(k,n);tentok(k,n);writeln;end.第7頁/共50頁9遞歸的一般適合場合1．數(shù)據(jù)的定義形式是按遞歸定義的.如：裴波那契數(shù)列的定義為：Fn=Fn-1+Fn-2F1=0F2=1beginread(n);s:=fib(n);writeln(s);end.測試數(shù)據(jù)：輸入：5輸出：3programaa;varn:integer;s:longint;FunctionFIB(N:integer):integer;BeginIfn=1thenFIB:=0Elseifn=2thenFIB:=1

ElseFIB:=FIB(n-1)+FIB(n-2)

End;第8頁/共50頁10例如；著名的Hanoi塔（漢諾塔）問題。3．數(shù)據(jù)之間的結(jié)構(gòu)關系按遞歸定義的例如：大家將在后面的學習內(nèi)容中遇到的樹的遍歷、圖的搜索等問題。2．問題的求解方法是按遞歸算法來實現(xiàn)的。第9頁/共50頁11判斷運行結(jié)果1.programd1;

var

s,n:integer;

functionf(n:integer):integer;

begin

ifn=1thenf:=1

elsef:=n*n+f(n-1);

end;

begin

write('inputn:');readln(n);

s:=f(n);

writeln('f(',n,')=',s)

end.輸入:inputn:3輸出:練習一第10頁/共50頁122．programd2;

var

a,b:integer;

functionf(n:integer):integer;

begin

ifn=1thenf:=1

elseifn=2thenf:=2

elsef:=f(n-1)+f(n-2);

end;

begin

read(a);

b:=f(a);

writeln(b);

end.輸入:4輸出:第11頁/共50頁133．programd3;

var

a,b,c,d:integer;

procedurep(a:integer;varb:integer);

var

c:integer;

begin

a:=a+1;b:=b+1;c:=2;d:=d+1;

writeln('m',a,b,c,d);

ifa<3thenp(a,b);

writeln('n',a,b,c,d)

end;

begin

a:=1;b:=1;c:=1;d:=1;

writeln('x',a,b,c,d);

p(a,b);

writeln('y',a,b,c,d);

end.第12頁/共50頁14程序設計1.（文件名：d4.pas）利用遞歸過程，將一個十進制整數(shù)K轉(zhuǎn)化為7進制整數(shù)。測試數(shù)據(jù)：輸入：十進制數(shù)K19輸出：7進制整數(shù)25第13頁/共50頁152.（文件名：d5.pas）樓梯有N階臺階，上樓可以一步上一階，也可以一步上二階，計算共有多少種不同走法。測試數(shù)據(jù)：輸入：輸入N的值6輸出：走法總數(shù)13提示：N=1f(1)=1N=2f(2)=2當N>=3時f(N)=f(N-1)+f(N-2)第14頁/共50頁16遞歸及其應用請計算ack(m,n)的值。(m,n<=5)例4:已知:ack(m,n)函數(shù)的計算公式如下:第15頁/共50頁17programaa;

var

m,n:longint;

a:longint;

functionack(m,n:longint):longint;

begin

ifm=0thenack:=n+1

elseifn=0thenack:=ack(m-1,1)

elseack:=ack(m-1,ack(m,n-1))

end;

begin

read(m,n);

a:=ack(m,n);

writeln(a);

end.測試數(shù)據(jù)輸入：34輸出：125第16頁/共50頁18其Pascal程序如下：例5:用輾轉(zhuǎn)相除法求兩個自然數(shù)m,n的最大公約數(shù)。思路：輾轉(zhuǎn)相除法規(guī)定：求兩個正整數(shù)m,n（m>=n）的最大公約數(shù)，應先將m除以n；求得余數(shù)r,如果等于零，除數(shù)n就是m,n的最大公約數(shù)；如果r不等于零，就用n除以r，再看所得余數(shù)是否為零。重復上面過程，直到余數(shù)r為零時，則上一次的余數(shù)值即為m,n的最大公約數(shù)。用其數(shù)學方式描述如下:第17頁/共50頁19programaa;

var

m,n,t:integer;

functionf(m,n:integer):integer;

varr:integer;

begin

if(mmodn)=0thenf:=n

else

begin

r:=mmodn;

f:=f(n,r);

end;

end;begin

readln(m,n);

ifm<nthen

begin

t:=m;

m:=n;

n:=t;

end;

writeln('gd=',f(m,n));end.測試數(shù)據(jù)輸入：2018輸出：gd=2第18頁/共50頁20functionfib(n:integer):longint;beginif(n=0)or(n=1)thenfib:=1elsefib:=fib(n-1)+fib(n-2);end;

爬樓梯時可以1次走1個臺階，也可以1次走2個臺階。對于由n個臺階組成的樓梯，共有多少種不同的走法？1個臺階：只有1種走法；2個臺階：有兩種走法；(1+1；2)n個臺階(n>2)，記走法為f(n)：

第1次走1個臺階，還剩(n-1)個臺階，走法為f(n-1)；

第1次走2個臺階，還剩(n-2)個臺階，走法為f(n-2)。所以，f(n)=f(n-1)+f(n-2)。定義f(0)=1，則有：第19頁/共50頁21

遞歸過程或函數(shù)直接（或間接）調(diào)用自身，但如果僅有這些操作，那么將會由于無休止地調(diào)用而引起死循環(huán)。因此一個正確的遞歸程序雖然每次調(diào)用的是相同的子程序，但它的參數(shù)、輸入數(shù)據(jù)等均有所變化，并且在正常的情況下，隨著調(diào)用的深入，必定會出現(xiàn)調(diào)用到某一層時，不再執(zhí)行調(diào)用而是終止函數(shù)的執(zhí)行。

遞歸思路是把一個不能或不好直接求解的“大問題”轉(zhuǎn)化成一個或幾個“小問題”來解決，再把這些“小問題”進一步分解成更小的“小問題”來解決，如此分解，直至每個“小問題”都可以直接解決。

遞歸分解不是隨意地分解，要保證“大問題”和“小問題”相似。例：采用遞歸算法求實數(shù)數(shù)組A[0..n]中的最小值。第20頁/共50頁22算法1:設f(a,i)為數(shù)組元素a[0]..a[i]中的最小值。當i=0時，有f(a,i)=a[0]；假設f(a,i-1)已求出，則：算法2：設f(i,j)為a[i]..a[j]中的最小值。將a[0]..a[n]看作一個線性表，它可以分解成a[0]..a[i]和a[i+1]..a[n]兩個子表，分別求得各自的最小值x和y，較小者就是a[0]..a[n]中的最小值。而求解子表中的最小值方法與總表相同，即再分別把它們分成兩個更小的子表，如此不斷分解，直到表中只有一個元素為止(該元素就是該表中的最小值)。第21頁/共50頁23functionmin(i,j:integer):real;varmid:integer;min1,min2:real;beginifi=jthenmin:=a[i]elsebeginmid:=(i+j)div2;min1:=min(i,mid);min2:=min(mid+1,j);ifmin1<min2thenmin:=min1elsemin:=min2;end;end;第22頁/共50頁24漢諾塔問題：

有n個半徑各不相同的圓盤，按半徑從大到小，自下而上依次套在A柱上，另外還有B、C兩根空柱。要求將A柱上的n個圓盤全部搬到C柱上去，每次只能搬動一個盤子，且必須始終保持每根柱子上是小盤在上，大盤在下。輸出總共移動的次數(shù)及移動方案。ABC第23頁/共50頁25思路：假定可以通過某個過程把1針上面的N-1個盤搬到過渡針2中，然后把1針中剩下的1個盤移動到3針，然后再把過渡針2中的N-1個盤移到3針去，這樣完成了移盤。思路是很明確的，我們把N個盤子移動問題轉(zhuǎn)化成N-1個盤子移動問題，即如何從1針把N-1個盤子移動到2針和從2針把N-1個盤子移動到3針。同理，移N-1個盤子問題又可以進一步簡化為移N-2盤子問題，這種簡化過程實質(zhì)就是一個遞歸過程。但遞歸過程不能永遠遞歸下去，必須有邊界條件令過程停止調(diào)用。顯然，邊界條件是當只有一個盤子時，僅需作最后一次移動即可。下面為移盤子游戲PASCAL程序。第24頁/共50頁26programaa;

var

n:integer;

proceduremove(n,a,b,c:integer);

begin

ifn=1then

writeln(a,'------>',c)

else

begin

move(n-1,a,c,b);

writeln(a,'------>',c);

move(n-1,b,a,c);

end;

end;

begin

readln(n);

move(n,1,2,3);

end.測試數(shù)據(jù)：輸入:3輸出:1------>31------>23------>21------>32------>12------>31------>3第25頁/共50頁27例7:數(shù)的計算（1）問題描述我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入的自然數(shù)n):先輸入一個自然數(shù)n(n<=1000),然后對此自然數(shù)按照如下方法進行處理:1、不作任何處理;2、在它的左邊加上一個自然數(shù),但該自然數(shù)不能超過原數(shù)的一半;3、加上數(shù)后,繼續(xù)按此規(guī)則進行處理,直到不能再加自然數(shù)為止.第26頁/共50頁28樣例:

輸入:

6

滿足條件的數(shù)為

6(此部分不必輸出)

16

26

126

36

136輸出:

6第27頁/共50頁29Var

ans,n:Longint;

proceduredfs(m:Longint);

vari:Longint;

begininc(ans);

fori:=1tomdiv2dodfs(i);

end;

begin

ans:=0;

read(n);

dfs(n);

writeLn(ans);

end.參考程序第28頁/共50頁30例8:反序輸出（1）問題描述從鍵盤輸入一個多位數(shù)(N>0,N位數(shù)小于等于9位），用遞歸方法把這個多位數(shù)顛倒過來輸出。（2）問題解析由于N比較大，所以需要長整型。長整型的位數(shù)<=10位。（3）測試數(shù)據(jù)輸入：12345678輸出：87654321第29頁/共50頁31programaa;

varn:Longint;

procedurerd(number:Longint);

begin

write(numbermod10:1);

number:=numberdiv10;

ifnumber<>0thenrd(number);

end;

begin

write('inputn=');

readLn(n);

rd(n);

end.第30頁/共50頁321.(文件名:d6.pas)有一對雌雄兔，每兩個月就繁殖各一對兔子。問N個月后共有多少對兔子？提示：測試數(shù)據(jù):輸入:10輸出:55練習二第31頁/共50頁332.(文件名:d7.pas)計算組合數(shù)提示：測試數(shù)據(jù):輸入:62輸出:15第32頁/共50頁343.前N項和（1）問題描述給定N(N>=1)，用遞歸的方法計算1+2+3+4+......+(N-1)+N,結(jié)果賦值給S。（2）測試數(shù)據(jù)輸入:5輸出:s=15第33頁/共50頁35程序提示:programaa;

vart:integer;s:Longint;

functionfac(n:integer):Longint;

begin

ifn=1thenfac:=

（1）

eLsefac:=

（2）;

end;

begin

read(t);s:=fac(t);

writeLn('s=',

（3）);

end.

第34頁/共50頁36搜索算法

對于給定的問題,如果有簡明的數(shù)學模型揭示問題的本質(zhì),我們盡量用解析法求解；如果無法建立數(shù)學模型,或者即使有一定的數(shù)學模型,但采用數(shù)學方法解決有一定的困難,我們只好用模擬或搜索來求解。

盡管搜索的時間復雜度一般是指數(shù)級的，但在缺乏解決問題的有效模型時，搜索卻是一種行之有效的解決問題的基本方法，而且使用搜索算法解決問題時，在實現(xiàn)過程中有很大的優(yōu)化空間。信息學奧賽中考察搜索算法，一是考察選手算法運用能力，二是考察選手算法優(yōu)化能力。枚舉法（窮舉法）回溯（深度優(yōu)先搜索）廣度優(yōu)先搜索第35頁/共50頁37

回溯法是搜索算法中的一種控制策略，它是從初始狀態(tài)出發(fā)，運用題目給出的條件、規(guī)則，按照深度優(yōu)先搜索的順序擴展所有可能情況，從中找出滿足題意要求的解答。即：從問題的某一種可能出發(fā),搜索從這種情況出發(fā)所能達到的所有可能,如果有路可以走下去，就走到下一個狀態(tài)，繼續(xù)按照這種規(guī)則搜索；當這一條路走到“盡頭”而沒達到目標狀態(tài)的時候,再倒回上一個出發(fā)點,從另一個可能出發(fā),繼續(xù)搜索，直到達到目標狀態(tài)。第36頁/共50頁38例：迷宮求解

從迷宮的入口進去后是如何找到出口的？

如果你不了解迷宮結(jié)構(gòu)顯然只能是摸索著前進，比如先往一個方向走，若走不通那就只能退回來再試試另一個方向。但在走的過程中你一定會有意識地“記住”你已經(jīng)走過的路，否則你會被困在迷宮中永遠也走不出來了。

計算機解迷宮時，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止,如果所有可能的通路都試探過，還是不能走到終點，那就說明該迷宮不存在從起點到終點的通道。

先看兩個動畫演示的例子。第37頁/共50頁39第38頁/共50頁40第39頁/共50頁41由此，求迷宮中一條路徑的算法的基本思想是：

若當前位置“可通”，則納入“當前路徑”，并繼續(xù)朝“下一位置”探索；

若當前位置“不可通”，則應順著“來的方向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個方塊均“不可通”，則應從“當前路徑”上刪除該通道塊。

第40頁/共50頁42

例：n皇后問題

在n×n的國際象棋棋盤上，放置n個皇后，使任何一個皇后都不能吃掉另一個,需滿足的條件是：

同一行、同一列、同一對角線上只能有一個皇后。求所有滿足要求的放置方案。第41頁/共50頁43【分析】一、問題解的形式：x:array[1..n]ofinteger;//x[i]:第i個皇后放在第i行，第x[i]列，保證所有皇后不同行問題的解變成求（x[1]，x[2]，…，x[n]）4皇后問題的解：（2，4，1，3），（3，1，4，2）第42頁/共50頁44二、放置第k(1<=k<=n)個皇后的遞歸算法：Procedurettry(k);//搜索第k個皇后所在的列x[k],前k-1個已放好,即已求得x[1]…x[k-1]vari:integer;beginifk=n+1thenprint//輸出放置方案：數(shù)組xelsefori:=1tondo//搜索第k個皇后所在的列iif第k個皇后能夠放置在第i列thenbegin放置第k個皇后在第i列（x[k]=i）；

ttry（k+1）；

end;end;第43頁/共50頁45三、如何判斷第k行的皇后能不能放在第i列：方法一：定義函數(shù)functionok(k,i:integer):boolean;varj:integer;beginforj:=1tok-1do

if(x[j]=i)or(x[j]+j=k+i)or(x[j]-j=k-i)thenbeginok:=false;exit;end;ok:=true;end;第44頁/共50頁46方法二：設置標志col:array[1..n]ofboolean;//col[i]=true，表示第i列上已有皇后left:array[2..2*n]ofboolean;//left[i]=true,表示行列和為i的對角線上已有皇后right:array[1-n..n-1]ofboolean;//right[i]=true,表示行列差為i的對角線上已有皇后programqueen;//遞歸算法constmaxn=10;varx:array[1..maxn]ofinteger;n,i,tot:integer;col:array[1..maxn]ofboolean;left:array[2..2*maxn]ofboolean;right:array[1-maxn..maxn-1]ofboolean;procedureout;//輸出解vari:integer;beginfori:=1ton-1dowrite(x[i],'');writeln(x[n]);end;第45頁/共50頁47procedurettry(k:integer);//搜索第k個皇后的位置vari:integer;beginifk=n+1thenbegintot:=tot+1;out;end;//n個皇后都放置完畢，輸出解fori:=1tondoifnot(col[i]orleft[k+i]orright[k-i])thenbeginx[k]:=i;//記錄第k行皇后的位置col[i]:=true;left[k+i]:=true;right[k-i]:=true;ttry(k+1);//搜索第k+1個皇后的位置col[i]:=false;left[k+i]:=false;right[k-i]:=false;//回溯end;end;第46頁/共50頁48beginassign(input,’queen.in’);reset(input);assign(output,’queen.out’);rewrite(output);