遞歸與回溯算法教學內容

遞歸與回溯算法遞歸的調用

在Pascal程序中，子程序可以直接自己調用自己或間接調用自己，則將這種調用形式稱之為遞歸調用。其中，我們將前者的調用方式稱為簡單遞歸，后者稱為間接遞歸。由于目前我們介紹、掌握的知識尚還無法實現間接遞歸，只有留待在以后的內容中我們再作介紹。本節(jié)只介紹直接遞歸。遞歸調用時必須符合以下三個條件：（1）可將一個問題轉化為一個新的問題，而新問題的解決方法仍與原問題的解法相同，只不過所處理的對象有所不同而已，即它們只是有規(guī)律的遞增或遞減。（2）可以通過轉化過程使問題回到對原問題的求解。（3）必須要有一個明確的結束遞歸的條件，否則遞歸會無止境地進行下去。下面我們通過一些例子，來解釋遞歸程序的設計。2programaa;vart:longint;n:integer;functionfac(n:integer):longint;beginifn=0thenfac:=1

elsefac:=fac(n-1)*n;end;例1：按照以上的分析，用遞歸的方法來求N！的解。程序如下：測試數據：輸入：inputn=5輸出：5!=120beginwrite('inputn=');read(n);ifn<0thenwriteln('n<0,dataerrer')elsebegint:=fac(n);writeln(n,'!=',t)endend.3如圖展示了程序的執(zhí)行過程：在這里，因為函數FAC的形參是值形參，因此每調用一次該函數，系統(tǒng)就為本次調用的值形參N開辟了一個存儲單元，以便存放它的實參的值。也就是說，對于遞歸函數或遞歸過程，每當對它調用一次時，系統(tǒng)都要為它的形式參數與局部變量（在函數或過程中說明的變量）分配存儲單元（這是一個獨立的單元，雖然名字相同，但實際上是互不相干的，只在本層內有效），并記下返回的地點，以便返回后程序從此處開始執(zhí)行。4例2：讀入一串字符倒序輸出，以字符’&’為結束標志，用過程來實現。分析：由題意可知，讀一串字符當然只能一個個地讀入，要倒序輸出，就要一直讀到字符’&’。如輸入的一段字符為ABCDEFGH&’，則倒序輸出的結果應該是’&HGFEDCBA’。（1）讀入一個字符；（2）讀（該字符后的）子串并倒序輸出；（3）然后輸出讀入字符（指（1）讀入的字符）（4）在（2）中若子串是空（即遇字符’&’），表示子串已完，不再處理子串。以上（2）表示一操作依賴另一操作，所以需要用遞歸調用。（4）表示已知操作（遞歸的終止）。5程序如下：programaa;procedurereverse;varch:char;beginread(ch);ifch<>'&'thenreverse;write(ch);end;beginreverse;writeln;end.測試數據：輸入：abcdefghijklmn&輸出：&nmlkjihgfedcba6例3：利用遞歸，將一個十進制整數K轉化為N進制整數（N<=10）。測試數據：輸入：K和N的值193輸出：轉化后的N進制整數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遞歸的一般適合場合1．數據的定義形式是按遞歸定義的.如：裴波那契數列的定義為：Fn=Fn-1+Fn-2F1=0F2=1beginread(n);s:=fib(n);writeln(s);end.測試數據：輸入：5輸出：3programaa;varn:integer;s:longint;FunctionFIB(N:integer):integer;BeginIfn=1thenFIB:=0Elseifn=2thenFIB:=1

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

End;8例如；著名的Hanoi塔（漢諾塔）問題。3．數據之間的結構關系按遞歸定義的例如：大家將在后面的學習內容中遇到的樹的遍歷、圖的搜索等問題。2．問題的求解方法是按遞歸算法來實現的。9判斷運行結果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輸出:練習一102．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輸出:113．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程序設計1.（文件名：d4.pas）利用遞歸過程，將一個十進制整數K轉化為7進制整數。測試數據：輸入：十進制數K19輸出：7進制整數25132.（文件名：d5.pas）樓梯有N階臺階，上樓可以一步上一階，也可以一步上二階，計算共有多少種不同走法。測試數據：輸入：輸入N的值6輸出：走法總數13提示：N=1f(1)=1N=2f(2)=2當N>=3時f(N)=f(N-1)+f(N-2)14遞歸及其應用請計算ack(m,n)的值。(m,n<=5)例4:已知:ack(m,n)函數的計算公式如下:15programaa;

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

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.測試數據輸入：2018輸出：gd=218functionfib(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遞歸過程或函數直接（或間接）調用自身，但如果僅有這些操作，那么將會由于無休止地調用而引起死循環(huán)。因此一個正確的遞歸程序雖然每次調用的是相同的子程序，但它的參數、輸入數據等均有所變化，并且在正常的情況下，隨著調用的深入，必定會出現調用到某一層時，不再執(zhí)行調用而是終止函數的執(zhí)行。遞歸思路是把一個不能或不好直接求解的“大問題”轉化成一個或幾個“小問題”來解決，再把這些“小問題”進一步分解成更小的“小問題”來解決，如此分解，直至每個“小問題”都可以直接解決。遞歸分解不是隨意地分解，要保證“大問題”和“小問題”相似。例：采用遞歸算法求實數數組A[0..n]中的最小值。20算法1:設f(a,i)為數組元素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]中的最小值。而求解子表中的最小值方法與總表相同，即再分別把它們分成兩個更小的子表，如此不斷分解，直到表中只有一個元素為止(該元素就是該表中的最小值)。21functionmin(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漢諾塔問題：有n個半徑各不相同的圓盤，按半徑從大到小，自下而上依次套在A柱上，另外還有B、C兩根空柱。要求將A柱上的n個圓盤全部搬到C柱上去，每次只能搬動一個盤子，且必須始終保持每根柱子上是小盤在上，大盤在下。輸出總共移動的次數及移動方案。ABC23思路：假定可以通過某個過程把1針上面的N-1個盤搬到過渡針2中，然后把1針中剩下的1個盤移動到3針，然后再把過渡針2中的N-1個盤移到3針去，這樣完成了移盤。思路是很明確的，我們把N個盤子移動問題轉化成N-1個盤子移動問題，即如何從1針把N-1個盤子移動到2針和從2針把N-1個盤子移動到3針。同理，移N-1個盤子問題又可以進一步簡化為移N-2盤子問題，這種簡化過程實質就是一個遞歸過程。但遞歸過程不能永遠遞歸下去，必須有邊界條件令過程停止調用。顯然，邊界條件是當只有一個盤子時，僅需作最后一次移動即可。下面為移盤子游戲PASCAL程序。24programaa;

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

輸入:

6

滿足條件的數為

6(此部分不必輸出)

16

26

126

36

136輸出:

627Var

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例8:反序輸出（1）問題描述從鍵盤輸入一個多位數(N>0,N位數小于等于9位），用遞歸方法把這個多位數顛倒過來輸出。（2）問題解析由于N比較大，所以需要長整型。長整型的位數<=10位。（3）測試數據輸入：12345678輸出：8765432129programaa;

varn:Longint;

procedurerd(number:Longint);

begin

write(numbermod10:1);

number:=numberdiv10;

ifnumber<>0thenrd(number);

end;

begin

write('inputn=');

readLn(n);

rd(n);

end.301.(文件名:d6.pas)有一對雌雄兔，每兩個月就繁殖各一對兔子。問N個月后共有多少對兔子？提示：測試數據:輸入:10輸出:55練習二312.(文件名:d7.pas)計算組合數提示：測試數據:輸入:62輸出:15323.前N項和（1）問題描述給定N(N>=1)，用遞歸的方法計算1+2+3+4+......+(N-1)+N,結果賦值給S。（2）測試數據輸入:5輸出:s=1533程序提示: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搜索算法對于給定的問題,如果有簡明的數學模型揭示問題的本質,我們盡量用解析法求解；如果無法建立數學模型,或者即使有一定的數學模型,但采用數學方法解決有一定的困難,我們只好用模擬或搜索來求解。

盡管搜索的時間復雜度一般是指數級的，但在缺乏解決問題的有效模型時，搜索卻是一種行之有效的解決問題的基本方法，而且使用搜索算法解決問題時，在實現過程中有很大的優(yōu)化空間。信息學奧賽中考察搜索算法，一是考察選手算法運用能力，二是考察選手算法優(yōu)化能力。枚舉法（窮舉法）回溯（深度優(yōu)先搜索）廣度優(yōu)先搜索35回溯法是搜索算法中的一種控制策略，它是從初始狀態(tài)出發(fā)，運用題目給出的條件、規(guī)則，按照深度優(yōu)先搜索的順序擴展所有可能情況，從中找出滿足題意要求的解答。即：從問題的某一種可能出發(fā),搜索從這種情況出發(fā)所能達到的所有可能,如果有路可以走下去，就走到下一個狀態(tài)，繼續(xù)按照這種規(guī)則搜索；當這一條路走到“盡頭”而沒達到目標狀態(tài)的時候,再倒回上一個出發(fā)點,從另一個可能出發(fā),繼續(xù)搜索，直到達到目標狀態(tài)。36例：迷宮求解從迷宮的入口進去后是如何找到出口的？ 如果你不了解迷宮結構顯然只能是摸索著前進，比如先往一個方向走，若走不通那就只能退回來再試試另一個方向。但在走的過程中你一定會有意識地“記住”你已經走過的路，否則你會被困在迷宮中永遠也走不出來了。 計算機解迷宮時，通常用的是“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止,如果所有可能的通路都試探過，還是不能走到終點，那就說明該迷宮不存在從起點到終點的通道。 先看兩個動畫演示的例子。373839由此，求迷宮中一條路徑的算法的基本思想是：若當前位置“可通”，則納入“當前路徑”，并繼續(xù)朝“下一位置”探索；若當前位置“不可通”，則應順著“來的方向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個方塊均“不可通”，則應從“當前路徑”上刪除該通道塊。

40例：n皇后問題在n×n的國際象棋棋盤上，放置n個皇后，使任何一個皇后都不能吃掉另一個,需滿足的條件是：同一行、同一列、同一對角線上只能有一個皇后。求所有滿足要求的放置方案。41【分析】一、問題解的形式：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二、放置第k(1<=k<=n)個皇后的遞歸算法：Procedurettry(k);//搜索第k個皇后所在的列x[k],前k-1個已放好,即已求得x[1]…x[k-1]vari:integer;beginifk=n+1thenprint//輸出放置方案：數組xelsefori:=1tondo//搜索第k個皇后所在的列iif第k個皇后能夠放置在第i列thenbegin放置第k個皇后在第i列（x[k]=i）；

ttry（k+1）；

end;end;43三、如何判斷第k行的皇后能不能放在第i列：方法一：定義函數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方法二：設置標志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;45procedurettry(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;46beginassign(input,’queen.in’);reset(input);assign(output,’queen.out’);rewrite(output);fillchar(col,sizeof(col),false);fillchar(left,sizeof(left),false);fillchar(right,sizeof(right),f