遞歸與回溯算法教學(xué)內(nèi)容

遞歸與回溯算法遞歸的調(diào)用

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

elsefac:=fac(n-1)*n;end;例1：按照以上的分析，用遞歸的方法來求N！的解。程序如下：測(cè)試數(shù)據(jù)：輸入：inputn=5輸出：5!=120beginwrite('inputn=');read(n);ifn<0thenwriteln('n<0,dataerrer')elsebegint:=fac(n);writeln(n,'!=',t)endend.3如圖展示了程序的執(zhí)行過程：在這里，因?yàn)楹瘮?shù)FAC的形參是值形參，因此每調(diào)用一次該函數(shù)，系統(tǒng)就為本次調(diào)用的值形參N開辟了一個(gè)存儲(chǔ)單元，以便存放它的實(shí)參的值。也就是說，對(duì)于遞歸函數(shù)或遞歸過程，每當(dāng)對(duì)它調(diào)用一次時(shí)，系統(tǒng)都要為它的形式參數(shù)與局部變量（在函數(shù)或過程中說明的變量）分配存儲(chǔ)單元（這是一個(gè)獨(dú)立的單元，雖然名字相同，但實(shí)際上是互不相干的，只在本層內(nèi)有效），并記下返回的地點(diǎn)，以便返回后程序從此處開始執(zhí)行。4例2：讀入一串字符倒序輸出，以字符’&’為結(jié)束標(biāo)志，用過程來實(shí)現(xiàn)。分析：由題意可知，讀一串字符當(dāng)然只能一個(gè)個(gè)地讀入，要倒序輸出，就要一直讀到字符’&’。如輸入的一段字符為ABCDEFGH&’，則倒序輸出的結(jié)果應(yīng)該是’&HGFEDCBA’。（1）讀入一個(gè)字符；（2）讀（該字符后的）子串并倒序輸出；（3）然后輸出讀入字符（指（1）讀入的字符）（4）在（2）中若子串是空（即遇字符’&’），表示子串已完，不再處理子串。以上（2）表示一操作依賴另一操作，所以需要用遞歸調(diào)用。（4）表示已知操作（遞歸的終止）。5程序如下：programaa;procedurereverse;varch:char;beginread(ch);ifch<>'&'thenreverse;write(ch);end;beginreverse;writeln;end.測(cè)試數(shù)據(jù)：輸入：abcdefghijklmn&輸出：&nmlkjihgfedcba6例3：利用遞歸，將一個(gè)十進(jìn)制整數(shù)K轉(zhuǎn)化為N進(jìn)制整數(shù)（N<=10）。測(cè)試數(shù)據(jù)：輸入：K和N的值193輸出：轉(zhuǎn)化后的N進(jì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遞歸的一般適合場(chǎng)合1．?dāng)?shù)據(jù)的定義形式是按遞歸定義的.如：裴波那契數(shù)列的定義為：Fn=Fn-1+Fn-2F1=0F2=1beginread(n);s:=fib(n);writeln(s);end.測(cè)試數(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例如；著名的Hanoi塔（漢諾塔）問題。3．?dāng)?shù)據(jù)之間的結(jié)構(gòu)關(guān)系按遞歸定義的例如：大家將在后面的學(xué)習(xí)內(nèi)容中遇到的樹的遍歷、圖的搜索等問題。2．問題的求解方法是按遞歸算法來實(shí)現(xiàn)的。9判斷運(yùn)行結(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輸出:練習(xí)一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程序設(shè)計(jì)1.（文件名：d4.pas）利用遞歸過程，將一個(gè)十進(jìn)制整數(shù)K轉(zhuǎn)化為7進(jìn)制整數(shù)。測(cè)試數(shù)據(jù)：輸入：十進(jìn)制數(shù)K19輸出：7進(jìn)制整數(shù)25132.（文件名：d5.pas）樓梯有N階臺(tái)階，上樓可以一步上一階，也可以一步上二階，計(jì)算共有多少種不同走法。測(cè)試數(shù)據(jù)：輸入：輸入N的值6輸出：走法總數(shù)13提示：N=1f(1)=1N=2f(2)=2當(dāng)N>=3時(shí)f(N)=f(N-1)+f(N-2)14遞歸及其應(yīng)用請(qǐng)計(jì)算ack(m,n)的值。(m,n<=5)例4:已知:ack(m,n)函數(shù)的計(jì)算公式如下: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.測(cè)試數(shù)據(jù)輸入：34輸出：12516其Pascal程序如下：例5:用輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m,n的最大公約數(shù)。思路：輾轉(zhuǎn)相除法規(guī)定：求兩個(gè)正整數(shù)m,n（m>=n）的最大公約數(shù)，應(yīng)先將m除以n；求得余數(shù)r,如果等于零，除數(shù)n就是m,n的最大公約數(shù)；如果r不等于零，就用n除以r，再看所得余數(shù)是否為零。重復(fù)上面過程，直到余數(shù)r為零時(shí)，則上一次的余數(shù)值即為m,n的最大公約數(shù)。用其數(shù)學(xué)方式描述如下: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.測(cè)試數(shù)據(jù)輸入：2018輸出：gd=218functionfib(n:integer):longint;beginif(n=0)or(n=1)thenfib:=1elsefib:=fib(n-1)+fib(n-2);end;爬樓梯時(shí)可以1次走1個(gè)臺(tái)階，也可以1次走2個(gè)臺(tái)階。對(duì)于由n個(gè)臺(tái)階組成的樓梯，共有多少種不同的走法？1個(gè)臺(tái)階：只有1種走法；2個(gè)臺(tái)階：有兩種走法；(1+1；2)n個(gè)臺(tái)階(n>2)，記走法為f(n)：第1次走1個(gè)臺(tái)階，還剩(n-1)個(gè)臺(tái)階，走法為f(n-1)；第1次走2個(gè)臺(tái)階，還剩(n-2)個(gè)臺(tái)階，走法為f(n-2)。所以，f(n)=f(n-1)+f(n-2)。定義f(0)=1，則有：19遞歸過程或函數(shù)直接（或間接）調(diào)用自身，但如果僅有這些操作，那么將會(huì)由于無休止地調(diào)用而引起死循環(huán)。因此一個(gè)正確的遞歸程序雖然每次調(diào)用的是相同的子程序，但它的參數(shù)、輸入數(shù)據(jù)等均有所變化，并且在正常的情況下，隨著調(diào)用的深入，必定會(huì)出現(xiàn)調(diào)用到某一層時(shí)，不再執(zhí)行調(diào)用而是終止函數(shù)的執(zhí)行。遞歸思路是把一個(gè)不能或不好直接求解的“大問題”轉(zhuǎn)化成一個(gè)或幾個(gè)“小問題”來解決，再把這些“小問題”進(jìn)一步分解成更小的“小問題”來解決，如此分解，直至每個(gè)“小問題”都可以直接解決。遞歸分解不是隨意地分解，要保證“大問題”和“小問題”相似。例：采用遞歸算法求實(shí)數(shù)數(shù)組A[0..n]中的最小值。20算法1:設(shè)f(a,i)為數(shù)組元素a[0]..a[i]中的最小值。當(dāng)i=0時(shí)，有f(a,i)=a[0]；假設(shè)f(a,i-1)已求出，則：算法2：設(shè)f(i,j)為a[i]..a[j]中的最小值。將a[0]..a[n]看作一個(gè)線性表，它可以分解成a[0]..a[i]和a[i+1]..a[n]兩個(gè)子表，分別求得各自的最小值x和y，較小者就是a[0]..a[n]中的最小值。而求解子表中的最小值方法與總表相同，即再分別把它們分成兩個(gè)更小的子表，如此不斷分解，直到表中只有一個(gè)元素為止(該元素就是該表中的最小值)。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個(gè)半徑各不相同的圓盤，按半徑從大到小，自下而上依次套在A柱上，另外還有B、C兩根空柱。要求將A柱上的n個(gè)圓盤全部搬到C柱上去，每次只能搬動(dòng)一個(gè)盤子，且必須始終保持每根柱子上是小盤在上，大盤在下。輸出總共移動(dòng)的次數(shù)及移動(dòng)方案。ABC23思路：假定可以通過某個(gè)過程把1針上面的N-1個(gè)盤搬到過渡針2中，然后把1針中剩下的1個(gè)盤移動(dòng)到3針，然后再把過渡針2中的N-1個(gè)盤移到3針去，這樣完成了移盤。思路是很明確的，我們把N個(gè)盤子移動(dòng)問題轉(zhuǎn)化成N-1個(gè)盤子移動(dòng)問題，即如何從1針把N-1個(gè)盤子移動(dòng)到2針和從2針把N-1個(gè)盤子移動(dòng)到3針。同理，移N-1個(gè)盤子問題又可以進(jìn)一步簡(jiǎn)化為移N-2盤子問題，這種簡(jiǎn)化過程實(shí)質(zhì)就是一個(gè)遞歸過程。但遞歸過程不能永遠(yuǎn)遞歸下去，必須有邊界條件令過程停止調(diào)用。顯然，邊界條件是當(dāng)只有一個(gè)盤子時(shí)，僅需作最后一次移動(dòng)即可。下面為移盤子游戲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.測(cè)試數(shù)據(jù)：輸入:3輸出:1------>31------>23------>21------>32------>12------>31------>325例7:數(shù)的計(jì)算（1）問題描述我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n):先輸入一個(gè)自然數(shù)n(n<=1000),然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理:1、不作任何處理;2、在它的左邊加上一個(gè)自然數(shù),但該自然數(shù)不能超過原數(shù)的一半;3、加上數(shù)后,繼續(xù)按此規(guī)則進(jìn)行處理,直到不能再加自然數(shù)為止.26樣例:

輸入:

6

滿足條件的數(shù)為

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）問題描述從鍵盤輸入一個(gè)多位數(shù)(N>0,N位數(shù)小于等于9位），用遞歸方法把這個(gè)多位數(shù)顛倒過來輸出。（2）問題解析由于N比較大，所以需要長(zhǎng)整型。長(zhǎng)整型的位數(shù)<=10位。（3）測(cè)試數(shù)據(jù)輸入：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)有一對(duì)雌雄兔，每?jī)蓚€(gè)月就繁殖各一對(duì)兔子。問N個(gè)月后共有多少對(duì)兔子？提示：測(cè)試數(shù)據(jù):輸入:10輸出:55練習(xí)二312.(文件名:d7.pas)計(jì)算組合數(shù)提示：測(cè)試數(shù)據(jù):輸入:62輸出:15323.前N項(xiàng)和（1）問題描述給定N(N>=1)，用遞歸的方法計(jì)算1+2+3+4+......+(N-1)+N,結(jié)果賦值給S。（2）測(cè)試數(shù)據(jù)輸入: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搜索算法對(duì)于給定的問題,如果有簡(jiǎn)明的數(shù)學(xué)模型揭示問題的本質(zhì),我們盡量用解析法求解；如果無法建立數(shù)學(xué)模型,或者即使有一定的數(shù)學(xué)模型,但采用數(shù)學(xué)方法解決有一定的困難,我們只好用模擬或搜索來求解。

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

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

ttry（k+1）；

end;end;43三、如何判斷第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方法二：設(shè)置標(biāo)志col:array[1..n]ofboolean;//col[i]=true，表示第i列上已有皇后left:array[2..2*n]ofboolean;//left[i]=true,表示行列和為i的對(duì)角線上已有皇后right:array[1-n..n-1]ofboolean;//right[i]=true,表示行列差為i的對(duì)角線上已有皇后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個(gè)皇后的位置vari:integer;beginifk=n+1thenbegintot:=tot+1;out;end;//n個(gè)皇后都放置完畢，輸出解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個(gè)皇后的位置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