遞歸基礎練習題

1、遞歸基礎練習題1.  求1+2+3+n的值2.  求1*2*3*n的值3. 數(shù)的全排列問題。將n個數(shù)字1，2，n的所有排列按字典順序枚舉出來  2 3 1  2 1 3  3 1 2  3 2 14. 數(shù)的組合問題。從1,2,n中取出m個數(shù)，將所有組合按照字典順序列出。如n=3,m=2時，輸出：1 21 32 39.  求兩個數(shù)

2、的最大公約數(shù)。10.  求兩個數(shù)的最小公倍數(shù)。5. 小猴子第一天摘下若干桃子,當即吃掉一半,又多吃一個.第二天早上又將剩下的桃子吃一半,又多吃一個.以后每天早上吃前一天剩下的一半另一個.到第10天早上猴子想再吃時發(fā)現(xiàn),只剩下一個桃子了.問第一天猴子共摘多少個桃子？8.  著名的菲波拉契(Fibonacci)數(shù)列，其第一項為1，第二項為1，從第三項開始，其每一項都是前兩項的和。編程求出該數(shù)列前N項數(shù)據(jù)。15.  梯有N階，上樓可以一步上一階，也可以一次上二階。編一個程序，計算共有多少種不同的走法。6. 有雌雄一對兔子

3、，假定過兩個月便可繁殖雌雄各一的一對小兔子。問過n個月后共有多少對兔子？7.  一個人趕著鴨子去每個村莊賣，每經(jīng)過一個村子賣去所趕鴨子的一半又一只。這樣他經(jīng)過了七個村子后還剩兩只鴨子，問他出發(fā)時共趕多少只鴨子？經(jīng)過每個村子賣出多少只鴨子？11.  輸入一個數(shù)，求這個數(shù)的各位數(shù)字之和。12.  角谷定理。輸入一個自然數(shù)，若為偶數(shù)，則把它除以2，若為奇數(shù)，則把它乘以3加1。經(jīng)過如此有限次運算后，總可以得到自然數(shù)值1。求經(jīng)過多少次可得到自然數(shù)1。如：輸入22，輸出 22  11  34

4、60; 17  52  26  13  40  20  10  5  16  8  4  2  1     STEP=1613.  將十進制轉(zhuǎn)換為二進制。14.  計算Mmax(a,b,c)/max(a+b,b,c)*max(a,b,b+c),其中a，b，c由

5、鍵盤輸入。16.  某人寫了n封信和n個信封，如果所有的信都裝錯了信封。求所有的信都裝錯信封共有多少種不同情況?17.  給出一棵二叉樹的中序與后序排列。求出它的先序排列。18.  求把一個整數(shù)n無序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。19.  已知一個一維數(shù)組A1.N。N<50 又已知一整數(shù)M。如能使數(shù)組A中任意幾個元素之和等于M，則輸出YES，反之則為NO。20.  要求找出具有下列性質(zhì)的數(shù)的個數(shù)(包含輸入的自然數(shù)n)：先輸入一個自然數(shù)n(n<=500),然后對此

6、自然數(shù)按照如下方法進行處理:. 不作任何處理;. 在它的左邊加上一個自然數(shù),但該自然數(shù)不能超過原數(shù)首位數(shù)字的一半;. 加上數(shù)后,繼續(xù)按此規(guī)則進行處理,直到不能再加自然數(shù)為止.樣例:  輸入:  6滿足條件的數(shù)為   6                16       &

7、#160;        26               126                36         

8、      136輸出:  621.  自然數(shù)的拆分問題。給定自然數(shù)n,將其拆分成若干自然數(shù)的和。輸出所有解，每組解中數(shù)字按從小到大排列。相同數(shù)字的不同排列算一組解。如：3=1+1+13=1+23=322.  用遞歸的方法求N個數(shù)中最大的數(shù)及其位置。23.  寫出折半查找的遞歸算法。24.  快速排序法。思考題 :1、數(shù)學寶塔，從最頂上走到最底層，每次只能走到下一層的左邊或右邊的數(shù)字，求出使所走到的所有數(shù)字之和為60的途徑。7

9、466936371253285947 326418563397684152573578422、 漢諾塔問題：設有三個塔座，依次命名為x,y,z。有z個直徑不同的圓盤，由小到大依次編號為1、2、，n。開始時，它們?nèi)堪催f減的次序插在塔座上?，F(xiàn)要求按下列規(guī)則把n個圓盤按次序插放在z塔座上。（1）、每次只能移動一個圓盤；（2）、圓盤可以從任一個塔座上移到另一個塔座上；（3）、任何時刻都不能把一個較大的圓盤壓在較小的圓盤上。典型例題: 1.設有n個數(shù)已經(jīng)按從大到小的順序排列，現(xiàn)在從鍵盤上輸入n，判斷它是否在這n 個數(shù)中，如果存在則輸出“yes”否則輸出“no”。

10、   Program lx4;   Const n=30;   Var a:array1.nof integer;       F,r,x,k:integer;   Program search(x,top,bot:integer);     Var  mid:integer; 

11、         Begin             if top<=bot then               Begin      

12、60;          Mid=(top + bot) div 2;                 If x =amid then writeln(x:5,mid:5,yes)      

13、;            else  If x<amid then search(x,top,mid-1)                          

14、60;          Else search(x,mid+1,r);               End            else Writeln(x:5,no);   

15、       End;  Begin      Writeln(input n ge shu);     For k:=1 to n do read(ak);     Read(x);     F:=1;r:=n;

16、60;    Search(x,f,r);  End.2.hanoi塔問題。  遞歸：procedure Hanoi(n:integer;x,y,z:char);          Begin            If n=1 then writeln(x,

17、-n,-,z)                   Else  begin                          &#

18、160;Hanoi(n-1,x,z,y);                           Writeln(x,-,n,-,z);                &#

19、160;          Hanoi(n-1,y,x,z)                         End;          End;&#

20、160;       Begin           Write(input n:);           Read(n);           Hanoi(n,A,B,C) &#

21、160;      End.3.有n個硬幣（n為偶數(shù)）正面朝上排成一排，每次將n-1個硬幣翻成朝上為止。編程讓計算機把翻硬幣的最簡過程及翻幣次數(shù)打印出來（用*代表正面，用0代表反面）?；拘问剑篋1=0;d2=1遞歸式：dn= (n-1)*( dn-1 + dn-2)var n:integer;function d(n:integer):longint;begincase n of1:d:=0;2:d:=1;else d:=(n-1)*(d(n-

22、1)+d(n-2);end;end;beginrepeatwrite('n=');readln(n);if n<=0 then writeln('Once more!')until n>0;writeln('d=',d(n);readln;end.4.有一對雌雄兔子，假定兩個月便可以繁殖雌雄各一對兔子。問n個月后共有多少對兔子？遞歸的三要素：遞歸的形式：Tn= Tn-1+ Tn-2基本：T1=1，T2=1結束條件：n個月program rabbit;var

23、 n:integer;function fa(n:integer):integer;beginif n<3 then fa:=1else fa:=fa(n-1)+fa(n-2);end;beginwrite('n=');readln(n);writeln('The number of the rabbits:',fa(n);end.5.梯有N階，上樓可以一步上一價，也可以一次上二階。編一個程序，計算共有多少種不同的走法。遞歸的形式：sn=sn-1+sn-2基

24、本式子：s1=1;s2=2program upstairs;var n:integer;function s(n:integer):longint;beginif (n=1)or(n=2) then s:=nelse s:=s(n-1)+s(n-2);end;beginrepeatwrite('N=');readln(n);until n>0;writeln('s=',s(n);readln;end.6.斐波那切數(shù)列  遞歸：var m,p:int

25、eger;        Function fib(n:integer):integer;           Begin               If n=0 then fib:=0  

26、0;                  Else if n=1 then fib:=1                        

27、60;        Else fib:=fib(n-1)+fib(n-2);           End;        Begin           Read(m);   &

28、#160;       P:=fib(m);           Writeln(fib(,mm)=,p)         End.7.設有2n個運動員要進行網(wǎng)球比賽?，F(xiàn)要設計一個滿足以下要求的比賽日程表：（1）、每個選手必須與其他n-1個選手各賽一次；（2）、每個選手每天只能參賽一次；（3）、循環(huán)賽在n-1天內(nèi)結束。progr

29、am match;const k=3;n=8;vars:array1.n,1.n of integer;i,j,p:integer;ju:boolean;procedure copy1(be,en:integer;jug:boolean;q:integer);var m,t,ban:integer;beginif jug thenbeginif be=1 thenbegin if sen,en=0 thenbegin copy1(be,en di

30、v 2,true,q div 2);copy1(en div 2)+1,en,false,q div 2);end;for m:=1 to en dofor t:=1 to en dosm+q,t+q:=sm,tendelse begin if sbe+q-1,q=0 thenbegin copy1(be,be+(q div 2)-1,true,q div 

31、2);copy1(be+(q div 2),en,false,q div 2)end;for m:=be to en dofor t:=1 to q dosm+q,t+q:=sm,tendendelse beginif sbe,q=0 thenbegin copy1(be,be+(q div 2)-1,true,q div 2);copy1(be+(q div 2),en,fa

32、lse,q div 2)end;for m:=be to en dofor t:=1 to q dosm-q,t+q:=sm,tendend;beginp:=8;for i:=1 to n dofor j:=1 to n dosi,j:=0;for i:=1 to n dobeginsi,1:=i;if odd(i) then si+1,2:=si

33、,1else si-1,2:=si,1;end;copy1(1,n div 2,true,p div 2);copy1(n div 2)+1,n,false,p div 2);for i:=1 to n dobeginfor j:=1 to n dowrite(si,j,' ');writeln;end;end.以下是USACO contest上的題目，全是遞歸-*  &

34、#160;                        BRONZE PROBLEMS*                     

35、0;    三道題目，從11到13*Problem 11: 谷倉的安保 Traditional, 2005Farmer John給谷倉安裝了一個新的安全系統(tǒng)，并且要給牛群中的每一個奶牛安排一個有效的密碼。一個有效的密碼由L(3 <= L <= 15)個小寫字母(來自傳統(tǒng)的拉丁字母集'a'.'z')組成，至少有一個元音('a', 'e', 'i', 

36、;'o', 或者 'u')，至少兩個輔音(除去元音以外的音節(jié))，并且有按字母表順序出現(xiàn)的字母(例如，'abc'是有效的，而'bac'不是) 。給定一個期望長度L和C個小寫字母，寫一個程序，打印出所有的長度為L、能由這些字母組成的有效密碼。密碼必須按字母表順序打印出來，一行一個。題目名稱: passwd輸入格式:* 第一行: 兩個由空格分開的整數(shù)，L和C* 第二行: C個空格分開的小寫字母，密碼是由這個字母集中的字母來構建的。輸入樣例 (文件&

37、#160;passwd.in):4 6a t c i s w輸入詳細說明:由從給定的六個字母中選擇的、長度為4的密碼。輸出格式:* 第一至?行: 每一個輸出行包括一個長度為L個字符的密碼(沒有空格)。輸出行必須按照字母順序排列。輸出樣例 (文件 passwd.out):acisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistw*Problem 12: "跳房子" Hal Burch, 2005奶牛們按不太傳統(tǒng)的方式玩起了小孩子們玩的"跳房子"游戲。奶牛們創(chuàng)造了一個5x5的、由與x,y軸平行的數(shù)字組成的直線型網(wǎng)格，而不是用來在里面跳的、線性排列的、帶數(shù)字的方格。然后他們熟練地在網(wǎng)格中的數(shù)字中跳：向前跳、向后跳、向左跳、向右跳(從不斜過來跳)，跳到網(wǎng)格中的另一個數(shù)字上。他們再這樣跳啊跳(按相同規(guī)則)，跳到另外一個數(shù)字上(可能是已經(jīng)跳過的數(shù)字)。一共在網(wǎng)格內(nèi)跳過五次后，他們的跳躍構建了一個六位整數(shù)(可能以0開頭，例如000201)。求出所有能被這樣創(chuàng)造出來的不同整