第四章遞歸算法

1、第四章第四章 遞歸算法遞歸算法 前面已經(jīng)介紹了關(guān)于遞歸調(diào)用這樣一種操作，而遞歸 程序設(shè)計是Pascal語言程序設(shè)計中的一種重要的方法，它 使許多復(fù)雜的問題變得簡單，容易解決了。遞歸特點(diǎn)是： 函數(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)前項(xià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. 運(yùn)行程序，當(dāng)T=5時，輸出結(jié)果：S=15，其遞歸調(diào)用執(zhí)行過程是： （設(shè)T=3） 遞歸調(diào)用過程，實(shí)質(zhì)上是不斷調(diào)用過程或函數(shù)的過程，

3、由于遞歸調(diào) 用一次，所有子程序的變量（局部變量、變參等）、地址在計算機(jī)內(nèi)部 都有用特殊的管理方法棧（先進(jìn)后出）來管理，一旦遞歸調(diào)用結(jié)束， 計算機(jī)便開始根據(jù)棧中存儲的地址返回各子程序變量的值，并進(jìn)行相應(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值，并進(jìn)行新的一段查找； （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)，這個過程把移動 分為以下三步來進(jìn)行： 先調(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); /遞歸公式，進(jìn)一步遞歸遞歸公式，進(jìn)一步遞歸 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） 【上機(jī)練習(xí)】【上機(jī)練習(xí)】 1、斐波那切數(shù)列、斐波那切數(shù)列 【問題描述】【問題描述】 斐波那切數(shù)列0，1，1，2，3，5，8，13，21，34，55從第三項(xiàng)起，每一項(xiàng)都 是緊挨著的前兩項(xiàng)的和。寫出計算斐波那切

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

14、數(shù)轉(zhuǎn)換成八進(jìn)制數(shù)輸出。 【輸入格式】【輸入格式】 輸入一個正整數(shù)，表示需要轉(zhuǎn)換的十進(jìn)制數(shù)。 【輸出格式】【輸出格式】 輸出一個正整數(shù)，表示轉(zhuǎn)換之后的八進(jì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ù)號圓盤著藍(lán)色，偶數(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） 進(jìn)一步：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ù)按照如下方法進(jìn)行處理： 1不作任何處理； 2在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)(輸入的n)的 一半； 3加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止。 【輸入樣例】【輸入樣例】 6 滿足條件的數(shù)為 6 (此部分不必輸出) 16 26 126 36 136 【輸出樣例】【輸出樣例】 6 10、集合劃分問題、集合劃分問題 【問題描述】【問題描述】 n個元素的集合1,2, n 可以劃分為若干個非空子集。例如，當(dāng)n=4 時，集