遞歸基礎(chǔ)練習(xí)題求1+2+3+……+n的值求1*2*3**n的值3?數(shù)的全排列問題。將n個(gè)數(shù)字1,2,...n的所有排列按字典順序枚舉出來2312133123214?數(shù)的組合問題。從1,2,...,n中取出m個(gè)數(shù)，將所有組合按照字典順序列出。如n=3,m=2時(shí),輸出：121323求兩個(gè)數(shù)的最大公約數(shù)。求兩個(gè)數(shù)的最小公倍數(shù)。小猴子第一天摘下若干桃子,當(dāng)即吃掉一半,又多吃一個(gè).第二天早上又將剩下的桃子吃一半,又多吃一個(gè).以后每天早上吃前一天剩下的一半另一個(gè).到第10天早上猴子想再吃時(shí)發(fā)現(xiàn),只剩下一個(gè)桃子了.問第一天猴子共摘多少個(gè)桃子8?著名的菲波拉契(Fibonacci)數(shù)列，其第一項(xiàng)為1,第二項(xiàng)為1,從第三項(xiàng)開始，其每一項(xiàng)都是前兩項(xiàng)的和。編程求出該數(shù)列前N項(xiàng)數(shù)據(jù)。梯有N階，上樓可以一步上一階，也可以一次上二階。編一個(gè)程序，計(jì)算共有多少種不同的走法。有雌雄一對兔子，假定過兩個(gè)月便可繁殖雌雄各一的一對小兔子。問過n個(gè)月后共有多少對兔子一個(gè)人趕著鴨子去每個(gè)村莊賣，每經(jīng)過一個(gè)村子賣去所趕鴨子的一半又一只。這樣他經(jīng)過了七個(gè)村子后還剩兩只鴨子，問他出發(fā)時(shí)共趕多少只鴨子經(jīng)過每個(gè)村子賣出多少只鴨子輸入一個(gè)數(shù)，求這個(gè)數(shù)的各位數(shù)字之和。角谷定理。輸入一個(gè)自然數(shù)，若為偶數(shù)，則把它除以2，若為奇數(shù)，則把它乘以3加1。經(jīng)過如此有限次運(yùn)算后，總可以得到自然數(shù)值1。求經(jīng)過多少次可得到自然數(shù)1。如：輸入22，輸出168421STEP=16將十進(jìn)制轉(zhuǎn)換為二進(jìn)制。計(jì)算M=max(a,b,c)/[max(a+b,b,c)*max(a,b,b+c)],其中a,b,c由鍵盤輸入。某人寫了n封信和n個(gè)信封，如果所有的信都裝錯(cuò)了信封。求所有的信都裝錯(cuò)信封共有多少種不同情況給出一棵二叉樹的中序與后序排列。求出它的先序排列。18?求把一個(gè)整數(shù)n無序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。已知一個(gè)一維數(shù)組A[1..N]。｛N<50｝又已知一整數(shù)M。如能使數(shù)組A中任意幾個(gè)元素之和等于M,則輸出YES,反之則為NO。要求找出具有下列性質(zhì)的數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n)：先輸入一個(gè)自然數(shù)n(n<=500)，然后對此自然數(shù)按照如下方法進(jìn)行處理：?不作任何處理；.在它的左邊加上一個(gè)自然數(shù)/旦該自然數(shù)不能超過原數(shù)首位數(shù)字的一半；?加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理,直到不能再加自然數(shù)為止.樣例:輸入:6滿足條件的數(shù)為6162612636136輸出:6自然數(shù)的拆分問題。給定自然數(shù)n,將其拆分成若干自然數(shù)的和。輸出所有解，每組解中數(shù)字按從小到大排列。相同數(shù)字的不同排列算一組解。如：3=1+1+13=1+23=322?用遞歸的方法求N個(gè)數(shù)中最大的數(shù)及其位置。寫出折半查找的遞歸算法。快速排序法。思考題:1、數(shù)學(xué)寶塔，從最頂上走到最底層，每次只能走到下一層的左邊或右邊的數(shù)字，求出使所走到的所有數(shù)字之和為60的途徑。7466936371253285947326418563397684152573578422、漢諾塔問題：設(shè)有三個(gè)塔座，依次命名為x,y,z。有z個(gè)直徑不同的圓盤，由小到大依次編號為1、2n。開始時(shí)，它們?nèi)堪催f減的次序插在塔座上。現(xiàn)要求按下列規(guī)則把n個(gè)圓盤按次序插放在z塔座上。（1）、每次只能移動(dòng)一個(gè)圓盤；（2）、圓盤可以從任一個(gè)塔座上移到另一個(gè)塔座上；（3）、任何時(shí)刻都不能把一個(gè)較大的圓盤壓在較小的圓盤上。典型例題:1?設(shè)有n個(gè)數(shù)已經(jīng)按從大到小的順序排列，現(xiàn)在從鍵盤上輸入n，判斷它是否在這n個(gè)數(shù)中，如果存在則輸出"yes”否則輸出"no”。Programlx4;Constn=30;Vara:array[1..n]ofinteger;F,r,x,k:integer;Programsearch(x,top,bot:integer);Varmid:integer;Beginiftop<=botthenBeginMid=(top+bot)div2;Ifx=a[mid]thenwriteln(x:5,mid:5,'yes')elseIfx<a[mid]thensearch(x,top,mid1)Elsesearch(x,mid+1,r);EndelseWriteln(x:5,‘no');End;BeginWriteln(‘inputngeshu');Fork:=1tondoread(a[k]);Read(x);F:=1;r:=n;Search(x,f,r);End.塔問題。遞歸：procedureHanoi(n:integer;x,y,z:char);BeginIfn=1thenwriteln(x,''n,'',z)ElsebeginHanoi(n1,x,z,y);Writeln(x,'',n,'',z);Hanoi(n1,y,x,z)End;End;BeginWrite(‘inputn:');Read(n);Hanoi(n,'A','B','C')End.有n個(gè)硬幣(n為偶數(shù))正面朝上排成一排，每次將n1個(gè)硬幣翻成朝上為止。編程讓計(jì)算機(jī)把翻硬幣的最簡過程及翻幣次數(shù)打印出來(用*代表正面，用0代表反面)。基本形式：D[1]=0;d[2]=1遞歸式：d[n]=(n1)*(d[n1]+d[n2])varn:integer;functiond(n:integer):longint;begincasenof1:d:=0;2:d:=1;elsed:=(n1)*(d(n1)+d(n2));end;end;beginrepeatwrite('n=');readln(n);ifn<=0thenwriteln('Oncemore!')untiln>0;writeln('d=',d(n));readln;end.4?有一對雌雄兔子，假定兩個(gè)月便可以繁殖雌雄各一對兔子。問n個(gè)月后共有多少對兔子遞歸的三要素：遞歸的形式：T[n]=T[n1]+T[n2]基本：T[1]=1，T[2]=1結(jié)束條件：n個(gè)月programrabbit;varn:integer;functionfa(n:integer):integer;beginifn<3thenfa:=1elsefa:=fa(n1)+fa(n2);end;beginwrite('n=');readln(n);writeln('Thenumberoftherabbits:',fa(n));end.5?梯有N階，上樓可以一步上一價(jià)，也可以一次上二階。編一個(gè)程序，計(jì)算共有多少種不同的走法。遞歸的形式：s[n]=s[n1]+s[n2]基本式子：s[1]=1;s[2]=2programupstairs;varn:integer;functions(n:integer):longint;beginif(n=1)or(n=2)thens:=nelses:=s(n1)+s(n2);end;beginrepeatwrite('N=');readln(n);untiln>0;writeln('s=',s(n));readln;end.6.斐波那切數(shù)列遞歸：varm,p:integer;Functionfib(n:integer):integer;BeginIfn=0thenfib:=0Elseifn=1thenfib:=1Elsefib:=fib(n1)+fib(n2);End;BeginRead(m);P:=fib(m);Writeln(‘fib(',mm')=',p)End.7?設(shè)有25個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球比賽。現(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表:、每個(gè)選手必須與其他n1個(gè)選手各賽一次；、每個(gè)選手每天只能參賽一次；、循環(huán)賽在n1天內(nèi)結(jié)束。programmatch;constk=3;n=8;vars:array[1..n,1..n]ofinteger;i,j,p:integer;ju:boolean;procedurecopy1(be,en:integer;jug:boolean;q:integer);varm,t,ban:integer;beginifjugthenbeginifbe=1thenbeginifs[en,en]=0thenbegincopy1(be,endiv2,true,qdiv2);copy1((endiv2)+1,en,false,qdiv2);end;form:=1toendofort:=1toendos[m+q,t+q]:=s[m,t]endelsebeginifs[be+q1,q]=0thenbegincopy1(be,be+(qdiv2)1,true,qdiv2);copy1(be+(qdiv2),en,false,qdiv2)end;form:=betoendofort:=1toqdos[m+q,t+q]:=s[m,t]endendelsebeginifs[be,q]=0thenbegincopy1(be,be+(qdiv2)1,true,qdiv2);copy1(be+(qdiv2),en,false,qdiv2)end;form:=betoendofort:=1toqdos[mq,t+q]:=s[m,t]endend;beginp:=8;fori:=1tondoforj:=1tondos[i,j]:=0;fori:=1tondobegins[i,1]:=i;ifodd(i)thens[i+1,2]:=s[i,1]elses[i1,2]:=s[i,1];end;copy1(1,ndiv2,true,pdiv2);copy1((ndiv2)+1,n,false,pdiv2);fori:=1tondobeginforj:=1tondowrite(s[i,j],'');writeln;end;end.以下是USACOcontest上的題目，全是遞歸BRONZEPROBLEMS三道題目，從11到13Problemll:谷倉的安保[Traditional,2005]FarmerJohn給谷倉安裝了一個(gè)新的安全系統(tǒng)，并且要給牛群中的每一個(gè)奶牛安排一個(gè)有效的密碼。一個(gè)有效的密碼由L（3<=L<=15）個(gè)小寫字母（來自傳統(tǒng)的拉丁字母集'a'...'z'）組成，至少有一個(gè)元音（'a','e','i','o'，或者'u'），至少兩個(gè)輔音（除去元音以外的音節(jié)），并且有按字母表順序出現(xiàn)的字母（例如，'abc'是有效的，而'bac'不是）。給定一個(gè)期望長度L和C個(gè)小寫字母，寫一個(gè)程序，打印出所有的長度為L、能由這些字母組成的有效密碼。密碼必須按字母表順序打印出來，一行一個(gè)。題目名稱:passwd輸入格式:*第一行:兩個(gè)由空格分開的整數(shù)，L和C*第二行:C個(gè)空格分開的小寫字母，密碼是由這個(gè)字母集中的字母來構(gòu)建的。輸入樣例（文件:46atcisw輸入詳細(xì)說明:由從給定的六個(gè)字母中選擇的、長度為4的密碼。輸出格式:*第一至行:每一個(gè)輸出行包括一個(gè)長度為L個(gè)字符的密碼（沒有空格）。輸出行必須按照字母順序排列。輸出樣例（文件:acisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistwProblem12:"跳房子"[HalBurch,2005]奶牛們按不太傳統(tǒng)的方式玩起了小孩子們玩的"跳房子"游戲。奶牛們創(chuàng)造了一個(gè)5x5的、由與x,y軸平行的數(shù)字組成的直線型網(wǎng)格，而不是用來在里面跳的、線性排列的、帶數(shù)字的方格。然后他們熟練地在網(wǎng)格中的數(shù)字中跳：向前跳、向后跳、向左跳、向右跳（從不斜過來跳），跳到網(wǎng)格中的另一個(gè)數(shù)字上。他們再這樣跳啊跳（按相同規(guī)則），跳到另外一個(gè)數(shù)字上（可能是已經(jīng)跳過的數(shù)字）。一共在網(wǎng)格內(nèi)跳過五次后，他們的跳躍構(gòu)建了一個(gè)六位整數(shù)（可能以0開頭，例如000201）。求出所有能被這樣創(chuàng)造出來的不同整數(shù)的總數(shù)。問題名稱:numgrid輸入格式:*第1到5行:這樣的網(wǎng)格，一行5個(gè)整數(shù)輸入樣例（文件:1111111111111111112111111輸出格式:*第1行:能構(gòu)建的不同整數(shù)的總數(shù)輸出樣例（文件:15輸出詳細(xì)說明:111111,111112,111121,111211,111212,112111,112121,121111,121112,121211,121212,211111,211121,212111和212121能夠被構(gòu)建。沒有其它可能的數(shù)了。Problem13:衛(wèi)星照片[RobKolstad,2005]FarmerJohn給他的農(nóng)場買了WxH像素的衛(wèi)星照片（1<=W<=80,1<=H<=1000），希望找出最大的"連續(xù)的"（互相連接的）牧場。任何一對像素，一個(gè)像素如果能橫向的或縱向的與屬于這個(gè)牧場的另一個(gè)像素相連，這樣的牧場稱作是連續(xù)的（這句話太難翻了，大家將就著理解一下，看了后面的范例應(yīng)