2023年JAVA遞歸試題庫

遞歸一基礎知識 <1>遞歸中每次循環(huán)都必須使問題規(guī)模有所縮小。<2>遞歸操作的每兩步都是有緊密的聯系，如在“遞歸”的“歸操作時”，前一次的輸出就是后一次的輸入。<3>當子問題的規(guī)模足夠小時，必須可以直接求出該規(guī)模問題的解，其實也就是必須要有結束遞歸的條件。 二遞歸要解決什么問題呢? 1不同的方法體之間的傳遞 publicstaticvoidmain(String[]args){ g(); } privatestaticvoidg(){ f(3); } privatestaticintf(inti){ returni+k(i); } privatestaticintk(inti){ returni;} 2相同的方法體不同方法名之間的傳遞publicstaticvoidmain(String[]args){ inti=g(4); System.out.println(i); } privatestaticintg(inti){ returni*g1(3); } privatestaticintg1(inti){ returni+g2(2); } privatestaticintg2(inti){ returni*g3(1); } privatestaticintg3(inti){ returni; }3看一看得出其實功能相同所以直接使用遞歸 publicstaticvoidmain(String[]args){ inti=g(4); System.out.println(i); } privatestaticintg(inti){ if(i==1){ returni; } returni*g(i-1); } 根據2與3的比較明顯的看得出使用遞歸明顯的縮短了代碼的使用量4遞歸的使用框架 返回值類型f(形參){ if(終止條件){ return結果; } else{ returnf(形參遞減或者遞增); }}5遞歸算法一般用于解決三類問題：(1)數據的定義是按遞歸定義的。（Fibonacci函數）(2)問題解法按遞歸算法實現。這類問題雖則自身沒有明顯的遞歸結構，但用遞歸求解比迭代求解更簡樸，如漢諾塔(3)數據的結構形式是按遞歸定義的。如二叉樹、廣義表等，由于結構自身固有的遞歸特性，則它們的操作可遞歸地描述。三經典案例1斐波納契數列斐波那契數列（Fibonaccisequence），又稱黃金分割數列、因數學家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：0、1、1、2、3、5、8、13、21、34、……在數學上，斐波納契數列以如下被以遞歸的方法定義：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*） publicstaticintf(intx){ if(x==0){ return0; } if(x==1||x==2){ return1; } returnf(x-1)+f(x-2); }2階乘 publicstaticintf(intx){ if(x==1){ return1; }else{ returnx*f(x-1); } }3全排列4漢諾塔publicstaticvoidhanoi(intn,charorigin,charassist,chardestination){ if(n==1){ System.out.println("Direction:"+origin+"--->"+destination); }else{ hanoi(n-1,origin,destination,assist); System.out.println("Direction:"+origin+"--->"+destination); hanoi(n-1,assist,origin,destination); }}四試題： I遞歸定義33.遞歸的框架題意試數字符串反轉/*我們把“cba”稱為“abc”的反轉串。題意就是對字符串的反轉求一個串的反轉串的方法很多。下面就是其中的一種方法，代碼十分簡潔（甚至有些神秘），請聰明的你通過給出的一點點線索補充缺少的代碼。把填空的答案（僅填空處的答案，不涉及題面）存入考生文獻夾下相應題號的“解答.txt”中即可。*/思緒就是每次保存最后一位并且放在第一個上返回 或者每次保存第一個并且放在最后一個publicclassDemo03{ publicstaticStringreverseString(Strings){ if(s.length()<2||s==null)returns; //每一次將第一位放在最后，將第二位放在倒數第二位然后進行遞歸 returnreverseString(s.substring(1))+s.charAt(0); //returns.charAt(s.length()-1)+reverseString(s.substring(0,s.length()-1)); } publicstaticvoidmain(String[]args){ Strings="123456"; Stringss=reverseString(s); System.out.println(ss); }}運營結果：654321132、遞歸把串s中第一個出現的數字的值返回。假如找不到數字，返回-1例如：s="abc24us43"則返回2s="82445adb5"則返回8s="ab"則返回-1publicstaticintgetFirstNum(Strings){ if(s==null||s.length()==0)return-1; charc=s.charAt(0); if(c>='0'&&c<='9')returnc-'0';//填空 returngetFirstNum(s.substring(1));//填空 } publicstaticvoidmain(String[]args){ Strings="abs7c24us43"; System.out.println(getFirstNum(s)); }102.遞歸的定義試數連續(xù)數以下程序打印出0~9的數字，請補充缺少的代碼。*/publicclass遞歸連續(xù)數{publicstaticvoidf(intbegin,intend){if(begin>end)return;//填空System.out.println(begin);f(begin+1,end);}publicstaticvoidmain(String[]args){f(0,9);}}運營結果:0123456789113.遞歸定義題意理解公交車標價*公交車票價為5角。假設每位乘客只持有兩種幣值的貨幣：5角、1元。*再假設持有5角的乘客有m人，持有1元的乘客有n人。由于特殊情況，開始的時候，售票員沒有零錢可找。*我們想知道這m+n名乘客以什么樣的順序購票則可以順利完畢購票過程。*顯然，m<n的時候，無論如何都不能完畢，m>=n的時候，有些情況也不行。比如，第一個購票的乘客就持有1元。*下面的程序計算出這m+n名乘客所有也許順利完畢購票的不同情況的組合數目。*注意：只關心5角和1元交替出現的順序的不同排列，持有同樣幣值的兩名乘客互換位置并不算做一種新的情況來計數。*/publicclass公交車票價{//m:持有5角幣的人數//n:持有1元幣的人數//返回：所有順利完畢購票過程的購票順序的種類數publicstaticintf(intm,intn){if(m<n)return0;if(n==0)return1;returnf(m-1,n)+f(m,n-1);//填空}publicstaticvoidmain(String[]args){System.out.println(f(10,8));}運營結果:11934147遞歸以下程序打印出0~9的數字，請補充缺少的代碼。publicclassMyTest{ publicstaticvoidf(intbegin,intend) { If(begin>end)return; System.out.println(begin); f(begin+1,end); } publicstaticvoidmain(String[]args) { f(0,9); }} II排列普通 1字符排序全排列算法是這樣的，假如給定N個不同字符，將這N個字符全排列，最終的結果將會是N!種。如：給定A、B、C三個不同的字符，則結果為：ABC、ACB、BAC、BCA、CAB、CBA一共3!=3*2=6種情況。publicclassAllPermutation{ publicstaticvoidmain(String[]args) { //使用遞歸完畢全排列 char[]source=newchar[]{'A','B','C'}; char[]result=newchar[source.length]; allPermutation(0,source,result); } /** * *@paramindex當前考慮的數的下標(從0開始) *@paramsource *@paramresult */ publicstaticvoidallPermutation(intindex,char[]source,char[]result){ //當源數據中只有一個字符時，將該字符加入結果數組，并輸出 if(source.length==1){ result[index]=source[0]; show(result); return; } // for(inti=0;i<result.length-index;i++){ result[index]=source[i]; char[]newSource=getNewSource(source,source[i]); allPermutation(index+1,newSource,result); } } publicstaticvoidshow(char[]result){ System.out.println(result); } /** *生成去掉指定字符的新源數據數組 *@paramsource本來的源數據數組 *@paramc指定去掉的字符 *@return */ publicstaticchar[]getNewSource(char[]source,charc){ char[]newSource=newchar[source.length-1]; for(inti=0,j=0;i<source.length;i++){ if(source[i]!=c){ newSource[j]=source[i]; j++; } } returnnewSource; }}42.全排列遞歸Stringbuffer警察智力訓練匪警請撥110,即使手機欠費也可撥通！為了保障社會秩序，保護人民群眾生命財產安全，警察叔叔需要與罪犯斗智斗勇，因而需要經常性地進行體力訓練和智力訓練！某批警察叔叔正在進行智力訓練：123456789=110;請看上邊的算式，為了使等式成立，需要在數字間填入加號或者減號（可以不填，但不能填入其它符號）。之間沒有填入符號的數字組合成一個數，例如：12+34+56+7-8+9就是一種合格的填法；123+4+5+67-89是另一個也許的答案。請你運用計算機的優(yōu)勢，幫助警察叔叔快速找到所有答案。每個答案占一行。形如：12+34+56+7-8+9123+4+5+67-89......已知的兩個答案可以輸出，但不計分。各個答案的前后順序不重要。//遍歷所有情況publicstaticvoidfun(Stringv,intn){if(n==9){//修改到最后一位符號時輸出check(v);}else{//遞歸向后修改，數字變?yōu)閿底旨臃杅un(v.replace(n+"",n+"+"),n+1);fun(v.replace(n+"",n+"-"),n+1);fun(v,n+1);}}//驗證并輸出publicstaticvoidcheck(Stringstr){String[]s=str.split("[\\+]");intsum=0;for(Stringt:s){String[]sub=t.split("[\\-]");intnum=Integer.parseInt(sub[0]);//計算負數for(inti=1;i<sub.length;i++){num-=Integer.parseInt(sub[i]);}sum+=num;//正數或負數結果加到總和上}if(sum==110){System.out.println(str);}}publicstaticvoidmain(String[]args){Stringstr="";fun(str,1);//調用函數，從1開始修改}46算法實現全排列遞歸算法：將數據分為兩部分，遞歸將數據從左側移右側實現全排列importjava.util.Arrays;importjava.util.List;importjava.util.ArrayList;publicclassT06{ //輸出 publicstaticvoidprint(Listtarget){ for(Objecto:target){ System.out.print(o); } System.out.println(); } //遞歸排列 publicstaticvoidsort(Listdatas,Listtarget,intn){ if(target.size()==n){ print(target); return; } for(inti=0;i<datas.size();i++){ ListnewDatas=newArrayList(datas); ListnewTarget=newArrayList(target); newTarget.add(newDatas.get(i)); newDatas.remove(i); sort(newDatas,newTarget,n); } } //主函數 publicstaticvoidmain(String[]args){ String[]s={"a","b","c"}; sort(Arrays.asList(s),newArrayList(),s.length); }}運營結果：abcacbbacbcacabcba方法二：publicclassAllSort{ publicstaticvoidperm(String[]buf,intstart,intend){ if(start==end){//當只規(guī)定對數組中一個字母進行全排列時，只要按該數組輸出即可 for(inti=0;i<=end;i++){ System.out.print(buf[i]); } System.out.println(); } else{//多個字母全排列 for(inti=start;i<=end;i++){ Stringtemp=buf[start];//互換數組第一個元素與后續(xù)的元素 buf[start]=buf[i]; buf[i]=temp; perm(buf,start+1,end);//后續(xù)元素遞歸全排列 temp=buf[start];//將互換后的數組還原 buf[start]=buf[i]; buf[i]=temp; } } }publicstaticvoidmain(String[]args){Stringbuf[]={"a","b","c"};perm(buf,0,buf.length-1);}}運營結果：abcacbbacbcacbacab47.遞歸字符串全排列

字符串全排列publicclassT03{ //輸出字符數組 publicstaticvoidprint(char[]arr){ for(inti=0;i<arr.length;i++){ System.out.print(arr[i]); } System.out.println(); } //遞歸遍歷 publicstaticvoidperm(char[]arr,intstart,intend){ if(start==end){ print(arr); //輸出 }else{ for(inti=start;i<=end;i++){ //換位 charc=arr[start]; arr[start]=arr[i]; arr[i]=c; //遞歸 perm(arr,start+1,end); //恢復數組原位 c=arr[start]; arr[start]=arr[i]; arr[i]=c; } } } //字符串轉字符數組 publicstaticvoidf(Strings){ char[]arr=s.toCharArray(); perm(arr,0,arr.length-1); } publicstaticvoidmain(String[]args){ Strings="abc"; f(s); }}運營結果：abcacbbacbcacbacab58.遞歸全排列帶分數100可以表達為帶分數的形式：100=3+69258/714還可以表達為：100=82+3546/197注意特性：帶分數中，數字1~9分別出現且只出現一次（不包含0）。類似這樣的帶分數，100有11種表達法。題目規(guī)定：從標準輸入讀入一個正整數N(N<1000*1000)程序輸出該數字用數碼1~9不反復不漏掉地組成帶分數表達的所有種數。注意：不規(guī)定輸出每個表達，只記錄有多少表達法！例如：用戶輸入：100程序輸出：11再例如：用戶輸入：105程序輸出：6資源約定：峰值內存消耗（含虛擬機）<64MCPU消耗<3000ms請嚴格按規(guī)定輸出，不要畫蛇添足地打印類似：“請您輸入...”的多余內容。所有代碼放在同一個源文獻中，調試通過后，拷貝提交該源碼。publicclassMyTest{privatestaticSet<Integer>all=newHashSet<Integer>();privatestaticSet<Integer>temp1=newHashSet<Integer>();privatestaticSet<Integer>temp2=newHashSet<Integer>();publicstaticvoidmain(String[]args){for(inti=1;i<9876;i++){all.clear();if(isDuplicate(i,temp1)){continue;}for(intj=2;j<100;j++){if(!isDuplicate(j*i,temp1)){inty=100-j;if(!isDuplicate(y,temp2)&&all.size()==9){System.out.println(100+"="+y+"+"+j*i+"/"+i);}else{all.removeAll(temp1);}}}}}privatestaticbooleanisDuplicate(intn,Set<Integer>temp){temp.clear();inti=0;booleanflag=false;while(n>0){intx=n%10;temp.add(x);n=n/10;i++;}if(temp.contains(0)||temp.size()<i||temp.removeAll(all)){flag=true;}else{all.addAll(temp);}returnflag;}}92.全排列排列組合數組列表m個字符的n個字符排列/**1~9個數中的n位數全排列*/staticintcount=0;//總個數/***全排列*@paramlis記錄組合*@paramstart為0~9(lis所用的下標)*@paramend為9*/publicstaticvoidf(List<Integer>lis,intstart){if(start>=lis.size()){System.out.println(lis);//輸出排列組合count++;//計數return;}for(inti=1;i<=9;i++){if(!lis.contains(i)){lis.set(start,i);//修改元素}else{continue;}f(lis,start+1);//遞歸修改每個元素lis.set(start,-1);//還原}}publicstaticvoidmain(String[]args){intn=5;//1~9個數中選5個全排列List<Integer>lis=newArrayList<Integer>();for(inti=0;i<n;i++){//初始化lis長度lis.add(-1);}f(lis,0);//全排列System.out.println("總個數:"+count);}運營結果:[1,2,3,4,5][1,2,3,4,6][1,2,3,4,7][1,2,3,4,8][1,2,3,4,9][1,2,3,5,4].............................................[9,8,7,5,6][9,8,7,6,1][9,8,7,6,2][9,8,7,6,3][9,8,7,6,4][9,8,7,6,5]總個數:15120方法二:對以上程序的(數字排列)擴展為(字符排列)看下程序:importjava.util.ArrayList;importjava.util.List;publicclassT13{staticintcount=0;//記錄個數//m排n全排列publicstaticvoidf(List<Character>lis,char[]c,intn){if(n==0){count++;//記錄個數System.out.println(lis);//輸出return;}for(inti=0;i<c.length;i++){if(!lis.contains(c[i])){//不包含,則添加lis.set(lis.size()-n,c[i]);}else{//否則跳過continue;}f(lis,c,n-1);//遞歸lis.set(lis.size()-n,'0');//還原}}publicstaticvoidmain(String[]args){longstar=System.currentTimeMillis();intn=3;//任選n個字符的排列組合char[]c="".toCharArray();//要排列的字符List<Character>lis=newArrayList<Character>();for(inti=0;i<n;i++){lis.add('0');//初始化lis的長度}f(lis,c,n);//進入全排列System.out.println("排列個數:"+count);System.out.println("花費時間:"+(System.currentTimeMillis()-star)+"毫秒");}}運營結果:[1,2,3][1,2,4][1,2,5][1,2,6][1,2,7][1,2,8][1,2,9][1,3,2]...........................[9,7,8][9,8,1][9,8,2][9,8,3][9,8,4][9,8,5][9,8,6][9,8,7]排列個數:504花費時間:19毫秒方法三:/**m個字符的n個字符排列*/importjava.util.ArrayList;importjava.util.List;publicclassm個字符的n個字符排列{privatestaticchar[]is=newchar[]{'1','2','3','4','5','6','7','8','9'};privatestaticinttotal;privatestaticintm=4;privatevoidplzh(Strings,List<Integer>iL,intm){if(m==0){System.out.println(s);total++;return;}List<Integer>iL2;for(inti=0;i<is.length;i++){iL2=newArrayList<Integer>();iL2.addAll(iL);if(!iL.contains(i)){Stringstr=s+is[i];iL2.add(i);plzh(str,iL2,m-1);}}}publicstaticvoidmain(String[]args){List<Integer>iL=newArrayList<Integer>();newm個字符的n個字符排列().plzh("",iL,m);System.out.println("total:"+total);}}運營結果:1234123512361237123812391243............9867987198729873987498759876total:3024106.全排列遞歸排列組合排列平方數若干不同的數字，排列組合后能產生多少個平方數？下面的代碼解決了這個問題。對于：1,6,9排列后，可產生3個平方數：169196961請閱讀下面的代碼，填寫缺失的部分（下劃線部分）。注意：請把填空的答案（僅填空處的答案，不涉及題面）存入考生文獻夾下相應題號的“解答.txt”中即可。直接寫在題面中不能得分。*/publicclassT{publicstaticvoidf(int[]a,intn){if(n==a.length-1){intk=0;//把a里的數字組合為一個數字kfor(inti=0;i<a.length;i++)k=k*10+a[i];//填空1intm=(int)(Math.sqrt(k)+0.5);if(m*m==k){System.out.println(k);}return;}//全排列for(inti=n;i<a.length;i++){intt=a[n];a[n]=a[i];a[i]=t;f(a,n+1);//填空2t=a[n];a[n]=a[i];a[i]=t;}}publicstaticvoidmain(String[]args){int[]a={1,9,6};f(a,0);}}117.排列的個數計算3個A，2個B可以組成多少種排列的問題（如：AAABB,AABBA）是《組合數學》的研究領域。但有些情況下，也可以運用計算機計算速度快的特點通過巧妙的推理來解決問題。下列的程序計算了m個A，n個B可以組合成多少個不同排列的問題。請完善它。*/publicclass排列的個數{publicstaticintf(intm,intn){if(m==0||n==0)return1;returnf(m-1,n)+f(m,n-1);//填空}publicstaticvoidmain(String[]args){System.out.println(f(3,2));}}運營結果:10|||全排列李白打酒類型38.全排列奇怪的比賽（低碳生活大獎賽）某電視臺舉辦了低碳生活大獎賽。題目的計分規(guī)則相稱奇怪：每位選手需要回答10個問題（其編號為1到10），越后面越有難度。答對的，當前分數翻倍；答錯了則扣掉與題號相同的分數（選手必須回答問題，不回答按錯誤解決）。每位選手都有一個起步的分數為10分。某獲勝選手最終得分剛好是100分，假如不讓你看比勝過程，你能推斷出他（她）哪個題目答對了，哪個題目答錯了嗎？假如把答對的記為1，答錯的記為0，則10個題目的回答情況可以用僅具有1和0的串來表達。例如：就是也許的情況。你的任務是算出所有也許情況。每個答案占一行。 publicclassTi_38{ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub //定義一個10個數的數組保存十個題目 intx[]=newint[10]; f(x,0); } privatestaticvoidf(int[]x,inti){ //TODOAuto-generatedmethodstiub //假如i大于數組的長度就說明數組賦值完畢開始輸出 if(i>=x.length){ show(x); return; } //調用兩次遞歸實現全排列逐步填充 x[i]=0; f(x,i+1); x[i]=1; f(x,i+1); } //按規(guī)定打印數組 privatestaticvoidshow(intx[]){ //TODOAuto-generatedmethodstub ints=10; for(inti=0;i<=x.length-1;i++){ if(x[i]==0){ s-=(i+1); } if(x[i]==1){ s*=2; } } if(s==100){ for(inti:x){ System.out.print(i); } System.out.println(); } }91.全排列李白打酒排列組合排座位/*排座位要安排：3個A國人，3個B國人，3個C國人坐成一排。規(guī)定不能使連續(xù)的3個人是同一個國籍。求所有不同方案的總數？*/publicclassT13{staticintsum=0;//不同方案總個數//檢查是否有同一國人連續(xù)3個publicstaticbooleancheck(char[]c){intcount=1;//初始個數for(inti=0;i<c.length-1;i++){if(c[i]==c[i+1]){count++;}else{count=1;//初始個數}if(count>=3)returntrue;}returnfalse;}//全排列publicstaticvoidallSort(char[]c,intstart,intend){if(start>end){if(!check(c)){//檢查是否有同一國人連續(xù)3個sum++;//不同方案總個數加1}return;}else{for(inti=start;i<=end;i++){chartemp=c[i];c[i]=c[start];c[start]=temp;allSort(c,start+1,end);//遞歸temp=c[i];c[i]=c[start];c[start]=temp;}}}publicstaticvoidmain(String[]args){char[]c={'A','A','A','B','B','B','C','C','C'};allSort(c,0,c.length-1);//全排列System.out.println(sum);}}151遞歸楊輝三角形(a+b)的n次冪的展開式中各項的系數很有規(guī)律，對于n=2，3，4時分別是：121，1331，14641。這些系數構成了著名的楊輝三角形：11112113311464115101051下列的程序給出了計算第m層的第n個系數的計算方法，試完善之（m，n都從0算起）。 publicstaticintf(intm,intn) { if(m==0)return1; if(n==0||n==m)return1; return___f(n-1)+f(n-2)_______________________; } IV經典案例43.漢諾塔思想遞歸泊松分酒泊松是法國數學家、物理學家和力學家。他一生致力科學事業(yè)，成果頗多。有許多著名的公式定理以他的名字命名，比如概率論中著名的泊松分布。有一次閑暇時，他提出過一個有趣的問題，后稱為：“泊松分酒”。在我國古代也提出過類似問題，遺憾的是沒有進行徹底探索，其中流傳較多是：“韓信走馬分油”問題。有3個容器，容量分別為12升，8升，5升。其中12升中裝滿油，此外兩個空著。規(guī)定你只用3個容器操作，最后使得某個容器中正好有6升油。下面的列表是也許的操作狀態(tài)記錄： 12,0,0 4,8,0 4,3,5 9,3,0 9,0,3 1,8,3 1,6,5每行3個數據，分別表達12，8，6升容器中的油量第一行表達初始狀態(tài)，第二行表達把12升倒入8升容器后的狀態(tài)，第三行是8升倒入5升，...當然，同一個題目也許有多種不同的對的操作環(huán)節(jié)。本題目的規(guī)定是，請你編寫程序，由用戶輸入：各個容器的容量，開始的狀態(tài)，和規(guī)定的目的油量，程序則通過計算輸出一種實現的環(huán)節(jié)（不需要找到所有也許的方法）。假如沒有也許實現，則輸出：“不也許”。例如，用戶輸入： 12,8,5,12,0,0,6用戶輸入的前三個數是容器容量（由大到?。?，接下來三個數是三個容器開始時的油量配置，最后一個數是規(guī)定得到的油量（放在哪個容器里得到都可以）則程序可以輸出（答案不唯一，只驗證操作可行性）： 12,0,0 4,8,0 4,3,5 9,3,0 9,0,3 1,8,3 1,6,5每一行表達一個操作過程中的油量狀態(tài)。publicclassTest{publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubWinew=newWine();w.Backtrack(12,0,0);}}classWine{intb1=12;intb2=8;intb3=5;intm=6;//目的酒量publicWine(){}publicvoidBacktrack(intcur1,intcur2,intcur3){ //輸出當前的三個瓶子中的情況System.out.println(cur1+""+cur2+""+cur3);//假如每一個瓶子都是6瓶就成功了if(cur1==m||cur2==m||cur3==m){System.out.print("findthekey！");return;}if(cur2!=0&&cur3!=b3){//瓶子2有酒并且瓶子三不滿 //假如瓶子2+瓶子3的不超過小瓶子的酒量就把瓶子2中的酒倒進瓶子三if(cur2+cur3<=5)Backtrack(cur1,0,cur2+cur3);//否則就用瓶子2中的把瓶子3填滿瓶子1不動elseBacktrack(cur1,cur2-(5-cur3),b3);}elseif(cur3==b3){//瓶子3滿的，這時就要把就倒入到瓶子1中if(cur3+cur1<=b1)//瓶子3+瓶子1小于瓶子1就把瓶子3中所有倒入瓶子1瓶子2不變瓶子1不滿Backtrack(cur1+cur3,cur2,0);else//Backtrack(b1,cur2,cur3-(b1-cur1));}elseif(cur2==0){//當瓶子2是空的時候從瓶子1倒入酒if(cur1>=b2)//當第一個瓶子大于5的時候，就把第二個瓶子倒?jié)MBacktrack(cur1-b2,b2,cur3);else//假如第一個瓶子小于5的時候就所有倒進第二個瓶子Backtrack(0,cur1,cur3);}}}51.漢諾塔類型振興中華小明參與了學校的趣味運動會，其中的一個項目是：跳格子。地上畫著一些格子，每個格子里寫一個字，如下所示：（也可參見p1.jpg）從我做起振我做起振興做起振興中起振興中華比賽時，先站在左上角的寫著“從”字的格子里，可以橫向或縱向跳到相鄰的格子里，但不能跳到對角的格子或其它位置。一直要跳到“華”字結束。規(guī)定跳過的路線剛好構成“從我做起振興中華”這句話。請你幫助小明算一算他一共有多少種也許的跳躍路線呢？答案是一個整數，請通過瀏覽器直接提交該數字。注意：不要提交解答過程，或其它輔助說明類的內容。/**振興中華*/publicclassTest002{privatestaticchar[][]a={{'從','我','做','起','振'},{'我','做','起','振','興'},{'做','起','振','興','中'},{'起','振','興','中','華'}};privatestaticintcount;//計數變量publicstaticvoidmain(String[]args){count=0;char[]b=newchar[8];jump(0,0,0,b);System.out.println(count);}/***模擬小明跳躍格子的遞歸方法**@paramstep跳格子通過的步數，范圍是0-7*@paramx向下跳的位置，范圍是0-3*@paramy向右跳的位置，范圍是0-4*@paramb暫存跳過路線的一維數組*/privatestaticvoidjump(intstep,intx,inty,char[]b){//*******遞歸出口**********if(x>3){return;}if(y>4){return;}if(step>7){return;}//記錄跳過的字b[step]=a[x][y];if(step==7){//剛好走到8個字的位置if(check(b)){count++;}return;}jump(step+1,x+1,y,b);//向下跳jump(step+1,x,y+1,b);//向右跳}//檢查數組內容是“從我做起振興中華”privatestaticbooleancheck(char[]b){if("從我做起振興中華".equals(String.valueOf(b))){returntrue;}else{returnfalse;}}}44.斐波納契數列黃金分割數黃金分割數0.618與美學有重要的關系。舞臺上報幕員所站的位置大約就是舞臺寬度的0.618處，墻上的畫像一般也掛在房間高度的0.618處，甚至股票的波動據說也能找到0.618的影子....黃金分割數是個無理數，也就是無法表達為兩個整數的比值。0.618只是它的近似值，其真值可以通過對5開方減去1再除以2來獲得，我們取它的一個較精確的近似值：0.618034有趣的是，一些簡樸的數列中也會包含這個無理數，這很令數學家震驚！134711182947....稱為“魯卡斯隊列”。它后面的每一個項都是前邊兩項的和。假如觀測前后兩項的比值，即：1/3,3/4,4/7,7/11,11/18...會發(fā)現它越來越接近于黃金分割數！你的任務就是計算出從哪一項開始，這個比值四舍五入后已經達成了與0.618034一致的精度。請寫出該比值。格式是：分子/分母。比如：29/47publicclassDemo05_Fibonacci{publicstaticdoubleformat(doubled){BigDecimalbd=newBigDecimal(d).setScale(6,BigDecimal.ROUND_HALF_UP);doubledd=bd.doubleValue();returndd;}publicstaticvoidf(inta,intb){doubled=format((double)a/b);if(d==0.618034){System.out.println(a+"/"+b+"="+d);return;}f(b,a+b);}publicstaticvoidmain(String[]args){f(1,3);}}109.楊輝三角(a+b)的n次冪的展開式中各項的系數很有規(guī)律，對于n=2，3，4時分別是：121，1331，14641。這些系數構成了著名的楊輝三角形：11112113311464115101051下列的程序給出了計算第m層的第n個系數的計算方法，試完善之（m，n都從0算起）。*/publicclass_33_151{ publicstaticintf(intm,intn) { if(m==0)return1; if(n==0||n==m)return1; returnf(m-1,n-1)+f(m-1,n); } publicstaticvoidmain(String[]args){ intm=5; intn=6; System.out.println(f(m,n)); }}V填充問題82.遞歸打印回型嵌套/*************************************************************************觀測這個圖形，它是由一系列正方形的星號方框嵌套而成。在上邊的例子中，最外方框的邊長為11。本題的任務就是從標準輸入獲得一個整數n(1<n<100)程序則生成嵌套著的回字型星號方框。其最外層方框的邊長為n例如：輸入：5程序輸出：*****************輸入：6程序輸出：*************************/importjava.util.Scanner;publicclassDemo04{//顯示數組publicstaticvoidshow(char[][]c){for(char[]x:c){for(chary:x){System.out.print(y);}System.out.println();}}//初始化數組為空數組publicstaticvoidinit(char[][]c){for(inti=0;i<c.length;i++){for(intj=0;j<c.length;j++){c[i][j]='';}}}publicstaticvoidoper(char[][]c,intn,intstart){if(start>=n)return;for(inti=start;i<n;i++){//賦值第一行為'*'上c[start][i]='*';}for(inti=start;i<n;i++){//賦值最后一行為'*'下c[n-1][i]='*';}for(inti=start;i<n;i++){//賦值左一列為'*'左c[i][start]='*';}for(inti=start;i<n;i++){//賦值右一列為'*'右c[i][n-1]='*';}oper(c,n-2,start+2);//矩陣范圍縮小2,起始賦值位置加2}publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);System.out.println("輸入獲得一個整數n(1<n<100)");intn=scan.nextInt();char[][]c=newchar[n][n];init(c);//初始化數組為空數組oper(c,n,0);//賦值show(c);//顯示數組}}VI其他10回溯法求21位數的水仙花數 水仙花數是指一個n位數(n≥3)，它的每個位上的數字的n次冪之和等于它自身。（例如：1^3+5^3+3^3=153）/**求21位數的水仙花數*/importjava.math.BigInteger;publicclassDemo01_BigInteger{//求每個i的21次方publicstaticBigIntegerp(inti){BigIntegerbase=BigInteger.valueOf(i);returnbase.pow(21);}publicstaticvoidji_suan(BigInteger[]pw,int[]nn){BigIntegersum=BigInteger.ZERO;for(inti=0;i<10;i++){sum=sum.add(pw[i].multiply(BigInteger.valueOf(nn[i])));}Strings=""+sum;if(s.length()!=21)return;//擬定各數字出現的多少次int[]nn2=newint[10];for(inti=0;i<21;i++){nn2[s.charAt(i)-'0']++;}for(inti=0;i<10;i++){if(nn[i]!=nn2[i])return;}System.out.println(s);}publicstaticvoidf(BigInteger[]pw,int[]nn,intcur,intuse){if(cur==9){nn[9]=21-use;ji_suan(pw,nn);return;}//對當前位置所有也許進行枚舉for(inti=0;i<21-use;i++){nn[cur]=i;f(pw,nn,cur+1,use+i);}}publicstaticvoidmain(String[]args){longstartTime=System.currentTimeMillis();//程序開始時間BigIntegerpw[]=newBigInteger[10];for(inti=0;i<pw.length;i++){pw[i]=p(i);}intnn[]=newint[10];f(pw,nn,0,0);System.out.println("OK");longendTime=System.currentTimeMillis();//程序結束時間System.out.println((endTime-startTime)/1000f+"秒");//運營總時間}}20.方陣順時針旋轉遞歸求解比迭代求解更簡樸對一個方陣轉置，就是把本來的行號變列號，本來的列號變行號例如，如下的方陣：12345678910111213141516轉置后變?yōu)椋?5913261014371115481216但，假如是對該方陣順時針旋轉（不是轉置），卻是如下結果：13951141062151173161284publicclassDemo03{//矩陣順時針旋轉publicstaticvoidrotation(int[][]n,int[][]m,inti,intj){intt=j;//標記最后一行的位置if(i>=n.length)return;for(intk=0;k<n.length;k++){m[i][k]=n[j--][i];//解決一行}rotation(n,m,++i,t);//遞歸解決下一行}//輸出矩陣publicstaticvo