遞歸基礎練習題

1、遞歸基礎練習題1.求123……n的值2.求123……n的值3.數(shù)的全排列問題。將n個數(shù)字1，2，…n的所有排列按字典順序枚舉出來2312133123214.數(shù)的組合問題。從12…n中取出m個數(shù)，將所有組合按照字典順序列出。如n=3m=2時，輸出：1213239.求兩個數(shù)的最大公約數(shù)。10.求兩個數(shù)的最小公倍數(shù)。5.小猴子第一天摘下若干桃子當即吃掉一半又多吃一個.第二天早上又將剩下的桃子吃一半又多吃一個.以后每天早上吃前一天剩下的一半另一

2、個.到第10天早上猴子想再吃時發(fā)現(xiàn)只剩下一個桃子了.問第一天猴子共摘多少個桃子？8.著名的菲波拉契(Fibonacci)數(shù)列，其第一項為1，第二項為1，從第三項開始，其每一項都是前兩項的和。編程求出該數(shù)列前N項數(shù)據(jù)。15.梯有N階，上樓可以一步上一階，也可以一次上二階。編一個程序，計算共有多少種不同的走法。6.有雌雄一對兔子，假定過兩個月便可繁殖雌雄各一的一對小兔子。問過n個月后共有多少對兔子？7.一個人趕著鴨子去每個村莊賣，每經過一個

3、村子賣去所趕鴨子的一半又一只。這樣他經過了七個村子后還剩兩只鴨子，問他出發(fā)時共趕多少只鴨子？經過每個村子賣出多少只鴨子？11.輸入一個數(shù)，求這個數(shù)的各位數(shù)字之和。12.角谷定理。輸入一個自然數(shù)，若為偶數(shù)，則把它除以2，若為奇數(shù)，則把它乘以3加1。經過如此有限次運算后，總可以得到自然數(shù)值1。求經過多少次可得到自然數(shù)1。如：輸入22，輸出221134175226134020105168421STEP=1613.將十進制轉換為二進制。14.計

4、算M＝max(abc)[max(abbc)max(abbc)]其中a，b，c由鍵盤輸入。16.某人寫了n封信和n個信封，如果所有的信都裝錯了信封。求所有的信都裝錯信封共有多少種不同情況17.給出一棵二叉樹的中序與后序排列。求出它的先序排列。18.求把一個整數(shù)n無序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。19.已知一個一維數(shù)組A[1..N]。N50又已知一整數(shù)M。如能使數(shù)組A中任意幾個元素之和等于M，則輸出YES，反之則為NO。20.要

5、求找出具有下列性質的數(shù)的個數(shù)(包含輸入的自然數(shù)n)：先輸入一個自然數(shù)n(n=500)然后對此自然數(shù)按照如下方法進行處理:①.不作任何處理Frxk:integerProgramsearch(xtopbot:integer)Var:integerBeginiftop=botthenBegin=(topbot)div2Ifx=a[]thenwriteln(x:5:5’yes’)elseIfxa[]thensearch(xtop1)Elsese

6、arch(x1r)EndelseWriteln(x:5‘no’)EndBeginWriteln(‘inputngeshu’)Fk:=1tondoread(a[k])Read(x)F:=1r:=nSearch(xfr)End.2.hanoi塔問題。遞歸：procedureHanoi(n:integerxyz:)BeginIfn=1thenwriteln(x’’n’’z)ElsebeginHanoi(n1xzy)Writeln(x’’n’’

7、z)Hanoi(n1yxz)EndEndBeginWrite(‘inputn:’)Read(n)Hanoi(n’A’’B’’C’)End.3.有n個硬幣（n為偶數(shù)）正面朝上排成一排，每次將n1個硬幣翻成朝上為止。編程讓計算機把翻硬幣的最簡過程及翻幣次數(shù)打印出來（用代表正面，用0代表反面）?；拘问剑篋[1]=0d[2]=1遞歸式：d[n]=(n1)(d[n1]d[n2])varn:integerfunctiond(n:integer):