第四章遞歸算法

1、第四章第四章 遞歸算法遞歸算法 前面已經(jīng)介紹了關(guān)于遞歸調(diào)用這樣一種操作，而遞歸 程序設(shè)計是Pascal語言程序設(shè)計中的一種重要的方法，它 使許多復(fù)雜的問題變得簡單，容易解決了。遞歸特點是： 函數(shù)或過程調(diào)用它自己本身。其中直接調(diào)用自己稱為直接 遞歸，而將A調(diào)用B，B以調(diào)用A的遞歸叫做間接遞歸。 【例【例1】 給定給定N（N=1）,用遞歸的方法計算用遞歸的方法計算1+2+3+4+.+(n-1)+n。 【算法分析】 本題可以用遞歸方法求解，其原因在于它符合遞歸的三個條件： (1)本題是累加問題：當(dāng)前和=前一次和+當(dāng)前項，而前一次和的計算方法與其 相同，只是數(shù)據(jù)不同s(n)=s(n-1)+n; (2)

2、給定n,所以是有限次的遞歸調(diào)用； (3)結(jié)束條件是當(dāng)N=1，則S=1。 【參考程序】 program ex4_1; var s,t:integer; function fac(n:integer):integer; /遞歸函數(shù) begin if n=1 then fac:=1 else fac:=fac(n-1)+n; end; BEGIN read(t); /輸入t的值 s:=fac(t); /計算1到t的累加和 writeln(s=,s); /輸出結(jié)果 END. 運行程序，當(dāng)T=5時，輸出結(jié)果：S=15，其遞歸調(diào)用執(zhí)行過程是： （設(shè)T=3） 遞歸調(diào)用過程，實質(zhì)上是不斷調(diào)用過程或函數(shù)的過程，

3、由于遞歸調(diào) 用一次，所有子程序的變量（局部變量、變參等）、地址在計算機內(nèi)部 都有用特殊的管理方法棧（先進后出）來管理，一旦遞歸調(diào)用結(jié)束， 計算機便開始根據(jù)棧中存儲的地址返回各子程序變量的值，并進行相應(yīng) 操作。 【例【例2】 設(shè)有設(shè)有N個數(shù)已經(jīng)按從大到小的順序排列，現(xiàn)在輸入個數(shù)已經(jīng)按從大到小的順序排列，現(xiàn)在輸入X，判斷它是，判斷它是 否在這否在這N個數(shù)中，如果存在則輸出：個數(shù)中，如果存在則輸出：“YES” 否則輸出否則輸出“NO”。 【算法分析】 該問題屬于數(shù)據(jù)的查找問題，數(shù)據(jù)查找有多種方法，通常方法是：順 序查找和二分查找，當(dāng)N個數(shù)排好序時，用二分查找方法速度大大加快。 二分查找算法： （1）

4、 設(shè)有N個數(shù)，存放在A數(shù)組中，待查找數(shù)為X，用F指向數(shù)據(jù)的高 端，用R指向數(shù)據(jù)的低端，MID指向中間： （2） 若X=AMID 輸出 “YES”； （3）若XAMID則到數(shù)據(jù)前半段查找：F不變，R=MID-1，計算新的 MID值，并進行新的一段查找； （5）若FR都沒有查找到，則輸出“NO”。 該算法符合遞歸程序設(shè)計的基本規(guī)律，可以用遞歸方法設(shè)計。 【參考程序】【參考程序】 program ex4_2; const n=10; var a:array1.nof integer; f,r,x,k:integer; procedure search(x,top,bot:integer); /二分查

5、找遞歸過程二分查找遞歸過程 var mid :integer; begin if top=bot then begin mid:=(top+bot) div 2 /求中間數(shù)的位置求中間數(shù)的位置 if x=amid then writeln(yes) /找到就輸出找到就輸出 else if xC; (2)當(dāng)N=2時，則需要移動三次： A- 1 - B, A - 2 - C, B - 1- C. (3)如果N=3，則具體移動步驟為： 假設(shè)把第3步，第4步，第7步抽出來就相當(dāng)于N=2的情況（把上面2片 捆在一起，視為一片）： 所以可按“N=2”的移動步驟設(shè)計： 如果N=0，則退出，即結(jié)束程序;否則繼

6、續(xù)往下執(zhí)行; 用C柱作為協(xié)助過渡，將A柱上的（N-1）片移到B柱上，調(diào)用過程mov(n-1, a,b,c); 將A柱上剩下的一片直接移到C柱上; 用A柱作為協(xié)助過渡，將B柱上的（N-1）移到C柱上，調(diào)用過程mov (n- 1,b,c,a)。 【參考程序】【參考程序】 Program ex4_3; Var x,y,z : char; N, k : integer; Procedure mov (n: integer; a, c , b: char); begin if n=0 then exit; /如果如果N=0，則退出，即結(jié)束程序，則退出，即結(jié)束程序 mov (n-1, a,b,c); /用

7、用C柱作為協(xié)助過渡，將柱作為協(xié)助過渡，將A柱上的（柱上的（N-1）片移到）片移到B柱上柱上 inc(k); writeln(k, : from, a, -, c); mov (n-1,b,c,a); /用用A柱作為協(xié)助過渡，將柱作為協(xié)助過渡，將B柱上的（柱上的（N-1）移到）移到C柱上柱上 end; begin write(n=); readln(n); k:=0; x:=a; y:=b; z:=c; mov (n,x,z,y); end. 程序定義了把n片從A柱移到C柱的過程mov (n,a,c,b)，這個過程把移動 分為以下三步來進行： 先調(diào)用過程mov (n-1, a, b, c)，把(

8、n-1)片從A柱移到B柱, C柱作為過 渡柱; 直接執(zhí)行 writeln(a, -, c)，把A柱上剩下的一片直接移到C柱 上，; 調(diào)用mov (n-1,b,c,a)，把B柱上的(n-1)片從B移到C柱上，A柱是過渡 柱。 對于B柱上的(n-1)片如何移到，仍然調(diào)用上述的三步。只是把(n-1)當(dāng)成 了n，每調(diào)用一次，要移到目標(biāo)柱上的片數(shù)N就減少了一片，直至減少到 n=0時就退出，不再調(diào)用。exit是退出指令，執(zhí)行該指令能在循環(huán)或遞歸調(diào) 用過程中一下子全部退出來。 mov過程中出現(xiàn)了自己調(diào)用自己的情況，在Pascal中稱為遞歸調(diào)用，這 是Pascal語言的一個特色。對于沒有遞歸調(diào)用功能的程序設(shè)計

9、語言，則需 要將遞歸過程重新設(shè)計為非遞歸過程的程序。 【例【例4】用遞歸的方法求斐波那契數(shù)列中的第用遞歸的方法求斐波那契數(shù)列中的第N個數(shù)個數(shù) 【參考程序】【參考程序】 program ex4_4 var m,p:integer; function fib(n:integer):integer; begin if n=0 then fib:=0 /滿足邊界條件，遞歸返回滿足邊界條件，遞歸返回 else if n=1 then fib:=1 /滿足邊界條件，遞歸返回滿足邊界條件，遞歸返回 else fib:=fib(n-1)+fib(n-2); /遞歸公式，進一步遞歸遞歸公式，進一步遞歸 end;

10、 begin readln(m); /輸入值輸入值 p:=fib(m); writeln(fib(,m,)=,p) /輸出結(jié)果輸出結(jié)果 end. 輸入輸入 15 輸出輸出 fib(15)=610 【課堂練習(xí)】【課堂練習(xí)】 1、輸入一串以！結(jié)束的字符，按逆序輸出。（用遞歸做） 2、背包問題 問題：假設(shè)有n件質(zhì)量分配為w1，w2，.，wn的物品和一個最多能裝載 總質(zhì)量為T的背包，能否從這n件物品中選擇若干件物品裝入背包，使得被選 物品的總質(zhì)量恰好等于背包所能裝載的最大質(zhì)量，即wi1+wi2+.+wik=T。若 能，則背包問題有解，否則無解。 (例如：有5件可選物品，質(zhì)量分別為8千克、4千克、3千克

11、、5千克、1千克。 假設(shè)背包的最大轉(zhuǎn)載質(zhì)量是10千克。) 3、阿克曼（Ackmann）函數(shù)A(x，y)中，x，y定義域是非負(fù)整數(shù)，函數(shù)值定 義為： 寫出計算Ack(m，n)的遞歸算法程序。 4、某人寫了n封信和n個信封，如果所有的信都裝錯了信封。求所有的信 都裝錯信封共有多少種不同情況。 基本形式：D1=0;d2=1 遞歸式：dn= (n-1)*( dn-1 + dn-2) 5、有52張牌，使它們?nèi)空娉?，第一輪是從?張開始，凡是2的倍 數(shù)位置上的牌翻成正面朝下；第二輪從第3張牌開始，凡是3的倍數(shù)位置上 的牌，正面朝上的翻成正面朝下,正面朝下的翻成正面朝上；第三輪從第4 張牌開始，凡是4

12、的倍數(shù)位置上的牌按上面相同規(guī)則翻轉(zhuǎn)，以此類推，直 到第一張要翻的牌超過52為止。統(tǒng)計最后有幾張牌正面朝上，以及它們的 位置號。 6、猴子吃桃問題 猴子第一天摘下若干桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個。第 二天早上又將剩下的桃子吃掉的一半，又多吃了一個。以后每天早上都吃 掉了前一天剩下的一半零一個。到第10天早上想再吃時，見只剩下一個桃 子了。求第一天共摘多少桃子。（答案：1534） 【上機練習(xí)】【上機練習(xí)】 1、斐波那切數(shù)列、斐波那切數(shù)列 【問題描述】【問題描述】 斐波那切數(shù)列0，1，1，2，3，5，8，13，21，34，55從第三項起，每一項都 是緊挨著的前兩項的和。寫出計算斐波那切

13、數(shù)列的任意一個數(shù)據(jù)項遞歸程序。 【輸入格式】【輸入格式】 輸入所求的項數(shù)。 【輸出格式】【輸出格式】 輸出數(shù)據(jù)項的值。 【輸入樣例】【輸入樣例】fbi.in 10 【輸出樣例】【輸出樣例】fbi.out 34 2、倒序數(shù)、倒序數(shù) 【問題描述】【問題描述】 用遞歸算法寫程序，輸入一個非負(fù)整數(shù)，輸出這個數(shù)的倒序數(shù)。 【輸入格式】【輸入格式】 輸入一個非負(fù)整數(shù)。 【輸出格式】【輸出格式】 輸出倒序結(jié)果。 【輸入樣例】【輸入樣例】num.in 123 【輸出樣例】【輸出樣例】num.out 321 3、十進制轉(zhuǎn)換成八進制、十進制轉(zhuǎn)換成八進制 【問題描述】【問題描述】 用遞歸算法，把任一給定的十進制正整

14、數(shù)轉(zhuǎn)換成八進制數(shù)輸出。 【輸入格式】【輸入格式】 輸入一個正整數(shù)，表示需要轉(zhuǎn)換的十進制數(shù)。 【輸出格式】【輸出格式】 輸出一個正整數(shù)，表示轉(zhuǎn)換之后的八進制的數(shù)。 【輸入樣例】【輸入樣例】change.in 15 【輸出樣例】【輸出樣例】change.out 17 4、求、求N！的值！的值 【問題描述】【問題描述】 用遞歸算法，求N！的精確值(N以一般整數(shù)輸入)。 【輸入樣例】【輸入樣例】ni.in 10 【輸出樣例】【輸出樣例】ni.out 10!=3628800 5、求最大公約數(shù)、求最大公約數(shù) 【問題描述】 用遞歸方法求兩個數(shù)m和n的最大公約數(shù)。 【輸入格式】 輸入二個數(shù)，即m和n的值。 【

15、輸出格式】 輸出最大公約數(shù)。 【輸入樣例】 8 6 【輸出樣例】 gcd=2 6、雙色、雙色Hanoi塔問題塔問題 【問題描述】【問題描述】 設(shè)A、B、C是3 個塔座。開始時，在塔座A 上有一疊共n 個圓盤，這些圓 盤自下而上，由大到小地疊在一起。各圓盤從小到大編號為1，2，n， 奇數(shù)號圓盤著藍色，偶數(shù)號圓盤著紅色，如圖所示?，F(xiàn)要求將塔座A 上的這一 疊圓盤移到塔座B 上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī) 則： 規(guī)則(1)：每次只能移動1 個圓盤； 規(guī)則(2)：任何時刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則(3)：任何時刻都不允許將同色圓盤疊在一起； 規(guī)則(4)：在滿足

16、移動規(guī)則(1)-(3)的前提下，可將圓盤移至A，B，C 中任 一塔座上。 試設(shè)計一個算法，用最少的移動次數(shù)將塔座A 上的n個圓盤移到塔座B 上， 并仍按同樣順序疊置。 【編程任務(wù)】【編程任務(wù)】 對于給定的正整數(shù)n，編程計算最優(yōu)移動方案。 【輸入格式】【輸入格式】 由文件hanoi.in給出輸入數(shù)據(jù)。第1 行是給定的正整數(shù)n。 【輸出格式】【輸出格式】 將計算出的最優(yōu)移動方案輸出到文件hanoi.out。文件的每一行由一個 正整數(shù)k和2個字符c1和c2組成，表示將第k個圓盤從塔座c1移到塔座c2上。 【輸入樣例】【輸入樣例】 3 【輸出樣例】【輸出樣例】 1 A B 2 A C 1 B C 3

17、A B 1 C A 2 C B 1 A B 7、背包問題、背包問題 【問題描述】【問題描述】 簡單的背包問題。設(shè)有一個背包，可以放入的重量為s?，F(xiàn)有n件物品， 重量分別為w1,w2，wn，（1in）均為正整數(shù)，從n件物品中挑選若干件， 使得放入背包的重量之和正好為s。找到一組解即可。 【輸入格式】【輸入格式】 第一行是物品總件數(shù)和背包的載重量，第二行為各物品的重量。 【輸出格式】【輸出格式】 各所選物品重量。 【輸入樣例】【輸入樣例】 5 10 1 2 3 4 5 【輸出樣例】【輸出樣例】 number:1 weight:1 number:4 weight:4 number:5 weight:

18、5 8、2的冪次方（的冪次方（Noip1998） 【問題描述】【問題描述】 任何一個正整數(shù)都可以用2的冪次方表示。例如： 137=27+23+20 同時約定方次用括號來表示，即ab 可表示為a（b）。 由此可知，137可表示為： 2（7）+2（3）+2（0） 進一步：7= 22+2+20 （21用2表示） 3=2+20 所以最后137可表示為： 2（2（2）+2+2（0）+2（2+2（0）+2（0） 又如： 1315=210 +28 +25 +2+1 所以1315最后可表示為： 2（2（2+2（0）+2）+2（2（2+2（0）+2（2（2）+2（0）+2+2（0） 【輸入格式】【輸入格式】 正

19、整數(shù)（n20000） 【輸出格式】【輸出格式】 符合約定的n的0，2表示（在表示中不能有空格） 【輸入樣例】【輸入樣例】 137 【輸出樣例】【輸出樣例】 2(2(2)+2+2(0)+2(2+2(0)+2(0) 9、數(shù)的計數(shù)（、數(shù)的計數(shù)（Noip2001） 【問題描述】【問題描述】 我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入的自然數(shù)n): 先輸入一個自然數(shù)n（n1000）, 然后對此自然數(shù)按照如下方法進行處理： 1不作任何處理； 2在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)(輸入的n)的 一半； 3加上數(shù)后，繼續(xù)按此規(guī)則進行處理，直到不能再加自然數(shù)為止。 【輸入樣例】【輸入樣例】 6 滿足條件的數(shù)為 6 (此部分不必輸出) 16 26 126 36 136 【輸出樣例】【輸出樣例】 6 10、集合劃分問題、集合劃分問題 【問題描述】【問題描述】 n個元素的集合1,2, n 可以劃分為若干個非空子集。例如，當(dāng)n=4 時，集