C語言遞歸練習(xí)

1、die遞歸基礎(chǔ)練習(xí)題：求1+2+3+.+n的值mtsum(inta.iiitb)if(b=a)returna;retuina+sum(a+l,b);求1*2*3*n的值cheng(intbegin,intend)if(begin=end)retuinbegin;retuinbegm*cheng(begm+1,end);數(shù)的全排列問題。將n個數(shù)字1,2,n的所有排列按字典順序枚舉出猴2311312321數(shù)的組合問題。從1,2,.,n中取出m個數(shù)，將所有組合按照字典順序列出。如n=3,m=2時，輸出：21323小猴子第一天摘下若干桃子,當即吃掉一半，又多吃一個.第二天早上又將剩下的桃子吃一半，又多

2、吃一個.以后每天早上吃前一天剩下的一半另一個.到第10天早上猴子想再吃時發(fā)現(xiàn),只剩下一個桃子了.問第一天猴子共摘多少個桃子？fiuit(iiitbegin.mttimes)if(tiines=10)returnbegm;returnfruit(begin+l)*2,times+l);有雌雄一對兔子，假定過兩個月便可繁殖雌雄各一的一對小兔子。問過n個月后共有多少對兔子？一個人趕著鴨子去每個村莊賣，每經(jīng)過一個村子賣去所趕鴨子的一半又一只。這樣他經(jīng)過了七個村子后還剩兩只鴨子，問他出發(fā)時共趕多少只鴨子？經(jīng)過每個村子賣出多少只鴨子？duck(iiitbegin.mttimes)if(tiines=7)r

3、etuinbegin;retuinduck(begiii-r1)*2.tmies+1);8著名的菲波拉契(Fibonacci)數(shù)列，其第一項為0,第二項為1,從第三項開始，其每一項都是前兩項的和。編程求出該數(shù)列前N項數(shù)據(jù)。mtfbi(iiiti)if(i=0)return0;elseretuin1;returnfbi(i-l)+fbi(i2);求兩個數(shù)的最大公約數(shù)。fgongyue(mtm,intn)/m要kJn,前面可以交換讓它實現(xiàn)if(n=0)returnm;fgongyue(n,m%n);求兩個數(shù)的最小公倍數(shù)。最小公倍數(shù)等于2個數(shù)之枳乘最好公約數(shù)m*iizfgoiigyue(m.n)輸入

4、一個數(shù)，求這個數(shù)的各位數(shù)字之和。add_eveiy_nuni(mtnum)if(num10)returnnum;retiiinnum%10+add_every_num(nuni10);角谷定理。輸入一個自然數(shù)，若為偶數(shù)，則把它除以2,若為奇數(shù)，則把它乘以3加1。經(jīng)過如此有限次運算后，總可以得到自然數(shù)值1。求經(jīng)過多少次可得到自然數(shù)1。如：輸入22,輸出221134175226134020105168421STEP=16#includeHstdafx.hnincludeHstdio.hHiiiti=1;mtfc(intn)if(n=1)returni;elseif(n%2=0)elsefc(n*3

5、+l)；i+；mtaigc,char*argv)intn.step;printHPleasemputthenum:M);scanfC%dt&ii);step=fc(n);printf(MnStep=%d,n,step);return0;將十進制轉(zhuǎn)換為二進制。#includeHstdafx.hnincludeHstdio.hMmtfc(intnum)prmtf(H%dH,nuni);return0;fc(nunV2);pmitf(”d=nun%2);mtaigc,char*argv)7intnum;printHpleasemputthenum:M);scanf(H%d,&num);fc(num)

6、;pmitffE);return0;計算M=niax(a,b,c)/max(a+b,b,c)*max(a,b,b+c),其中a,b,c由鍵盤輸入。skip梯有N階，上樓可以一步上一階，也可以一次上二階。編一個程序，計算共有多少種不同的走法。returnl+(fc(n-l)+fc(n-2)某人寫了n封信和n個信封，如果所有的信都裝錯了信封。求所有的信都裝錯信封共有多少種不同情況？給出一棵二叉樹的中序與后序排列。求出它的先序排列。求把一個整數(shù)n無序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。已知一個一維數(shù)組Al.NoN50又已知一整數(shù)M。如能使數(shù)組A中任意幾個元素之和等于M,則輸出YES,反之則為N

7、O。要求找出具有卞列性質(zhì)的數(shù)的個數(shù)(包含輸入的自然數(shù)n)：先輸入一個自然數(shù)n(n=500),然后對此自然數(shù)按照如下方法進行處理：.不作任何處理；.在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)首位數(shù)字的一半；.加上數(shù)后，繼續(xù)按此規(guī)則進行處理,直到不能再加自然數(shù)為止.樣例：輸入：6滿足條件的數(shù)為6162612636136輸出：6自然數(shù)的拆分問題。給定自然數(shù)11,將其拆分成若干自然數(shù)的和。輸出所有解，每組解中數(shù)字按從小到大排列。相同數(shù)字的不同排列算一組解。女口：3=1+1+13=1+23=3用遞歸的方法求N個數(shù)中最大的數(shù)及其位置。寫出折半查找的遞歸算法?？焖倥判蚍?。思考題：1、數(shù)學(xué)寶塔，從最頂上

8、走到最底層，每次只能走到卞一層的左邊或右邊的數(shù)字，求出使所走到的所有數(shù)字之和為60的途徑。TOC o 1-5 h z6693637153289473241856397684152573578422、漢諾塔問題：設(shè)有三個塔座,編號為1、2、,1U開始時,依次命名為xyz。有z個直徑不同的圓盤，由小到人依次它們?nèi)堪催f減的次序插在塔座上?，F(xiàn)要求按下列規(guī)則把n個圓盤按次序插放在z塔座上。（1）、每次只能移動一個圓盤；（2）、圓盤可以從任一個塔座上移到另一個塔座上;（3）、任何時刻都不能把一個較人的圓盤壓在較小的圓盤上。典型例題：1設(shè)有n個數(shù)已經(jīng)按從人到小的順序排列，現(xiàn)在從鍵盤上輸入n,判斷它是否在這

9、n個數(shù)中,如果存在則輸出“yes”否則輸出“no”。Program1x4;Constn=30;Vaia:arrayl.nofinteger;Fj,x.k:integer;Programsearch(x.top,bot:integer);Varimd:mteger;Begmiftop=botthenBeginMid=(top+bot)div2;Ifx=anudthenTiteln(x:5.mid:5/yes)elseIfxanndtliensearch(x.top4iiid-1)Elsesearch(xjiiid+lj)；EndelseWriteln(x:5/no,);End;BeginWrit

10、elii(cinputngeshu，);Fork:=ltondoread(ak);Read(x);F:=l;r:=n;Search(x.fr);End.Hanoi塔問題。遞iJH:procedureHanoi(n:integer;x,y,z:char);BegmIfn=lthenwritelii(x一5一z)ElsebeginHanoi(n-l?x,z,y);Wntelii(x；-n；z);Hanoi(n-l,y,x,z)End;End;BeginWriteCmputn/);Read(n);Haiioi(n；A,B,；C,)End.有n個硬幣(n為偶數(shù))正面朝上排成一排，每次將ml個硬幣翻成朝

11、上為止。編程讓計算機把翻硬幣的最簡過程及翻幣次數(shù)打印出來(用*代表正面，用0代表反面)。基本形式：Dl=0;d2=l遞歸式：dn=(n-l)*(dn-l+dn-2)varn:integer;fiinctiond(n:integer):longint;begmcasenofl:d:=0;2:d:=l;elsed:=(n-1)*(d(n-l)+d(n-2);end;end;beginrepeatwrite(,n=,);readlii(n);ifn0;wntelii(rd=d(n);readhi;end.有一對雌雄兔子，假定兩個月便可以繁殖雌雄各一對兔子。問n各月后共有多少對兔子？遞歸的三要素：遞歸

12、的形式：Tn=Tn-l+Tn-2基本：Tl=l,T2=l結(jié)束條件：n個月programrabbit;varn:integer;fiinctionfa(n:mtegei):integer;begmifn0;wntelii(rs=s(n);readlii;end斐波那切數(shù)列遞歸：vaim,p:integer;Functionfib(n:integer):integer;BegmIfn=0thenfib:=OElseifn=lthenfib:=lElsefib:=fib(n-1)+fib(n-2);End;BeginRead(m);P:=fib(m);WritelnCfib(niinJ)=p)End

13、.設(shè)有2-n個運動員要進行網(wǎng)球比賽?，F(xiàn)要設(shè)計一個滿足以卞要求的比賽口程表：、每個選手必須與其他ml個選手各賽一次；、每個選手每天只能參賽一次；、循壞賽在ml天內(nèi)結(jié)束。programmatch;constk=3;n=8;vars:array1.n,l.nofinteger;ij,p:mteger;ju:boolean;procedurecopyl(be,en:mteger;jug:boolean;q:integer);varm.t,ban:integer;begmifjugthenbeginifbe=lthenbegmifsen,en=0thenbegincopvl(be,endiv2,true

14、.qdiv2);copyl(endiv2)+l,en,false,qdiv2);end;form:=ltoendofort:=ltoendosm+qj+q:=sm,tendelsebeginifsbe+q-l,q=0thenbegincopyl(be,be+(qdiv2)-1,true,qdiv2);copyl(be+(qdiv2),eiLfalse.qdiv2)form:=betoendofort:=ltoqdosm-rq.Hq：=smjendendelsebeginifsbe.q=0thenbegincopyl(be,be+(qdiv2)-lJiue,qdiv2);copyl(be+(qd

15、iv2),en,false,qdiv2)end;form:=betoendofort:=ltoqdosm-qj+q:=sm,tendend;begmfori:=ltondofbij:=ltondosij：=0；fori:=ltondobegmifodd(i)thensi+l,2:=sijelsesi-l,2:=si,l;end;copy1(Lndiv2jme,pdiv2);copyl(ndiv2)+l,n,false,pdiv2);fori:=ltondobeginfbij:=ltondownte(si,j；)；wiitelii;end;end.以下是USACOcontest上的題目,全是遞歸

16、*BRONZEPROBLEMS*三道題目，從11到13*Problem11:谷倉的安保Traditional,2005FarmerJolm給谷倉安裝了一個新的安全系統(tǒng)，并且要給牛群中的每一個奶牛安排一個有效的密碼。一個有效的密碼由L（3=L=15）個小寫字母（來自傳統(tǒng)的拉丁字母集W.N）組成，至少有一個元音（h,e,T,O,或者W）,至少兩個輔音（除去元音以外的音節(jié)），并且有按字母表順序出現(xiàn)的字母（例如，是有效的，而Sc，不是）。給定一個期望長度L和C個小寫字母，寫一個程序，打印出所有的長度為L、能由這些字母組成的有效密碼。密碼必須按字母表順序打印出來，一行一個。題目名稱:passwd輸入格式

17、：*第一行：兩個由空格分開的整數(shù)，L和C*第二行:C個空格分開的小寫字母，密碼是由這個字母集中的字母來構(gòu)建的。輸入樣例（文件passwd.m）:46atcisw輸入詳細說明：由從給定的六個字母中選擇的、長度為4的密碼。輸出格式：*第一至?行:每一個輸出行包括一個長度為L個字符的密碼（沒有空格）。輸出行必須按照字母順序排列。輸出樣例（文件passwd.out）:acisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistw*Problem12:“跳房子HalBurch,2005奶牛們按不太傳統(tǒng)的方式玩起了小孩子們玩的”跳房子”游戲。奶牛們創(chuàng)造了一

18、個5x5的、由與x,y軸平行的數(shù)字組成的直線型網(wǎng)格，而不是用來在里面跳的、線性排列的、帶數(shù)字的方格。然后他們熟練地在網(wǎng)格中的數(shù)字中跳：向前跳、向后跳、向左跳、向右跳（從不斜過來跳），跳到網(wǎng)格中的另一個數(shù)字上。他們再這樣跳啊跳（按相同規(guī)則），跳到另外一個數(shù)字上（可能是已經(jīng)跳過的數(shù)字）。一共在網(wǎng)格內(nèi)跳過五次后，他們的跳躍構(gòu)建了一個六位整數(shù)（可能以0開頭，例如000201）。求出所有能被這樣創(chuàng)造出來的不同整數(shù)的總數(shù)。問題名稱:numgnd輸入格式：*第1到5行:這樣的網(wǎng)格，一行5個整數(shù)輸入樣例（文件numgud.in）:1111111111111111112111111輸出格式：*第1行：能構(gòu)建的不同整數(shù)的