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

1、遞歸根底練習(xí)題1. 求 1+2+3+ +n的值2. 求1*2*3*n的值3. 數(shù)的全排列問(wèn)題。將 n個(gè)數(shù)字1, 2,n的所有排列按字典順序枚舉出來(lái)2 3 12 1 33 1 23 2 14. 數(shù)的組合問(wèn)題。從1,2,，中取出m個(gè)數(shù)，將所有組合按照字典順序列出。如 n=3,m=2 時(shí)，輸出：1 21 32 39. 求兩個(gè)數(shù)的最大公約數(shù)。10. 求兩個(gè)數(shù)的最小公倍數(shù)。5. 小猴子第一天摘下假設(shè)干桃子,當(dāng)即吃掉一半 ,又多吃一個(gè) .第二天早上又將剩下的桃子吃一半,又多吃一個(gè) .以后每天早上吃前一天剩下的一半另一個(gè).到第 10 天早上猴子想再吃時(shí)發(fā)現(xiàn),只剩下一個(gè)桃子了 .問(wèn)第一天猴子共摘多少個(gè)桃子？8

2、.著名的菲波拉契(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è)村子賣去所趕鴨子的一半又一只。這樣他經(jīng) 過(guò)了七個(gè)村子后還剩兩只鴨子,問(wèn)他出發(fā)時(shí)共趕多少只鴨子？經(jīng)過(guò)每個(gè)村子賣出多少只鴨 子？11. 輸入一個(gè)數(shù),求這個(gè)數(shù)的各位數(shù)字之和。12. 角谷定理。輸入一個(gè)自然數(shù),假設(shè)為偶數(shù),那

3、么把它除以2,假設(shè)為奇數(shù),那么把它乘以 3加 1。經(jīng)過(guò)如此有限次運(yùn)算后,總可以得到自然數(shù)值 1。求經(jīng)過(guò)多少次可得到自然數(shù) 1。 如：輸入 22,輸出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1STEP=1613. 將十進(jìn)制轉(zhuǎn)換為二進(jìn)制。14. 計(jì)算 M = max(a,b,c)/max(a+b,b,c)*max(a,b,b+c),其中 a, b, c 由鍵盤輸入。16. 某人寫(xiě)了 n 封信和 n 個(gè)信封,如果所有的信都裝錯(cuò)了信封。求所有的信都裝錯(cuò)信封共有 多少種不同情況 ?17. 給出一棵二叉樹(shù)的中序與后序排列。求出它的先序排列。18. 求把一個(gè)整數(shù)

4、n 無(wú)序劃分成 k 份互不相同的正整數(shù)之和的方法總數(shù)。19. 一個(gè)一維數(shù)組 A1.N。N<50又一整數(shù) M。如能使數(shù)組A中任意幾個(gè)元素之 和等于M,那么輸出YES，反之那么為NO。20. 要求找出具有以下性質(zhì)的數(shù)的個(gè)數(shù)(包含輸入的自然數(shù) n)：先輸入一個(gè)自然數(shù) n(n<=500), 然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理 : . 不作任何處理 ; . 在它的左邊加上一個(gè)自然數(shù) ,但該自然數(shù)不能超過(guò)原數(shù)首位數(shù)字的一半; . 加上數(shù)后 ,繼續(xù)按此規(guī)那么進(jìn)行處理 ,直到不能再加自然數(shù)為止 . 樣例 : 輸入 : 6滿足條件的數(shù)為 6162612636136輸出 : 621. 自然數(shù)的拆分問(wèn)題

5、。給定自然數(shù)n,將其拆分成假設(shè)干自然數(shù)的和。輸出所有解，每組解中數(shù)字按從小到大排列。相同數(shù)字的不同排列算一組解。如：3=1+1+13=1+23=322. 用遞歸的方法求 N 個(gè)數(shù)中最大的數(shù)及其位置。23. 寫(xiě)出折半查找的遞歸算法。24. 快速排序法。思考題60 的途徑。1、數(shù)學(xué)寶塔，從最頂上走到最底層，每次只能走到下一層的左邊或右邊的數(shù)字，求出使所 走到的所有數(shù)字之和為75639 252、漢諾塔問(wèn)題：設(shè)有三個(gè)塔座，依次命名為x,y,z。有z個(gè)直徑不同的圓盤，由小到大依次編號(hào)為1、2、,n。開(kāi)始時(shí)，它們?nèi)堪催f減的次序插在塔座上?，F(xiàn)要求按以下規(guī)那么把n個(gè)圓盤按次序插放在 z塔座上。1、每次只能移

6、動(dòng)一個(gè)圓盤；2、圓盤可以從任一個(gè)塔座上移到另一個(gè)塔座上；3、任何時(shí)刻都不能把一個(gè)較大的圓盤壓在較小的圓盤上。典型例題 :1設(shè)有n個(gè)數(shù)已經(jīng)按從大到小的順序排列，現(xiàn)在從鍵盤上輸入 n,判斷它是否在這n個(gè)數(shù)中,如果存在那么輸出“ yes否那么輸出“noProgram lx4;Const n=30;Var a:array1.nof integer;F,r,x,k:integer;Program search(x,top,bot:integer);Var mid:integer;Beginif top<=bot thenBeginMid=(top + bot) div 2;If x =amid t

7、hen writeln(x:5,mid:5,' yes ')else If x<amid then search(x,top,mid-1) Else search(x,mid+1,r);Endelse Writeln(x:5, no' );End;BeginWriteln( innpugte shu' );For k:=1 to n do read(ak);Read(x);F:=1;r:=n; Search(x,f,r);End.2.hanoi 塔問(wèn)題。 遞歸： procedure Hanoi(n:integer;x,y,z:char);BeginIf n

8、=1 then writeln(x, - ''n-,- ' ,z)Else begin Hanoi(n-1,x,z,y); Writeln(x, - ' ,n-,- ' ,z); Hanoi(n-1,y,x,z)End;End;BeginWrite( inpnu:t' );Read(n);Hanoi(n, 'A', 'B', 'C')End.3. 有 n 個(gè)硬幣 n 為偶數(shù)正面朝上排成一排，每次將n-1 個(gè)硬幣翻成朝上為止。編程讓電腦把翻硬幣的最簡(jiǎn)過(guò)程及翻幣次數(shù)打印出來(lái)用*代表正面，用 0 代表反面

9、。根本形式： D1=0;d2=1遞歸式： dn= (n-1)*( dn-1 + dn-2)var n:integer;function d(n:integer):longint;begin case n of1:d:=0;2:d:=1;else d:=(n-1)*(d(n-1)+d(n-2);end;end;beginrepeat write('n='); readln(n);if n<=0 then writeln('Once more!')until n>0;writeln('d=',d(n);readln;end.4. 有一對(duì)雌

10、雄兔子，假定兩個(gè)月便可以繁殖雌雄各一對(duì)兔子。問(wèn)n 個(gè)月后共有多少對(duì)兔子？遞歸的三要素：遞歸的形式： Tn= Tn-1+ Tn-2 根本： T1=1 ，T2=1 結(jié)束條件： n 個(gè)月 program rabbit;var 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. 梯有

11、 N 階，上樓可以一步上一價(jià)，也可以一次上二階。編一個(gè)程序，計(jì)算共有多少種不同 的走法。遞歸的形式： sn=sn-1+sn-2 根本式子： s1=1;s2=2 program 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;beginrepeat write('N=');readln(n); until n>0;writeln('s=',s(n);readln;end.遞歸： var m,

12、p:integer;Function fib(n:integer):integer;BeginIf n=0 then fib:=0Else if n=1 then fib:=1Else fib:=fib(n-1)+fib(n-2);End;BeginRead(m);P:=fib(m);Writeln( fib( ' ,mm' )= ' ,p)End.7設(shè)有2An個(gè)運(yùn)發(fā)動(dòng)要進(jìn)行網(wǎng)球比賽?，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表: 1、每個(gè)選手必須與其他n-1 個(gè)選手各賽一次；2、每個(gè)選手每天只能參賽一次；3、循環(huán)賽在 n-1 天內(nèi)結(jié)束。 program match;const

13、 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 then begin if sen,en=0 thenbegin copy1(be,en div 2,true,q div 2); copy1(en div 2)+1,en,false,q div 2);end;for m:=1 to en dofor t:=1 t

14、o en do sm+q,t+q:=sm,t endelse begin if sbe+q-1,q=0 thenbegin copy1(be,be+(q div 2)-1,true,q div 2);copy1(be+(q div 2),en,false,q div 2)end;for m:=be to en dofor t:=1 to q do sm+q,t+q:=sm,t end end else begin if sbe,q=0 then begin copy1(be,be+(q div 2)-1,true,q div 2); copy1(be+(q div 2),en,false,q

15、div 2) end;for m:=be to en dofor t:=1 to q do sm-q,t+q:=sm,t end end;beginp:=8;for i:=1 to n dofor j:=1 to n do si,j:=0;for i:=1 to n dobeginsi,1:=i;if odd(i) then si+1,2:=si,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 dow

16、rite(si,j,' '); writeln; end;end.以下是 USACO contest 上的題目，全是遞歸*BRONZE PROBLEMS*三道題目，從 11 到 13*Problem 11: 谷倉(cāng)的安保 Traditional, 2005 Farmer John 給谷倉(cāng)安裝了一個(gè)新的平安系統(tǒng)，并且要給牛群中的每一個(gè)奶牛安排一個(gè)有效 的密碼。一個(gè)有效的密碼由 L3 <= L <= 15 個(gè)小寫(xiě)字母 來(lái)自傳統(tǒng)的拉丁字母集 'a'.'z' 組成， 至少有一個(gè)元音'a', 'e', 'i

17、', 'o',或者u'，至少兩個(gè)輔音除去元音以外的音節(jié)，并且有按字母 表順序出現(xiàn)的字母例如，abc'是有效的，而bac'不是。給定一個(gè)期望長(zhǎng)度L和C個(gè)小寫(xiě)字母，寫(xiě)一個(gè)程序，打印出所有的長(zhǎng)度為L(zhǎng)、能由這些字母組成的有效密碼。密碼必須按字母表順序打印出來(lái)，一行一個(gè)。題目名稱 : passwd 輸入格式 :* 第一行 : 兩個(gè)由空格分開(kāi)的整數(shù)， L 和 C* 第二行 : C 個(gè)空格分開(kāi)的小寫(xiě)字母，密碼是由這個(gè)字母集中的字母來(lái)構(gòu)建的。 輸入樣例 文件 passwd.in:4 6a t c i s w 輸入詳細(xì)說(shuō)明 : 由從給定的六個(gè)字母中選擇的、長(zhǎng)度為

18、4 的密碼。輸出格式 :* 第一至 ?行: 每一個(gè)輸出行包括一個(gè)長(zhǎng)度為L(zhǎng) 個(gè)字符的密碼 沒(méi)有空格 。輸出行必須按照字母順序排列。輸出樣例 文件 passwd.out:acis acit aciw acst acsw actw aist aisw aitw astw cist cisw citw istw*Problem 12: "跳房子" Hal Burch, 2005 奶牛們按不太傳統(tǒng)的方式玩起了小孩子們玩的"跳房子 "游戲。奶牛們創(chuàng)造了一個(gè) 5x5 的、由與 x,y 軸平行的數(shù)字組成的直線型網(wǎng)格，而不是用來(lái)在里面跳 的、線性排列的、帶數(shù)字的方格。然后

19、他們熟練地在網(wǎng)格中的數(shù)字中跳：向前跳、向后跳、向左跳、向右跳 從不斜過(guò)來(lái)跳 ，跳到網(wǎng)格中的另一個(gè)數(shù)字上。他們?cè)龠@樣跳啊跳 按相同規(guī) 那么，跳到另外一個(gè)數(shù)字上 可能是已經(jīng)跳過(guò)的數(shù)字 。一共在網(wǎng)格內(nèi)跳過(guò)五次后，他們的跳躍構(gòu)建了一個(gè)六位整數(shù) 可能以 0 開(kāi)頭， 例如 000201 。求出所有能被這樣創(chuàng)造出來(lái)的不同整數(shù)的總數(shù)。 問(wèn)題名稱 : numgrid 輸入格式 :* 第 1到 5行: 這樣的網(wǎng)格，一行 5個(gè)整數(shù) 輸入樣例 文件 numgrid.in:1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 2 11 1 1 1 1 輸出格式 :* 第 1行: 能構(gòu)建的不同整數(shù)的總數(shù) 輸出樣例 文件 numgrid.out:15 輸出詳細(xì)說(shuō)明 :111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112,12121