JAVA遞歸試題庫完整

./遞歸一基礎(chǔ)知識<1>遞歸中每次循環(huán)都必須使問題規(guī)模有所縮小。<2>遞歸操作的每兩步都是有緊密的聯(lián)系,如在"遞歸"的"歸操作時",前一次的輸出就是后一次的輸入。<3>當(dāng)子問題的規(guī)模足夠小時,必須能夠直接求出該規(guī)模問題的解,其實也就是必須要有結(jié)束遞歸的條件。二遞歸要解決什么問題呢? 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>; }根據(jù)2與3的比較明顯的看得出使用遞歸明顯的縮短了代碼的使用量4遞歸的使用框架返回值類型f<形參>{if<終止條件>{return結(jié)果;}else{returnf<形參遞減或者遞增>;}}5遞歸算法一般用于解決三類問題：<1>數(shù)據(jù)的定義是按遞歸定義的?！睩ibonacci函數(shù)〕<2>問題解法按遞歸算法實現(xiàn)。這類問題雖則本身沒有明顯的遞歸結(jié)構(gòu),但用遞歸求解比迭代求解更簡單,如漢諾塔<3>數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。如二叉樹、廣義表等,由于結(jié)構(gòu)本身固有的遞歸特性,則它們的操作可遞歸地描述。三經(jīng)典案例1斐波納契數(shù)列斐波那契數(shù)列〔Fibonaccisequence〕,又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契以兔子繁殖為例子而引入,故又稱為"兔子數(shù)列",指的是這樣一個數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上,斐波納契數(shù)列以如下被以遞歸的方法定義：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.遞歸的框架題意試數(shù)字符串反轉(zhuǎn)/*我們把"cba"稱為"abc"的反轉(zhuǎn)串。題意就是對字符串的反轉(zhuǎn)求一個串的反轉(zhuǎn)串的方法很多。下面就是其中的一種方法,代碼十分簡潔〔甚至有些神秘〕,請聰明的你通過給出的一點點線索補(bǔ)充缺少的代碼。把填空的答案〔僅填空處的答案,不包括題面〕存入考生文件夾下對應(yīng)題號的"解答.txt"中即可。*/思路就是每次保存最后一位并且放在第一個上返回 或者每次保存第一個并且放在最后一個publicclassDemo03{publicstaticStringreverseString<Strings>{if<s.length<><2||s==null>returns; //每一次將第一位放在最后,將第二位放在倒數(shù)第二位然后進(jìn)行遞歸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>; }}運行結(jié)果：654321132、遞歸把串s中第一個出現(xiàn)的數(shù)字的值返回。如果找不到數(shù)字,返回-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.遞歸的定義試數(shù)連續(xù)數(shù)以下程序打印出0~9的數(shù)字,請補(bǔ)充缺少的代碼。*/publicclass遞歸連續(xù)數(shù){publicstaticvoidf<intbegin,intend>{if<begin>end>return;//填空System.out.println<begin>;f<begin+1,end>;}publicstaticvoidmain<String[]args>{f<0,9>;}}運行結(jié)果:0123456789113.遞歸定義題意理解公交車標(biāo)價*公交車票價為5角。假設(shè)每位乘客只持有兩種幣值的貨幣：5角、1元。*再假設(shè)持有5角的乘客有m人,持有1元的乘客有n人。由于特殊情況,開始的時候,售票員沒有零錢可找。*我們想知道這m+n名乘客以什么樣的順序購票則可以順利完成購票過程。*顯然,m<n的時候,無論如何都不能完成,m>=n的時候,有些情況也不行。比如,第一個購票的乘客就持有1元。*下面的程序計算出這m+n名乘客所有可能順利完成購票的不同情況的組合數(shù)目。*注意：只關(guān)心5角和1元交替出現(xiàn)的次序的不同排列,持有同樣幣值的兩名乘客交換位置并不算做一種新的情況來計數(shù)。*/publicclass公交車票價{//m:持有5角幣的人數(shù)//n:持有1元幣的人數(shù)//返回：所有順利完成購票過程的購票次序的種類數(shù)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>>;}運行結(jié)果:11934147遞歸以下程序打印出0~9的數(shù)字,請補(bǔ)充缺少的代碼。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個字符全排列,最終的結(jié)果將會是N!種。如：給定A、B、C三個不同的字符,則結(jié)果為：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當(dāng)前考慮的數(shù)的下標(biāo)<從0開始> *paramsource *paramresult */publicstaticvoidallPermutation<intindex,char[]source,char[]result>{//當(dāng)源數(shù)據(jù)中只有一個字符時,將該字符加入結(jié)果數(shù)組,并輸出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>; }/** *生成去掉指定字符的新源數(shù)據(jù)數(shù)組 *paramsource原來的源數(shù)據(jù)數(shù)組 *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警察智力訓(xùn)練匪警請撥110,即使手機(jī)欠費也可撥通！為了保障社會秩序,保護(hù)人民群眾生命財產(chǎn)安全,警察叔叔需要與罪犯斗智斗勇,因而需要經(jīng)常性地進(jìn)行體力訓(xùn)練和智力訓(xùn)練！某批警察叔叔正在進(jìn)行智力訓(xùn)練：123456789=110;請看上邊的算式,為了使等式成立,需要在數(shù)字間填入加號或者減號〔可以不填,但不能填入其它符號〕。之間沒有填入符號的數(shù)字組合成一個數(shù),例如：12+34+56+7-8+9就是一種合格的填法；123+4+5+67-89是另一個可能的答案。請你利用計算機(jī)的優(yōu)勢,幫助警察叔叔快速找到所有答案。每個答案占一行。形如：12+34+56+7-8+9123+4+5+67-89已知的兩個答案可以輸出,但不計分。各個答案的前后順序不重要。//遍歷所有情況publicstaticvoidfun<Stringv,intn>{if<n==9>{//修改到最后一位符號時輸出check<v>;}else{//遞歸向后修改,數(shù)字變?yōu)閿?shù)字加符號fun<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]>;//計算負(fù)數(shù)for<inti=1;i<sub.length;i++>{num-=Integer.parseInt<sub[i]>;}sum+=num;//正數(shù)或負(fù)數(shù)結(jié)果加到總和上}if<sum==110>{System.out.println<str>;}}publicstaticvoidmain<String[]args>{Stringstr="123456789";fun<str,1>;//調(diào)用函數(shù),從1開始修改}46算法實現(xiàn)全排列遞歸算法：將數(shù)據(jù)分為兩部分,遞歸將數(shù)據(jù)從左側(cè)移右側(cè)實現(xiàn)全排列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>; } }//主函數(shù)publicstaticvoidmain<String[]args>{ String[]s={"a","b","c"};sort<Arrays.asList<s>,newArrayList<>,s.length>; }}運行結(jié)果：abcacbbacbcacabcba方法二：publicclassAllSort{publicstaticvoidperm<String[]buf,intstart,intend>{if<start==end>{//當(dāng)只要求對數(shù)組中一個字母進(jìn)行全排列時,只要按該數(shù)組輸出即可for<inti=0;i<=end;i++>{ System.out.print<buf[i]>; } System.out.println<>; }else{//多個字母全排列for<inti=start;i<=end;i++>{ Stringtemp=buf[start];//交換數(shù)組第一個元素與后續(xù)的元素 buf[start]=buf[i]; buf[i]=temp;perm<buf,start+1,end>;//后續(xù)元素遞歸全排列 temp=buf[start];//將交換后的數(shù)組還原 buf[start]=buf[i]; buf[i]=temp; } } }publicstaticvoidmain<String[]args>{Stringbuf[]={"a","b","c"};perm<buf,0,buf.length-1>;}}運行結(jié)果：abcacbbacbcacbacab47.遞歸字符串全排列字符串全排列publicclassT03{//輸出字符數(shù)組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>;//恢復(fù)數(shù)組原位 c=arr[start]; arr[start]=arr[i]; arr[i]=c; } } }//字符串轉(zhuǎn)字符數(shù)組publicstaticvoidf<Strings>{char[]arr=s.toCharArray<>;perm<arr,0,arr.length-1>; }publicstaticvoidmain<String[]args>{ Strings="abc";f<s>; }}運行結(jié)果：abcacbbacbcacbacab58.遞歸全排列帶分?jǐn)?shù)100可以表示為帶分?jǐn)?shù)的形式：100=3+69258/714還可以表示為：100=82+3546/197注意特征：帶分?jǐn)?shù)中,數(shù)字1~9分別出現(xiàn)且只出現(xiàn)一次〔不包含0〕。類似這樣的帶分?jǐn)?shù),100有11種表示法。題目要求：從標(biāo)準(zhǔn)輸入讀入一個正整數(shù)N<N<1000*1000>程序輸出該數(shù)字用數(shù)碼1~9不重復(fù)不遺漏地組成帶分?jǐn)?shù)表示的全部種數(shù)。注意：不要求輸出每個表示,只統(tǒng)計有多少表示法！例如：用戶輸入：100程序輸出：11再例如：用戶輸入：105程序輸出：6資源約定：峰值內(nèi)存消耗〔含虛擬機(jī)〕<64MCPU消耗<3000ms請嚴(yán)格按要求輸出,不要畫蛇添足地打印類似："請您輸入..."的多余內(nèi)容。所有代碼放在同一個源文件中,調(diào)試通過后,拷貝提交該源碼。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.全排列排列組合數(shù)組列表m個字符的n個字符排列/**1~9個數(shù)中的n位數(shù)全排列*/staticintcount=0;//總個數(shù)/***全排列*paramlis記錄組合*paramstart為0~9<lis所用的下標(biāo)>*paramend為9*/publicstaticvoidf<List<Integer>lis,intstart>{if<start>=lis.size<>>{System.out.println<lis>;//輸出排列組合count++;//計數(shù)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個數(shù)中選5個全排列List<Integer>lis=newArrayList<Integer><>;for<inti=0;i<n;i++>{//初始化lis長度lis.add<-1>;}f<lis,0>;//全排列System.out.println<"總個數(shù):"+count>;}運行結(jié)果:[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]總個數(shù):15120方法二:對以上程序的<數(shù)字排列>擴(kuò)展為<字符排列>看下程序:importjava.util.ArrayList;importjava.util.List;publicclassT13{staticintcount=0;//記錄個數(shù)//m排n全排列publicstaticvoidf<List<Character>lis,char[]c,intn>{if<n==0>{count++;//記錄個數(shù)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="123456789".toCharArray<>;//要排列的字符List<Character>lis=newArrayList<Character><>;for<inti=0;i<n;i++>{lis.add<'0'>;//初始化lis的長度}f<lis,c,n>;//進(jìn)入全排列System.out.println<"排列個數(shù):"+count>;System.out.println<"花費時間:"+<System.currentTimeMillis<>-star>+"毫秒">;}}運行結(jié)果:[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]排列個數(shù):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>;}}運行結(jié)果:12341235123612371238123912439867987198729873987498759876total:3024106.全排列遞歸排列組合排列平方數(shù)若干不同的數(shù)字,排列組合后能產(chǎn)生多少個平方數(shù)？下面的代碼解決了這個問題。對于：1,6,9排列后,可產(chǎn)生3個平方數(shù)：169196961請閱讀下面的代碼,填寫缺失的部分〔下劃線部分〕。注意：請把填空的答案〔僅填空處的答案,不包括題面〕存入考生文件夾下對應(yīng)題號的"解答.txt"中即可。直接寫在題面中不能得分。*/publicclassT{publicstaticvoidf<int[]a,intn>{if<n==a.length-1>{intk=0;//把a(bǔ)里的數(shù)字組合為一個數(shù)字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.排列的個數(shù)計算3個A,2個B可以組成多少種排列的問題〔如：AAABB,AABBA〕是《組合數(shù)學(xué)》的研究領(lǐng)域。但有些情況下,也可以利用計算機(jī)計算速度快的特點通過巧妙的推理來解決問題。下列的程序計算了m個A,n個B可以組合成多少個不同排列的問題。請完善它。*/publicclass排列的個數(shù){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>>;}}運行結(jié)果:10|||全排列李白打酒類型38.全排列奇怪的比賽〔低碳生活大獎賽〕某電視臺舉辦了低碳生活大獎賽。題目的計分規(guī)則相當(dāng)奇怪：每位選手需要回答10個問題〔其編號為1到10〕,越后面越有難度。答對的,當(dāng)前分?jǐn)?shù)翻倍；答錯了則扣掉與題號相同的分?jǐn)?shù)〔選手必須回答問題,不回答按錯誤處理〕。每位選手都有一個起步的分?jǐn)?shù)為10分。某獲勝選手最終得分剛好是100分,如果不讓你看比賽過程,你能推斷出他〔她〕哪個題目答對了,哪個題目答錯了嗎？如果把答對的記為1,答錯的記為0,則10個題目的回答情況可以用僅含有1和0的串來表示。例如：0010110011就是可能的情況。你的任務(wù)是算出所有可能情況。每個答案占一行。publicclassTi_38{publicstaticvoidmain<String[]args>{//TODOAuto-generatedmethodstub//定義一個10個數(shù)的數(shù)組保存十個題目intx[]=newint[10];f<x,0>; }privatestaticvoidf<int[]x,inti>{//TODOAuto-generatedmethodstiub//如果i大于數(shù)組的長度就說明數(shù)組賦值完畢開始輸出if<i>=x.length>{show<x>;return; }//調(diào)用兩次遞歸實現(xiàn)全排列逐步填充x[i]=0;f<x,i+1>; x[i]=1;f<x,i+1>; }//按要求打印數(shù)組privatestaticvoidshow<intx[]>{//TODOAuto-generatedmethodstubints=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國人坐成一排。要求不能使連續(xù)的3個人是同一個國籍。求所有不同方案的總數(shù)？*/publicclassT13{staticintsum=0;//不同方案總個數(shù)//檢查是否有同一國人連續(xù)3個publicstaticbooleancheck<char[]c>{intcount=1;//初始個數(shù)for<inti=0;i<c.length-1;i++>{if<c[i]==c[i+1]>{count++;}else{count=1;//初始個數(shù)}if<count>=3>returntrue;}returnfalse;}//全排列publicstaticvoidallSort<char[]c,intstart,intend>{if<start>end>{if<!check<c>>{//檢查是否有同一國人連續(xù)3個sum++;//不同方案總個數(shù)加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次冪的展開式中各項的系數(shù)很有規(guī)律,對于n=2,3,4時分別是：121,1331,14641。這些系數(shù)構(gòu)成了著名的楊輝三角形：11112113311464115101051下列的程序給出了計算第m層的第n個系數(shù)的計算方法,試完善之〔m,n都從0算起〕。 publicstaticintf<intm,intn> { if<m==0>return1; if<n==0||n==m>return1; return___f<n-1>+f<n-2>_______________________; } IV經(jīng)典案例43.漢諾塔思想遞歸泊松分酒泊松是法國數(shù)學(xué)家、物理學(xué)家和力學(xué)家。他一生致力科學(xué)事業(yè),成果頗多。有許多著名的公式定理以他的名字命名,比如概率論中著名的泊松分布。有一次閑暇時,他提出過一個有趣的問題,后稱為："泊松分酒"。在我國古代也提出過類似問題,遺憾的是沒有進(jìn)行徹底探索,其中流傳較多是："韓信走馬分油"問題。有3個容器,容量分別為12升,8升,5升。其中12升中裝滿油,另外兩個空著。要求你只用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個數(shù)據(jù),分別表示12,8,6升容器中的油量第一行表示初始狀態(tài),第二行表示把12升倒入8升容器后的狀態(tài),第三行是8升倒入5升,...當(dāng)然,同一個題目可能有多種不同的正確操作步驟。本題目的要求是,請你編寫程序,由用戶輸入：各個容器的容量,開始的狀態(tài),和要求的目標(biāo)油量,程序則通過計算輸出一種實現(xiàn)的步驟〔不需要找到所有可能的方法〕。如果沒有可能實現(xiàn),則輸出："不可能"。例如,用戶輸入： 12,8,5,12,0,0,6用戶輸入的前三個數(shù)是容器容量〔由大到小〕,接下來三個數(shù)是三個容器開始時的油量配置,最后一個數(shù)是要求得到的油量〔放在哪個容器里得到都可以〕則程序可以輸出〔答案不唯一,只驗證操作可行性〕： 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;//目標(biāo)酒量publicWine<>{}publicvoidBacktrack<intcur1,intcur2,intcur3>{//輸出當(dāng)前的三個瓶子中的情況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中的酒倒進(jìn)瓶子三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>{//當(dāng)瓶子2是空的時候從瓶子1倒入酒if<cur1>=b2>//當(dāng)?shù)谝粋€瓶子大于5的時候,就把第二個瓶子倒?jié)MBacktrack<cur1-b2,b2,cur3>;else//如果第一個瓶子小于5的時候就全部倒進(jìn)第二個瓶子Backtrack<0,cur1,cur3>;}}}51.漢諾塔類型振興中華小明參加了學(xué)校的趣味運動會,其中的一個項目是：跳格子。地上畫著一些格子,每個格子里寫一個字,如下所示：〔也可參見p1.jpg〕從我做起振我做起振興做起振興中起振興中華比賽時,先站在左上角的寫著"從"字的格子里,可以橫向或縱向跳到相鄰的格子里,但不能跳到對角的格子或其它位置。一直要跳到"華"字結(jié)束。要求跳過的路線剛好構(gòu)成"從我做起振興中華"這句話。請你幫助小明算一算他一共有多少種可能的跳躍路線呢？答案是一個整數(shù),請通過瀏覽器直接提交該數(shù)字。注意：不要提交解答過程,或其它輔助說明類的內(nèi)容。/**振興中華*/publicclassTest002{privatestaticchar[][]a={{'從','我','做','起','振'},{'我','做','起','振','興'},{'做','起','振','興','中'},{'起','振','興','中','華'}};privatestaticintcount;//計數(shù)變量publicstaticvoidmain<String[]args>{count=0;char[]b=newchar[8];jump<0,0,0,b>;System.out.println<count>;}/***模擬小明跳躍格子的遞歸方法**paramstep跳格子經(jīng)過的步數(shù),X圍是0-7*paramx向下跳的位置,X圍是0-3*paramy向右跳的位置,X圍是0-4*paramb暫存跳過路線的一維數(shù)組*/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>;//向右跳}//檢查數(shù)組內(nèi)容是"從我做起振興中華"privatestaticbooleancheck<char[]b>{if<"從我做起振興中華".equals<String.valueOf<b>>>{returntrue;}else{returnfalse;}}}44.斐波納契數(shù)列黃金分割數(shù)黃金分割數(shù)0.618與美學(xué)有重要的關(guān)系。舞臺上報幕員所站的位置大約就是舞臺寬度的0.618處,墻上的畫像一般也掛在房間高度的0.618處,甚至股票的波動據(jù)說也能找到0.618的影子黃金分割數(shù)是個無理數(shù),也就是無法表示為兩個整數(shù)的比值。0.618只是它的近似值,其真值可以通過對5開方減去1再除以2來獲得,我們?nèi)∷囊粋€較精確的近似值：0.618034有趣的是,一些簡單的數(shù)列中也會包含這個無理數(shù),這很令數(shù)學(xué)家震驚！134711182947稱為"魯卡斯隊列"。它后面的每一個項都是前邊兩項的和。如果觀察前后兩項的比值,即：1/3,3/4,4/7,7/11,11/18...會發(fā)現(xiàn)它越來越接近于黃金分割數(shù)！你的任務(wù)就是計算出從哪一項開始,這個比值四舍五入后已經(jīng)達(dá)到了與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次冪的展開式中各項的系數(shù)很有規(guī)律,對于n=2,3,4時分別是：121,1331,14641。這些系數(shù)構(gòu)成了著名的楊輝三角形：11112113311464115101051下列的程序給出了計算第m層的第n個系數(shù)的計算方法,試完善之〔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。本題的任務(wù)就是從標(biāo)準(zhǔn)輸入獲得一個整數(shù)n<1<n<100>程序則生成嵌套著的回字型星號方框。其最外層方框的邊長為n例如：輸入：5程序輸出：*****************輸入：6程序輸出：*************************/importjava.util.Scanner;publicclassDemo04{//顯示數(shù)組publicstaticvoidshow<char[][]c>{for<char[]x:c>{for<chary:x>{System.out.print<y>;}System.out.println<>;}}//初始化數(shù)組為空數(shù)組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>;//矩陣X圍縮小2,起始賦值位置加2}publicstaticvoidmain<String[]args>{Scannerscan=newScanner<System.in>;System.out.println<"輸入獲得一個整數(shù)n<1<n<100>">;intn=scan.nextInt<>;char[][]c=newchar[n][n];init<c>;//初始化數(shù)組為空數(shù)組oper<c,n,0>;//賦值show<c>;//顯示數(shù)組}}VI其他10回溯法求21位數(shù)的水仙花數(shù)水仙花數(shù)是指一個n位數(shù)<n≥3>,它的每個位上的數(shù)字的n次冪之和等于它本身?！怖纾?^3+5^3+3^3=153〕/**求21位數(shù)的水仙花數(shù)*/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;//確定各數(shù)字出現(xiàn)的多少次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;}//對當(dāng)前位置所有可能進(jìn)行枚舉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<>;//程序結(jié)束時間System.out.println<<endTime-startTime>/1000f+"秒">;//運行總時間}}20.方陣順時針旋轉(zhuǎn)遞歸求解比迭代求解更簡單對一個方陣轉(zhuǎn)置,就是把原來的行號變列號,原來的列號變行號例如,如下的方陣：12345678910111213141516轉(zhuǎn)置后變?yōu)椋?5913261014371115481216但,如果是對該方陣順時針旋轉(zhuǎn)〔不是轉(zhuǎn)置〕,卻是如下結(jié)果：13951141062151173161284publicclassDemo03{//矩陣順時針旋轉(zhuǎn)publicstaticvoidrotation<int[][]n,int[][]m,inti,intj>{intt=j;//標(biāo)記最后一行的位置if<i>=n.length>return;for<intk=0;k<n.length;k++>{m[i][k]=n[j--][i];//解決一行}rotation<n,m,++i,t>;//遞歸解決下一行}//輸出矩陣publicstaticvoidprint<int[][]t>{for<int[]x:t>{for<inty:x>{System.out.print<y+"\t">;}System.out.println<>;}}publicstaticvoidmain<String[]args>{int[][]n={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};print<n>;//顯示原矩陣intlen=n.length;int[][]m=newint[len][len];//目標(biāo)矩陣rotation<n,m,0,len-1>;//矩陣順時針旋轉(zhuǎn)System.out.println<"順時針旋轉(zhuǎn)結(jié)果:">;print<m>;//顯示目標(biāo)矩陣}}}639.遞歸益智玩具<漢諾塔>經(jīng)典算法〔主要是原理弄懂〕漢諾塔〔又稱河內(nèi)塔〕問題是源于印度一個古老傳說的益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子,在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上<可以借助第三根柱子做緩沖>。并且規(guī)定,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤。如圖[1.jpg]是現(xiàn)代"山寨"版的該玩具。64個圓盤太多了,所以減為7個,金剛石和黃金都以木頭代替了但道理是相同的。據(jù)說完成大梵天的命令需要太多的移動次數(shù),以至被認(rèn)為完成之時就是世界末日！你的任務(wù)是精確計算出到底需要移動多少次。很明顯,如果只有2個圓盤,需要移動3次。圓盤數(shù)為3,則需要移動7次。那么64個呢？publicstaticvoidmoveDish<intlevel,charA,charB,charC>{if<level==1>{System.out.println<"from:"+A+"1號to:"+C>;}else{moveDish<level-1,A,C,B>;System.out.println<"from:"+A+""+level+"號to:"+C>;moveDish<level-1,A,B,C>;}}publicstaticvoidmain<String[]args>{intnDisks=5;moveDish<nDisks,'A','B','C'>;}52.遞歸排序有理數(shù)類有理數(shù)就是可以表示為兩個整數(shù)的比值的數(shù)字。一般情況下,我們用近似的小數(shù)表示。但有些時候,不允許出現(xiàn)誤差,必須用兩個整數(shù)來表示一個有理數(shù)。這時,我們可以建立一個"有理數(shù)類",下面的代碼初步實現(xiàn)了這個目標(biāo)。為了簡明,它只提供了加法和乘法運算。classRational{ privatelongra; privatelongrb; privatelonggcd<longa,longb>{ if<b==0>returna; returngcd<b,a%b>; } publicRational<longa,longb>{ ra=a; rb=b; longk=gcd<ra,rb>; if<k>1>{//需要約分 ra/=k; rb/=k; } } //加法 publicRationaladd<Rationalx>{ returnnewRational<this.ra*x.rb+this.rb+x.ra,this.rb*x.rb>;//填空位置 } //乘法 publicRationalmul<Rationalx>{ returnnewRational<ra*x.ra,rb*x.rb>; } publicStringtoString<>{ if<rb==1>return""+ra; returnra+"/"+rb; }}使用該類的示例： Rationala=newRational<1,3>; Rationalb=newRational<1,6>; Rationalc=a.add<b>; System.out.println<a+"+"+b+"="+c>;請分析代碼邏輯,并推測劃線處的代碼,通過網(wǎng)頁提交52.遞歸有理數(shù)類有理數(shù)就是可以表示為兩個整數(shù)的比值的數(shù)字。一般情況下,我們用近似的小數(shù)表示。但有些時候,不允許出現(xiàn)誤差,必須用兩個整數(shù)來表示一個有理數(shù)。這時,我們可以建立一個"有理數(shù)類",下面的代碼初步實現(xiàn)了這個目標(biāo)。為了簡明,它只提供了加法和乘法運算。publicclassTest002{publicstaticvoidmain<String[]args>{longstart=System.currentTimeMillis<>; Rationala=newRational<1,3>; Rationalb=newRational<1,6>; Rationalc=a.mul<b>; System.out.println<a+"+"+b+"="+c>;longend=System.currentTimeMillis<>; System.out.print