遞歸基礎練習題求1+2+3+……+n的值求1*2*3**n的值3?數的全排列問題。將n個數字1,2,...n的所有排列按字典順序枚舉出來2312133123214?數的組合問題。從1,2,...,n中取出m個數，將所有組合按照字典順序列出。如n=3,m=2時,輸出：121323求兩個數的最大公約數。求兩個數的最小公倍數。小猴子第一天摘下若干桃子,當即吃掉一半,又多吃一個.第二天早上又將剩下的桃子吃一半,又多吃一個.以后每天早上吃前一天剩下的一半另一個.到第10天早上猴子想再吃時發現,只剩下一個桃子了.問第一天猴子共摘多少個桃子8?著名的菲波拉契(Fibonacci)數列，其第一項為1,第二項為1,從第三項開始，其每一項都是前兩項的和。編程求出該數列前N項數據。梯有N階，上樓可以一步上一階，也可以一次上二階。編一個程序，計算共有多少種不同的走法。有雌雄一對兔子，假定過兩個月便可繁殖雌雄各一的一對小兔子。問過n個月后共有多少對兔子一個人趕著鴨子去每個村莊賣，每經過一個村子賣去所趕鴨子的一半又一只。這樣他經過了七個村子后還剩兩只鴨子，問他出發時共趕多少只鴨子經過每個村子賣出多少只鴨子輸入一個數，求這個數的各位數字之和。角谷定理。輸入一個自然數，若為偶數，則把它除以2，若為奇數，則把它乘以3加1。經過如此有限次運算后，總可以得到自然數值1。求經過多少次可得到自然數1。如：輸入22，輸出168421STEP=16將十進制轉換為二進制。計算M=max(a,b,c)/[max(a+b,b,c)*max(a,b,b+c)],其中a,b,c由鍵盤輸入。某人寫了n封信和n個信封，如果所有的信都裝錯了信封。求所有的信都裝錯信封共有多少種不同情況給出一棵二叉樹的中序與后序排列。求出它的先序排列。18?求把一個整數n無序劃分成k份互不相同的正整數之和的方法總數。已知一個一維數組A[1..N]。｛N<50｝又已知一整數M。如能使數組A中任意幾個元素之和等于M,則輸出YES,反之則為NO。要求找出具有下列性質的數的個數(包含輸入的自然數n)：先輸入一個自然數n(n<=500)，然后對此自然數按照如下方法進行處理：?不作任何處理；.在它的左邊加上一個自然數/旦該自然數不能超過原數首位數字的一半；?加上數后，繼續按此規則進行處理,直到不能再加自然數為止.樣例:輸入:6滿足條件的數為6162612636136輸出:6自然數的拆分問題。給定自然數n,將其拆分成若干自然數的和。輸出所有解，每組解中數字按從小到大排列。相同數字的不同排列算一組解。如：3=1+1+13=1+23=322?用遞歸的方法求N個數中最大的數及其位置。寫出折半查找的遞歸算法。快速排序法。思考題:1、數學寶塔，從最頂上走到最底層，每次只能走到下一層的左邊或右邊的數字，求出使所走到的所有數字之和為60的途徑。7466936371253285947326418563397684152573578422、漢諾塔問題：設有三個塔座，依次命名為x,y,z。有z個直徑不同的圓盤，由小到大依次編號為1、2n。開始時，它們全部按遞減的次序插在塔座上。現要求按下列規則把n個圓盤按次序插放在z塔座上。（1）、每次只能移動一個圓盤；（2）、圓盤可以從任一個塔座上移到另一個塔座上；（3）、任何時刻都不能把一個較大的圓盤壓在較小的圓盤上。典型例題:1?設有n個數已經按從大到小的順序排列，現在從鍵盤上輸入n，判斷它是否在這n個數中，如果存在則輸出"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個硬幣(n為偶數)正面朝上排成一排，每次將n1個硬幣翻成朝上為止。編程讓計算機把翻硬幣的最簡過程及翻幣次數打印出來(用*代表正面，用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?有一對雌雄兔子，假定兩個月便可以繁殖雌雄各一對兔子。問n個月后共有多少對兔子遞歸的三要素：遞歸的形式：T[n]=T[n1]+T[n2]基本：T[1]=1，T[2]=1結束條件：n個月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階，上樓可以一步上一價，也可以一次上二階。編一個程序，計算共有多少種不同的走法。遞歸的形式：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.斐波那切數列遞歸：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?設有25個運動員要進行網球比賽。現要設計一個滿足以下要求的比賽日程表:、每個選手必須與其他n1個選手各賽一次；、每個選手每天只能參賽一次；、循環賽在n1天內結束。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給谷倉安裝了一個新的安全系統，并且要給牛群中的每一個奶牛安排一個有效的密碼。一個有效的密碼由L（3<=L<=15）個小寫字母（來自傳統的拉丁字母集'a'...'z'）組成，至少有一個元音（'a','e','i','o'，或者'u'），至少兩個輔音（除去元音以外的音節），并且有按字母表順序出現的字母（例如，'abc'是有效的，而'bac'不是）。給定一個期望長度L和C個小寫字母，寫一個程序，打印出所有的長度為L、能由這些字母組成的有效密碼。密碼必須按字母表順序打印出來，一行一個。題目名稱:passwd輸入格式:*第一行:兩個由空格分開的整數，L和C*第二行:C個空格分開的小寫字母，密碼是由這個字母集中的字母來構建的。輸入樣例（文件:46atcisw輸入詳細說明:由從給定的六個字母中選擇的、長度為4的密碼。輸出格式:*第一至行:每一個輸出行包括一個長度為L個字符的密碼（沒有空格）。輸出行必須按照字母順序排列。輸出樣例（文件:acisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistwProblem12:"跳房子"[HalBurch,2005]奶牛們按不太傳統的方式玩起了小孩子們玩的"跳房子"游戲。奶牛們創造了一個5x5的、由與x,y軸平行的數字組成的直線型網格，而不是用來在里面跳的、線性排列的、帶數字的方格。然后他們熟練地在網格中的數字中跳：向前跳、向后跳、向左跳、向右跳（從不斜過來跳），跳到網格中的另一個數字上。他們再這樣跳啊跳（按相同規則），跳到另外一個數字上（可能是已經跳過的數字）。一共在網格內跳過五次后，他們的跳躍構建了一個六位整數（可能以0開頭，例如000201）。求出所有能被這樣創造出來的不同整數的總數。問題名稱:numgrid輸入格式:*第1到5行:這樣的網格，一行5個整數輸入樣例（文件:1111111111111111112111111輸出格式:*第1行:能構建的不同整數的總數輸出樣例（文件:15輸出詳細說明:111111,111112,111121,111211,111212,112111,112121,121111,121112,121211,121212,211111,211121,212111和212121能夠被構建。沒有其它可能的數了。Problem13:衛星照片[RobKolstad,2005]FarmerJohn給他的農場買了WxH像素的衛星照片（1<=W<=80,1<=H<=1000），希望找出最大的"連續的"（互相連接的）牧場。任何一對像素，一個像素如果能橫向的或縱向的與屬于這個牧場的另一個像素相連，這樣的牧場稱作是連續的（這句話太難翻了，大家將就著理解一下，看了后面的范例應