第4章遞歸算法(C版)

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

2、1，則s=1。 【參考程序】#includeusing namespace std;int fac(int); /遞歸函數(shù)int main()int t;cint; /輸入t的值couts=fac(t)endl; /計(jì)算1到t的累加和，輸出結(jié)果int fac(int n)if (n=1) return 1;return (fac(n-1)+n); /調(diào)用下一層遞歸 運(yùn)行程序，當(dāng)T=5時(shí)，輸出結(jié)果：S=15，其遞歸調(diào)用執(zhí)行過程是：（設(shè)T=3） 遞歸調(diào)用過程，實(shí)質(zhì)上是不斷調(diào)用過程或函數(shù)的過程，由于遞歸調(diào)用一次，所有子程序的變量（局部變量、變參等）、地址在計(jì)算機(jī)內(nèi)部都有用特殊的管理方法棧（先進(jìn)后出）

3、來管理，一旦遞歸調(diào)用結(jié)束，計(jì)算機(jī)便開始根據(jù)棧中存儲(chǔ)的地址返回各子程序變量的值，并進(jìn)行相應(yīng)操作。 【例2】 設(shè)有N個(gè)數(shù)已經(jīng)按從大到小的順序排列，現(xiàn)在輸入X，判斷它是否在這N個(gè)數(shù)中，如果存在則輸出：“YES” 否則輸出“NO”。 【算法分析】 該問題屬于數(shù)據(jù)的查找問題，數(shù)據(jù)查找有多種方法，通常方法是：順序查找和二分查找，當(dāng)N個(gè)數(shù)排好序時(shí)，用二分查找方法速度大大加快。二分查找算法： （1） 設(shè)有N個(gè)數(shù)，存放在A數(shù)組中，待查找數(shù)為X，用L指向數(shù)據(jù)的高端，用R指向數(shù)據(jù)的低端，MID指向中間： （2） 若X=AMID 輸出 “YES”； （3）若XAMID則到數(shù)據(jù)前半段查找：L不變，R=MID-1，計(jì)算新

4、的MID值，并進(jìn)行新的一段查找； （5）若LR都沒有查找到，則輸出“NO”。 該算法符合遞歸程序設(shè)計(jì)的基本規(guī)律，可以用遞歸方法設(shè)計(jì)。 【參考程序】 #include#includeusing namespace std;int a11;void search(int,int,int);int main() /主程序int k,x,L=1,R=10;cout輸入10個(gè)從大到小順序的數(shù)：endl;for (k=1;kak;cinx;search(x,L,R); system(pause); void search(int x,int top,int bot) /二分查找遞歸過程 int mid;

5、if (top=bot) mid=(top+bot)/2; /求中間數(shù)的位置 if (x=amid) cout“YES”endl; /找到就輸出 else if (xamid) search(x,mid+1,bot); /判斷在前半段還是后半段查找 else search(x,top,mid-1); else coutNOC; (2)當(dāng)N=2時(shí)，則需要移動(dòng)三次： A-1 - B, A -2 - C, B -1- C. (3)如果N=3，則具體移動(dòng)步驟為： 假設(shè)把第3步，第4步，第7步抽出來就相當(dāng)于N=2的情況（把上面2片捆在一起，視為一片）： 所以可按“N=2”的移動(dòng)步驟設(shè)計(jì)： 如果N=0，則

6、退出，即結(jié)束程序;否則繼續(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)?！緟⒖汲绦颉?#includeusing namespace std;int k=0,n;void mov(int n,char a,char c,char b) /用b柱作為協(xié)助過渡，將a柱上的（n）移到c柱上if (n=0) return; /如果n=0，則退出，即結(jié)束程序mov(n-1,a,b,c ); /用c柱作為協(xié)助過渡，將a

7、柱上的（n-1）片移到b柱上k+;cout k :from a cendl; /超時(shí)改scanf和printfmov(n-1,b,c,a ); /用a柱作為協(xié)助過渡，將b柱上的（n-1）移到c柱上int main() coutn; mov(n,a,c,b); 程序定義了把n片從A柱移到C柱的過程mov (n,a,c,b)，這個(gè)過程把移動(dòng)分為以下三步來進(jìn)行： 先調(diào)用過程mov(n-1, a, b, c)，把(n-1)片從A柱移到B柱, C柱作為過渡柱; 直接執(zhí)行 cout(a, -, c)，把A柱上剩下的一片直接移到C柱上，; 調(diào)用mov(n-1,b,c,a)，把B柱上的(n-1)片從B移到C柱

8、上，A柱是過渡柱。 對(duì)于B柱上的(n-1)片如何移到C柱，仍然調(diào)用上述的三步。只是把(n-1)當(dāng)成了n，每調(diào)用一次，要移到目標(biāo)柱上的片數(shù)N就減少了一片，直至減少到n=0時(shí)就退出，不再調(diào)用。exit是退出指令，執(zhí)行該指令能在循環(huán)或遞歸調(diào)用過程中一下子全部退出來。 mov過程中出現(xiàn)了自己調(diào)用自己的情況，在C+中稱為遞歸調(diào)用，這是C+語言的一個(gè)特色。對(duì)于沒有遞歸調(diào)用功能的程序設(shè)計(jì)語言，則需要將遞歸過程重新設(shè)計(jì)為非遞歸過程的程序。 【例4】用遞歸的方法求斐波那契數(shù)列中的第N個(gè)數(shù) 【參考程序】#includeusing namespace std;int a11;int fib(int);int mai

9、n() int m; cinm; coutfib(m)=k，k0)。 下面，我們來確定S(n，k)的邊界條件,首先不能把n個(gè)元素不放進(jìn)任何一個(gè)集合中去，即k=0時(shí)，S(n，k)0；也不可能在不允許空盒的情況下把n個(gè)元素放進(jìn)多于n的k個(gè)集合中去，即kn時(shí),S(n，k)0；再者，把n個(gè)元素放進(jìn)一個(gè)集合或把n個(gè)元素放進(jìn)n個(gè)集合，方案數(shù)顯然都是1，即k=1或k=n時(shí)，S(n,k)=1。 因此，我們可以得出劃分?jǐn)?shù)S(n，k)的遞歸關(guān)系式為： S(n，k)S(n1，k1) + k * S(n1，k) (nk，k0) S(n，k)0 (nk)或(k0) S(n，k)1 (k=1)或(kn)【參考程序】 #i

10、ncludeusing namespace std;int s(int n, int k) /數(shù)據(jù)還有可能越界，請(qǐng)用高精度計(jì)算 if (n n k; cout s(n,k); return 0;【例6】數(shù)的計(jì)數(shù)(Noip2001)【問題描述】我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)（包括輸入的自然數(shù)n）。先輸入一個(gè)自然數(shù)n（n1000），然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理：不作任何處理；在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半；加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止。輸入：自然數(shù)n（n1000）輸出：滿足條件的數(shù)【輸入樣例】 6 滿足條件的數(shù)為 6 (此部分不必輸出) 1

11、6 26 126 36 136【輸出樣例】 6【方法一】用遞歸，f(n)=1+f(1)+f(2)+f(div/2)，當(dāng)n較大時(shí)會(huì)超時(shí)，時(shí)間應(yīng)該為指數(shù)級(jí)?！緟⒖汲绦颉?includeusing namespace std;int ans;void dfs(int m) /統(tǒng)計(jì)m所擴(kuò)展出的數(shù)據(jù)個(gè)數(shù) int i; ans+; /每出現(xiàn)一個(gè)原數(shù)，累加器加1； for (i = 1; i n; dfs(n); cout ans; return 0; 【方法二】：用記憶化搜索，實(shí)際上是對(duì)方法一的改進(jìn)。設(shè)hi表示自然數(shù)i滿足題意三個(gè)條件的數(shù)的個(gè)數(shù)。如果用遞歸求解，會(huì)重復(fù)來求一些子問題。例如在求h4時(shí)，需要再

12、求h1和h2的值。現(xiàn)在我們用h數(shù)組記錄在記憶求解過程中得出的所有子問題的解，當(dāng)遇到重疊子問題時(shí)，直接使用前面記憶的結(jié)果?！緟⒖汲绦颉?includeusing namespace std;int h1001;void dfs(int m) int i; if (hm != -1) return; /說明前面已經(jīng)求得hm的值，直接引用即可，不需要再遞歸 hm = 1; /將hm置為1，表示m本身為一種情況 for (i = 1; i n; for (int i = 1; i = n; i+) hi = -1; /h數(shù)組初始化為-1 dfs(n); /由頂?shù)较掠洃浕f歸求解 cout hn; re

13、turn 0;【方法三】 用遞推，用h(n)表示自然數(shù)n所能擴(kuò)展的數(shù)據(jù)個(gè)數(shù)，則h(1)=1, h(2)=2, h(3)=2, h(4)=4, h(5)=4, h(6)=6, h(7)=6, h(8)=10, h(9)=10.分析以上數(shù)據(jù)，可得遞推公式：h(i)=1+h(1)+h(2)+h(i/2)。此算法的時(shí)間度為O(n*n)。設(shè)hi-i按照規(guī)則擴(kuò)展出的自然數(shù)個(gè)數(shù)(1in)。下表列出了hi值及其方案：【參考程序】#includeusing namespace std;int h10001;int main() int n; cin n; for (int i = 1; i = n; i+) /

14、按照遞增順序計(jì)算擴(kuò)展出的自然數(shù)的個(gè)數(shù) hi = 1; /擴(kuò)展出的自然數(shù)包括i本身 for (int j = 1; j = i/2; j+) /i左邊分別加上1自然數(shù) 按規(guī)則擴(kuò)展出的自然數(shù) hi += hj; cout hn; return 0;【方法四】是對(duì)方法三的改進(jìn)，我們定義數(shù)組s，s(x)=h(1)+h(2)+h(x),h(x)=s(x)-s(x-1)，此算法的時(shí)間復(fù)雜度可降到O(n)?！緟⒖汲绦颉?includeusing namespace std;int h1001,s1001;int main() int n; cin n; for (int i = 1; i = n; i+)

15、hi = 1 + si/2; si = si-1 + hi; /s是h的前綴累加和 cout hn; return 0;【方法五】 還是用遞推，只要作仔細(xì)分析，其實(shí)我們還可以得到以下的遞推公式: (1)當(dāng)i為奇數(shù)時(shí)，h(i)=h(i-1); (2)當(dāng)i為偶數(shù)時(shí),h(i)=h(i-1)+h(i/2).【參考程序】#includeusing namespace std;int h1001;int main() int n; cin n; h1 = 1; for (int i = 2; i = n; i+) hi = hi-1; if (i % 2 = 0) hi = hi-1 + hi/2; co

16、ut 0，n0) 【輸入格式】 輸入二個(gè)數(shù)，即m和n的值?！据敵龈袷健?輸出最大公約數(shù)?！据斎霕永?8 6【輸出樣例】 gcd=26、雙色Hanoi塔問題【問題描述】 設(shè)A、B、C是3 個(gè)塔座。開始時(shí)，在塔座A 上有一疊共n 個(gè)圓盤，這些圓盤自下而上，由大到小地疊在一起。各圓盤從小到大編號(hào)為1，2，n，奇數(shù)號(hào)圓盤著藍(lán)色，偶數(shù)號(hào)圓盤著紅色，如圖所示?，F(xiàn)要求將塔座A 上的這一疊圓盤移到塔座B 上，并仍按同樣順序疊置。在移動(dòng)圓盤時(shí)應(yīng)遵守以下移動(dòng)規(guī)則： 規(guī)則(1)：每次只能移動(dòng)1 個(gè)圓盤； 規(guī)則(2)：任何時(shí)刻都不允許將較大的圓盤壓在較小的圓盤之上； 規(guī)則(3)：任何時(shí)刻都不允許將同色圓盤疊在一起；

17、 規(guī)則(4)：在滿足移動(dòng)規(guī)則(1)-(3)的前提下，可將圓盤移至A，B，C 中任一塔座上。 試設(shè)計(jì)一個(gè)算法，用最少的移動(dòng)次數(shù)將塔座A 上的n個(gè)圓盤移到塔座B 上，并仍按同樣順序疊置?！揪幊倘蝿?wù)】 對(duì)于給定的正整數(shù)n，編程計(jì)算最優(yōu)移動(dòng)方案。【輸入格式】 由文件hanoi.in給出輸入數(shù)據(jù)。第1 行是給定的正整數(shù)n。【輸出格式】 將計(jì)算出的最優(yōu)移動(dòng)方案輸出到文件hanoi.out。文件的每一行由一個(gè)正整數(shù)k和2個(gè)字符c1和c2組成，表示將第k個(gè)圓盤從塔座c1移到塔座c2上?！据斎霕永? 【輸出樣例】1 A B2 A C1 B C3 A B1 C A2 C B1 A B7、背包問題【問題描述】 簡(jiǎn)

18、單的背包問題。設(shè)有一個(gè)背包，可以放入的重量為s?，F(xiàn)有n件物品，重量分別為w1,w2，wn，（1in）均為正整數(shù)，從n件物品中挑選若干件，使得放入背包的重量之和正好為s。找到一組解即可。【輸入格式】 第一行是物品總件數(shù)和背包的載重量，第二行為各物品的重量?！据敵龈袷健?各所選物品重量?！据斎霕永? 101 2 3 4 5【輸出樣例】number:1 weight:1number:4 weight:4number:5 weight:58、2的冪次方（Noip1998）【問題描述】 任何一個(gè)正整數(shù)都可以用2的冪次方表示。例如： 137=27+23+20 同時(shí)約定方次用括號(hào)來表示，即ab 可表示為a

19、（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）【輸入格式】 正整數(shù)（n20000）【輸出格式】 符合約定的n的0，2表示（在表示中不能有空格）【輸入樣例】 137【輸出樣例】2(2(2)+2+2(0)+2(2+2(0)+2(0)9、數(shù)的計(jì)數(shù)（Noip2001）【問題描述】 我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n): 先輸入一個(gè)自然數(shù)n（n1000）, 然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理： 1不作任何處理； 2在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超過原數(shù)(輸入的n)的一半； 3加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止?！据斎霕永?6 滿足條件的數(shù)為 6 (此部分不必輸出) 16 26 126 36 1