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

1、函數(shù)的遞歸調(diào)用,長沙市一中岳麓中學信息學奧賽培訓,閱讀程序，分析結果：,#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，只有當整個函數(shù)體執(zhí)行完畢，這些局部變量才失去意義。每遞歸調(diào)用一次，就必須生成一組“新”的局部變量，雖然這些新的局部變量與原來的局部變量具有相同的名字，但其分配的存儲空間不同，其值也完全無關。,使用遞歸必須符合的條件：,（1）可以把這個問題轉化成一個新問題，而新問題的解法和原問題的解法完全相同，只是問題規(guī)模變小了（參數(shù)不同）；（2）必須要有一個明確的遞歸結束條件（遞歸邊界）。,

3、例1：求階乘（jc,1s,64MB）,問題分析：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;}思考：最后一行可否寫成：else return jc(n-1)*n;,例2：求最大公約數(shù)（gcd,1s,64MB）,問題分析：(

4、先使m>n)根據(jù)歐幾定理，發(fā)現(xiàn)(m,n)的最大公約數(shù)與(n,m%n)的最大公約數(shù)是一樣的，但是數(shù)據(jù)規(guī)模變小了。所以，最大公約數(shù)問題的遞歸公式為：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：分解質因子（zyz,1s,64MB）,問題描述：輸入一個正整數(shù)

5、n，用遞歸方法從小到大輸出它的所有質因子。輸入格式：一行一個正整數(shù)n，2<=n<=10000。輸出格式：一行若干個正整數(shù)，兩數(shù)之間用一個空格隔開，從小到大輸出。輸入樣例：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：抽獎（lottery2,1s,64MB）,公司舉辦年會，為了活躍氣氛，設置了搖獎環(huán)節(jié)。參加聚會的每位員工都有一張帶有號碼的抽獎券?，F(xiàn)在，主持人從小到大依次公布n個不同的獲獎號碼，小謝看著自己抽獎券上的號碼win，無比緊張。請編寫一個程序，如果小謝獲獎了，請輸出他中獎的是第幾個號碼；如果沒有中獎，請輸出0.輸入格式：第一行1個正整數(shù)n，表示有n個

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

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

9、，則n變成n/2；3）若n為大于1的奇數(shù)，則n變成n*3+1.請編程驗證此猜想。輸入格式：1行，一個正整數(shù)n，1<=n<=20000。輸出格式：若干行，每行表示一個操作，具體格式參見輸出樣例。,樣例輸入：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ù)的計算（count,1s,256MB）,問題描述：輸入一個自然數(shù)n，然后對此自然數(shù)按照如下方法處理：1）不做任何處理；2）在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半。3）加上數(shù)后繼續(xù)按此規(guī)則進行處理，直到不能再加自然數(shù)為止。請找出以上操作能得到的數(shù)的個數(shù)。例如，n=6時，滿足條件的數(shù)有6個，分別是6、16、26、126、36、136.輸入格式：一行，一個正