信息學(xué)奧賽課課通(c++)第6單元第5課函數(shù)的遞歸調(diào)用

1、函數(shù)的遞歸調(diào)用,長(zhǎng)沙市一中岳麓中學(xué)信息學(xué)奧賽培訓(xùn),閱讀程序，分析結(jié)果：,#include using namespace std;void p(int n){if(n>0){p(n-1);for(int i=0;i<n;i++)cout<<n;cout<<endl;}}int main(){p(5);return 0;},答案：122333444455555,遞歸函

2、數(shù)的局部變量：,遞歸函數(shù)通常帶有一些局部變量，如上例中的n，只有當(dāng)整個(gè)函數(shù)體執(zhí)行完畢，這些局部變量才失去意義。每遞歸調(diào)用一次，就必須生成一組“新”的局部變量，雖然這些新的局部變量與原來(lái)的局部變量具有相同的名字，但其分配的存儲(chǔ)空間不同，其值也完全無(wú)關(guān)。,使用遞歸必須符合的條件：,（1）可以把這個(gè)問(wèn)題轉(zhuǎn)化成一個(gè)新問(wèn)題，而新問(wèn)題的解法和原問(wèn)題的解法完全相同，只是問(wèn)題規(guī)模變小了（參數(shù)不同）；（2）必須要有一個(gè)明確的遞歸結(jié)束條件（遞歸邊界）。,

3、例1：求階乘（jc,1s,64MB）,問(wèn)題分析：jc(n)=1 (n=0或n=1)jc(n)=n*jc(n-1) (n>1)long long jc(int n){if(n==0||n==1) return 1;return jc(n-1)*n;}思考：最后一行可否寫(xiě)成：else return jc(n-1)*n;,例2：求最大公約數(shù)（gcd,1s,64MB）,問(wèn)題分析：(

4、先使m>n)根據(jù)歐幾定理，發(fā)現(xiàn)(m,n)的最大公約數(shù)與(n,m%n)的最大公約數(shù)是一樣的，但是數(shù)據(jù)規(guī)模變小了。所以，最大公約數(shù)問(wèn)題的遞歸公式為：gcd(m,n)=m (n=0)gcd(n,m%n) (n!=0)int gcd(int m,int n){if(n==0)return m;else return gcd(n,m%n);},例3：分解質(zhì)因子（zyz,1s,64MB）,問(wèn)題描述：輸入一個(gè)正整數(shù)

5、n，用遞歸方法從小到大輸出它的所有質(zhì)因子。輸入格式：一行一個(gè)正整數(shù)n，2<=n<=10000。輸出格式：一行若干個(gè)正整數(shù)，兩數(shù)之間用一個(gè)空格隔開(kāi)，從小到大輸出。輸入樣例：18輸出樣例：2 3 3,遞歸公式：,n=1 返回 輸出pzyz(n,p)= n%p=0 n>1 zyz(n/p,p)

6、 n%p!=0 zyz(n,p+1),,,,例4：抽獎(jiǎng)（lottery2,1s,64MB）,公司舉辦年會(huì)，為了活躍氣氛，設(shè)置了搖獎(jiǎng)環(huán)節(jié)。參加聚會(huì)的每位員工都有一張帶有號(hào)碼的抽獎(jiǎng)券。現(xiàn)在，主持人從小到大依次公布n個(gè)不同的獲獎(jiǎng)號(hào)碼，小謝看著自己抽獎(jiǎng)券上的號(hào)碼win，無(wú)比緊張。請(qǐng)編寫(xiě)一個(gè)程序，如果小謝獲獎(jiǎng)了，請(qǐng)輸出他中獎(jiǎng)的是第幾個(gè)號(hào)碼；如果沒(méi)有中獎(jiǎng)，請(qǐng)輸出0.輸入格式：第一行1個(gè)正整數(shù)n，表示有n個(gè)

7、獲獎(jiǎng)號(hào)碼，2<=n<=100.第二行包含n個(gè)正整數(shù)，之間用一個(gè)空格隔開(kāi)，表示依次公布的n個(gè)獲獎(jiǎng)號(hào)碼。第三行1個(gè)正整數(shù)win，表示小謝抽獎(jiǎng)券上的號(hào)碼。1<=獲獎(jiǎng)號(hào)碼,win<10000。輸出格式：一行一個(gè)整數(shù)，如果小謝中獎(jiǎng)了，請(qǐng)輸出中的是第幾個(gè)號(hào)碼；如果沒(méi)有中獎(jiǎng)，請(qǐng)輸出0.,思考1：走樓梯（stairs,1s,64MB）,問(wèn)題描述：已知一個(gè)樓梯有n級(jí)，小謝同學(xué)從下往上走，一步可以走一級(jí)，也可以走兩級(jí)。問(wèn)：

8、他走到第n級(jí)樓梯有多少種走法？要求用遞歸函數(shù)實(shí)現(xiàn)。輸入格式：一行，一個(gè)正整數(shù)n，1<=n<=40。輸出格式：一行，一個(gè)整數(shù)，表示走到第n級(jí)有多少種走法。輸入樣例：9輸出樣例：10,思考2：角谷猜想,問(wèn)題描述：角谷猜想是指對(duì)于每一個(gè)正整數(shù)，如果它是奇數(shù)，則對(duì)它乘3再加1；如果它是偶數(shù)，則對(duì)它除以2.如此循環(huán)，最終都能夠得到1.也就是說(shuō)，給定正整數(shù)n，要進(jìn)行如下操作：1）若n為1，操作結(jié)束；2）若n為偶數(shù)

9、，則n變成n/2；3）若n為大于1的奇數(shù)，則n變成n*3+1.請(qǐng)編程驗(yàn)證此猜想。輸入格式：1行，一個(gè)正整數(shù)n，1<=n<=20000。輸出格式：若干行，每行表示一個(gè)操作，具體格式參見(jiàn)輸出樣例。,樣例輸入：22樣例輸出：22/2=1111*3+1=3434/2=1717*3+1=5252/2=2626/2=1313*3+1=4040/2=2020/2=1010/2=55*3+1=1616

10、/2=88/2=44/2=22/2=1,思考3：數(shù)的計(jì)算（count,1s,256MB）,問(wèn)題描述：輸入一個(gè)自然數(shù)n，然后對(duì)此自然數(shù)按照如下方法處理：1）不做任何處理；2）在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超過(guò)原數(shù)的一半。3）加上數(shù)后繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止。請(qǐng)找出以上操作能得到的數(shù)的個(gè)數(shù)。例如，n=6時(shí)，滿(mǎn)足條件的數(shù)有6個(gè)，分別是6、16、26、126、36、136.輸入格式：一行，一個(gè)正