算法與程序?qū)嵺`2(遞歸1)

1、算法與程序?qū)嵺`2習(xí) 題 解 答8遞歸1讓我們來看看計(jì)算n的階乘的計(jì)算機(jī)程序的寫法。在數(shù)學(xué)上，求n的階乘，有兩種表示方法：（1）n!=n*(n-1)*(n-2)*2*1（2）n!=n*(n-1)! （0！=1）這兩種表示方法實(shí)際上對(duì)應(yīng)到兩種不同的算法思想。在第（1）種表示方法中，求n!要反復(fù)把1、2、3、（n-2）、（n-1）和n累乘起來，是循環(huán)的思想，很直接地我們會(huì)用一個(gè)循環(huán)語句將n以下的數(shù)都乘起來: int n,m = 1; for(int i = 2; i <= n; i+) m *= i; printf(“%d 的階乘是%dn”, n, m); 在第（2）種表示方法中，求n！時(shí)需要

2、用到（n-1）！，所以可以用下面的方法來求n的階乘： int factorial(int n) if(n <= 0) return(-1); if(n = 1) return 1; else return n*factorial(n - 1); 上面這兩種實(shí)現(xiàn)方式體現(xiàn)了兩種不同的解決問題的思想方法。第一種通過一個(gè)循環(huán)語句來計(jì)算階乘，其前提是了解階乘的計(jì)算過程，并用語句把這個(gè)計(jì)算過程模擬出來。第二種解決問題的思想是不直接找到計(jì)算n的階乘的方法，而是試圖找到n的階乘和n-1的階乘的遞推關(guān)系，通過這種遞推關(guān)系把原來問題縮小成一個(gè)更小規(guī)模的同類問題，并延續(xù)這一縮小規(guī)模的過程，直到在某一規(guī)模上，問

3、題的解是已知的。這樣一種解決問題的思想我們稱為遞歸的思想。遞歸方法的總體思想是將待求解問題的解看作輸入變量x的函數(shù)f(x)，通過尋找函數(shù)g，使得f(x) = g(f(x-1)，并且已知f(0)的值，就可以通過f(0)和g求出f(x)的值。這樣一個(gè)思想也可以推廣到多個(gè)輸入變量x，y，z等，x-1也可以推廣到x - x1，只要遞歸朝著出口的方向走就可以了。用遞歸的方法可以求解具有遞推關(guān)系的問題，此外，還可以廣泛應(yīng)用在搜索領(lǐng)域和排列組合領(lǐng)域。CS801：猴子吃桃（來源：程序設(shè)計(jì)方法及在線實(shí)踐指導(dǎo)（王衍等） P263）問題描述：猴子第1天摘下若干個(gè)桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個(gè)。第2天又將

4、剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半另加一個(gè)。到第10天早上想再吃時(shí)，就只剩下一個(gè)桃子了。求第1天共摘了多少個(gè)桃子。分析：假設(shè)Ai為第i天吃完后剩下的桃子的個(gè)數(shù)，A0表示第一天共摘下的桃子，本題要求的是A0.有以下遞推式子：A0=2*（A1+1） A1：第1天吃完后剩下的桃子數(shù)A1=2*（A2+1） A2：第2天吃完后剩下的桃子數(shù)A8=2*（A9+1） A9：第9天吃完后剩下的桃子數(shù)A9=1以上遞推過程可分別用非遞歸思想（循環(huán)結(jié)構(gòu)）和遞歸思想實(shí)現(xiàn)。用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)：如果x1、x2表示前后兩天吃完剩下的桃子數(shù)，則有遞推關(guān)系：x1=（x2+1）*2。從第9天剩下1個(gè)桃

5、子，反復(fù)遞推9次，則可求第1天共摘下的桃子數(shù)。這里包含了反復(fù)的思想，可以用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)，代碼如下：#include <stdio.h>int main() int day,x1,x2; day=9; x2=1; while(day>0) x1=(x2+1)*2; x2=x1; day-; printf("total= %dn",x1); / system("pause"); return 0;用遞歸思想實(shí)現(xiàn)：前面所述的遞推關(guān)系也可以采用下面的方式描述。假設(shè)第n天吃完后剩下的桃子數(shù)為 A（n），第n+1天吃完后剩下的桃子數(shù)為A（n+1）

6、，則存在的遞推關(guān)系：A(n)=(A(n+1)+1)*2。這種遞推關(guān)系可以用遞歸函數(shù)實(shí)現(xiàn)，代碼如下：#include <stdio.h>int A(int n) if(n>=9) return 1; else return (2*(A(n+1)+1);int main() printf("total= %dn",A(0);/ system("pause"); return 0;CS802：最大公約數(shù)（來源：程序設(shè)計(jì)方法及在線實(shí)踐指導(dǎo)（王衍等） P265）問題描述：輸入兩個(gè)正整數(shù)，求其最大公約數(shù)。數(shù)論中有一個(gè)求最大公約數(shù)的算法稱為輾轉(zhuǎn)相除法

7、，又稱歐幾里德算法。其基本思想及執(zhí)行過程為（設(shè)m為兩正整數(shù)中較大者，n為較小者）：（1）令u=m,v=n；（2）取u對(duì)v的余數(shù)，即r=u%v，如果r的值為0，則此時(shí)v的值就是m和n的最大公約數(shù)，否則執(zhí)行第（3）步；（3）u=v，v=r，即u的值為v的值，而v的值為余數(shù)r。并轉(zhuǎn)向第（2）步。用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)，代碼如下：#include<stdio.h>int gcd(int u,int v) int r; while(r=u%v)!=0) u=v; v=r; return (v);int main() int m,n,t; printf("Please input two p

8、ositive integers:"); scanf("%d%d",&m,&n); if(m<n) t=m; m=n; n=t; printf("The great common divisor of these two integers is %dn",gcd(m,n);/ system("pause"); return 0;用遞歸思想實(shí)現(xiàn)：int gcd(int u,int v)if(u%v=0) return v;else return gcd(v,u%v);CS803：經(jīng)典的Hanoi(漢諾塔)

9、問題（來源：程序設(shè)計(jì)方法及在線實(shí)踐指導(dǎo)（王衍等） P267）問題描述：有一個(gè)漢諾塔，塔內(nèi)有A,B,C三個(gè)柱子。起初，A柱上有n個(gè)盤子，依次由大到小、從下往上堆放，要求將它們?nèi)恳频紺柱上；在移動(dòng)過程中可以利用B柱，但每次只能移到一個(gè)盤子，且必須使三個(gè)柱子上始終保持大盤在下，小盤在上的狀態(tài)。要求編程輸出移動(dòng)的步驟。分析：先分析盤子數(shù)量很少的情形。比如，當(dāng)n=2時(shí)，只有2個(gè)盤子，只需要3步就可以完成整個(gè)移動(dòng)操作。A>BA>CB>C又如，移動(dòng)3個(gè)盤子的情況，需要7步：A>CA>BC>BA>CB>AB>CA>C現(xiàn)在的問題是，當(dāng)A柱上有n個(gè)盤子

10、時(shí)，至少需要移動(dòng)多少步？現(xiàn)按如下思路進(jìn)行思考：將n個(gè)盤子從A柱移到C柱可以分解為以下3個(gè)步驟：（1）將A柱上n-1個(gè)盤子借助C柱先移到B柱上；（2）將A柱上剩下的1個(gè)盤子移到C柱上；（3）將B柱上的n-1個(gè)盤子借助A柱移到C柱上。而n-1個(gè)盤子的移動(dòng)又可以分解為兩次n-2個(gè)盤子的移動(dòng)和一次1個(gè)盤子的移動(dòng)。依次類推。設(shè)移動(dòng)n個(gè)盤子至少需要A(n)步，則存在遞推式子：A(n)=2*A(n-1)+1。這個(gè)遞推式子結(jié)束條件是：當(dāng)n=1時(shí)，只有一個(gè)盤子，只需一次移動(dòng)即可。因此移動(dòng)n個(gè)盤子至少需要：A(n)=2n-1步。這樣我們可以描述為：將n個(gè)盤子從one柱上借助two柱子移動(dòng)到three柱上。這樣，以

11、上3個(gè)步驟可以表示為：第（1）步：將n-1個(gè)盤子從one柱子上借助three柱子移動(dòng)到two柱子上；第（2）步：將one柱子上的盤子（只有一個(gè)）移動(dòng)到three柱子上；第（3）步：將n-1個(gè)盤子從two柱子上借助one柱子移動(dòng)到three柱子上。n個(gè)盤子的移動(dòng)分解成兩次n-1個(gè)盤子的移動(dòng)和一次1個(gè)盤子的移動(dòng)，因此可以用遞歸函數(shù)實(shí)現(xiàn)：（1）hanoi函數(shù)：函數(shù)調(diào)用hanoi(n,one,two,three)實(shí)現(xiàn)將n個(gè)盤子從one柱子上借助two柱子移到three柱子的過程。（2）move函數(shù)：函數(shù)調(diào)用move(x,y)實(shí)現(xiàn)把1個(gè)盤子從x柱子上移到y(tǒng)柱子上的過程。x和y代表A、B、C柱子之一，根據(jù)

12、不同情況分別以A、B、C代入。代碼如下：#include<stdio.h>int main() void hanoi(int m,char one,char two,char three); /函數(shù)聲明 int m; /盤子個(gè)數(shù) printf("input the number of disks:"); scanf("%d",&m); printf("The steps of moving %d disks:n",m); hanoi(m,'A','B','C'); /

13、調(diào)用hanoi函數(shù)實(shí)現(xiàn)將m個(gè)盤子從A柱移動(dòng)到C柱（借助B柱） return 0;/將n個(gè)盤子從one柱移到three柱（借助two柱）void hanoi(int n,char one,char two,char three) void move(char x,char y); /函數(shù)聲明 if(n=1) move(one,three); else hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); void move(char x,char y) /將1個(gè)盤子從x柱移動(dòng)到y(tǒng)柱 printf("%c

14、 -> %cn",x,y); *遞歸存在的問題*用遞歸思想的代價(jià)是十分巨大，它會(huì)消耗大量的內(nèi)存。對(duì)于Fibonacci數(shù)列，調(diào)用到第20項(xiàng)時(shí)，遞歸次數(shù)達(dá)到21891次。CS804：另一個(gè)Fibonacci數(shù)列（來源：ZOJ 2060，程序設(shè)計(jì)方法及在線實(shí)踐指導(dǎo)（王衍等） P272）問題描述：定義另外一個(gè)Fibonacci數(shù)列：F(0)=7,F(1)=11,F(n)=F(n-1)+F(n-2)，（n2）。輸入：輸入文件中包含多行，每行為一個(gè)整數(shù)n，n<1000000。輸出：對(duì)輸入文件中的每個(gè)整數(shù)n，如果F(n)能被3整除，輸出yes，否則輸出no。樣例輸入：0123樣例輸出

15、：nonoyesno解題分析：如果利用遞歸思想求Fibonacci數(shù)列的各項(xiàng)，本題中如果直接采用遞歸方法求F(n)對(duì)3取余得到的余數(shù)，則會(huì)超時(shí)。我們可以嘗試?yán)贸绦蜉敵銮?0項(xiàng)對(duì)3取余的結(jié)果：#include<stdio.h>int f(int n)if(n=0) return 1;else if(n=1) return2;else return (f(n-1)+f(n-2)%3;int main()for(int i=0;i<30;i+)printf(“%d”,f(i);前30項(xiàng)對(duì)3取余得到的余數(shù)分別為：1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 1 1 2

16、 0 2 2 1 0 1 1 2 0 2 2 1。分析這些余數(shù)，我們不難發(fā)現(xiàn)該Fibonacci數(shù)列各項(xiàng)對(duì)3取余的余數(shù)每8項(xiàng)構(gòu)成一個(gè)循環(huán)：1 2 0 2 2 1 0 1。如果我們把這8個(gè)余數(shù)存放到一個(gè)數(shù)組f0，對(duì)輸入的任意整數(shù)n，則有：f(n)%3=f0n%8。按照這種方法可以很快判斷f(n)是否能被3整除。參考程序：#include<stdio.h>int f(int n) if(n=0) return 1; else if(n=1) return 2; else return (f(n-1)+f(n-2)%3;int main() int f08; for(int i=0;i&

17、lt;8;i+) f0i=f(i); int n; while(scanf("%d",&n)!=EOF) if(f0n%8=0) printf("yesn"); else printf("non"); return 0;CS822：分形（Fractal）（來源：POJ 2083 ZOJ 2423，程序設(shè)計(jì)方法及在線實(shí)踐指導(dǎo)（王衍等） P274）問題描述：分形是存在“自相似”的一個(gè)物體或一種量，從某種技術(shù)角度來說，這種“自相似”是全方位的。盒形分形定義如下：度數(shù)為1的分形很簡單，為：X度數(shù)為2的分形為：X X XX X如果用B(

18、n-1)代表度數(shù)為n-1的盒形分形，則度數(shù)為n的盒形分形可以遞歸地定義為：B(n-1) B(n-1) B(n-1)B(n-1) B(n-1)你的任務(wù)是輸出度數(shù)為n的盒形分形。輸入：輸入文件包含多個(gè)測試數(shù)據(jù)，每個(gè)測試數(shù)據(jù)占一行，包含一個(gè)正整數(shù)n，n7。輸入文件的最后一行為-1，代表輸入結(jié)束輸出：對(duì)每個(gè)測試數(shù)據(jù)，用符號(hào)“X”表示輸出盒形分形。在每個(gè)測試數(shù)據(jù)對(duì)應(yīng)的輸出之后輸出一個(gè)短劃線符號(hào)“-”，在每行的末尾不要輸出任何多余的空格，否則得到的是“格式錯(cuò)誤”的結(jié)果。樣例輸入：123-1樣例輸出：X-X X XX X-X X X X X XX X X X X X X X XX X X X X XX X

19、X X-解題分析：首先注意到度數(shù)為n的盒形分形，其大小是3n-1*3n-1?？梢杂米址麛?shù)組來存儲(chǔ)盒形分形中各個(gè)字符。因?yàn)閚7，而36=729，因此可以定義一個(gè)字符數(shù)組Fractal730730來存儲(chǔ)度數(shù)不超過7的盒形分形。其次，度數(shù)為n的盒形分形可以由以下遞推式子表示： B(n-1) B(n-1)B(n)= B(n-1)B(n-1) B(n-1)因此，可以用一個(gè)遞歸函數(shù)來設(shè)置度數(shù)為n的盒形分形。假設(shè)需要在（startX,startY）位置開始設(shè)置度數(shù)為n的盒形分形，它由5個(gè)度數(shù)為n-1的盒形分形組成，其起始位置分別為：(startX+0,startY+0)、(startX+2*L0,start

20、Y+0)、(startX+L0,startY+L0)、(startX+0,startY+2*L0)和(startX+2*L0,startY+2*L0)，其中L0=3n-2。該遞歸函數(shù)的結(jié)束條件是：當(dāng)n=1時(shí)（即度數(shù)為1的盒形分形），只需要在(startX,startY)位置設(shè)置一個(gè)“X”字符。另外，題目中提到“在每行的末尾不要輸出任何多余的空格”，因此在字符數(shù)組Fractal每行最后一個(gè)“X”字符之后，應(yīng)該設(shè)置串結(jié)束符標(biāo)志0。參考程序：#include<stdio.h>#include<math.h>#define MAXSCALE 730 /n為最大值7，分形的大小是

21、36*36，而36=729/函數(shù)功能：從(startX,startY)位置開始設(shè)置度數(shù)為n的盒形分形 /即對(duì)盒形分形中的每個(gè)X，在字符數(shù)組Frac的相應(yīng) 位置設(shè)置字符"X" /其中第1個(gè)形參為一個(gè)二維數(shù)組名，其第2維不能省略 void SetFractal(char Frac730,int startX,int startY,int n) if(n=1) FracstartXstartY='X' else int L0=(int)pow(3,n-2); SetFractal(Frac,startX+0,startY+0,n-1); SetFractal(Frac,startX+2*L0,startY+0,n-1); Set