遞歸基礎(chǔ)練習(xí)題

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

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

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

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

5、求找出具有下列性質(zhì)的數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n)：先輸入一個(gè)自然數(shù)n(n=500)然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理:①.不作任何處理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塔問(wèn)題。遞歸：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個(gè)硬幣（n為偶數(shù)）正面朝上排成一排，每次將n1個(gè)硬幣翻成朝上為止。編程讓計(jì)算機(jī)把翻硬幣的最簡(jiǎn)過(guò)程及翻幣次數(shù)打印出來(lái)（用代表正面，用0代表反面）。基本形式：D[1]=0d[2]=1遞歸式：d[n]=(n1)(d[n1]d[n2])varn:integerfunctiond(n:integer):