2023年JAVA遞歸試題庫(kù)

遞歸一基礎(chǔ)知識(shí) <1>遞歸中每次循環(huán)都必須使問(wèn)題規(guī)模有所縮小。<2>遞歸操作的每?jī)刹蕉际怯芯o密的聯(lián)系，如在“遞歸”的“歸操作時(shí)”，前一次的輸出就是后一次的輸入。<3>當(dāng)子問(wèn)題的規(guī)模足夠小時(shí)，必須可以直接求出該規(guī)模問(wèn)題的解，其實(shí)也就是必須要有結(jié)束遞歸的條件。 二遞歸要解決什么問(wèn)題呢? 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看一看得出其實(shí)功能相同所以直接使用遞歸 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遞歸算法一般用于解決三類問(wèn)題：(1)數(shù)據(jù)的定義是按遞歸定義的。（Fibonacci函數(shù)）(2)問(wèn)題解法按遞歸算法實(shí)現(xiàn)。這類問(wèn)題雖則自身沒(méi)有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比迭代求解更簡(jiǎn)樸，如漢諾塔(3)數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。如二叉樹、廣義表等，由于結(jié)構(gòu)自身固有的遞歸特性，則它們的操作可遞歸地描述。三經(jīng)典案例1斐波納契數(shù)列斐波那契數(shù)列（Fibonaccisequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：0、1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F（0）=0，F(xiàn)（1）=1，F(xiàn)（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)串。題意就是對(duì)字符串的反轉(zhuǎn)求一個(gè)串的反轉(zhuǎn)串的方法很多。下面就是其中的一種方法，代碼十分簡(jiǎn)潔（甚至有些神秘），請(qǐng)聰明的你通過(guò)給出的一點(diǎn)點(diǎn)線索補(bǔ)充缺少的代碼。把填空的答案（僅填空處的答案，不涉及題面）存入考生文獻(xiàn)夾下相應(yīng)題號(hào)的“解答.txt”中即可。*/思緒就是每次保存最后一位并且放在第一個(gè)上返回 或者每次保存第一個(gè)并且放在最后一個(gè)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); }}運(yùn)營(yíng)結(jié)果：654321132、遞歸把串s中第一個(gè)出現(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ù)字，請(qǐng)補(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);}}運(yùn)營(yíng)結(jié)果:0123456789113.遞歸定義題意理解公交車標(biāo)價(jià)*公交車票價(jià)為5角。假設(shè)每位乘客只持有兩種幣值的貨幣：5角、1元。*再假設(shè)持有5角的乘客有m人，持有1元的乘客有n人。由于特殊情況，開始的時(shí)候，售票員沒(méi)有零錢可找。*我們想知道這m+n名乘客以什么樣的順序購(gòu)票則可以順利完畢購(gòu)票過(guò)程。*顯然，m<n的時(shí)候，無(wú)論如何都不能完畢，m>=n的時(shí)候，有些情況也不行。比如，第一個(gè)購(gòu)票的乘客就持有1元。*下面的程序計(jì)算出這m+n名乘客所有也許順利完畢購(gòu)票的不同情況的組合數(shù)目。*注意：只關(guān)心5角和1元交替出現(xiàn)的順序的不同排列，持有同樣幣值的兩名乘客互換位置并不算做一種新的情況來(lái)計(jì)數(shù)。*/publicclass公交車票價(jià){//m:持有5角幣的人數(shù)//n:持有1元幣的人數(shù)//返回：所有順利完畢購(gòu)票過(guò)程的購(gòu)票順序的種類數(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));}運(yùn)營(yíng)結(jié)果:11934147遞歸以下程序打印出0~9的數(shù)字，請(qǐng)補(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個(gè)不同字符，將這N個(gè)字符全排列，最終的結(jié)果將會(huì)是N!種。如：給定A、B、C三個(gè)不同的字符，則結(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ù)中只有一個(gè)字符時(shí)，將該字符加入結(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本來(lái)的源數(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)練匪警請(qǐng)撥110,即使手機(jī)欠費(fèi)也可撥通！為了保障社會(huì)秩序，保護(hù)人民群眾生命財(cái)產(chǎn)安全，警察叔叔需要與罪犯斗智斗勇，因而需要經(jīng)常性地進(jìn)行體力訓(xùn)練和智力訓(xùn)練！某批警察叔叔正在進(jìn)行智力訓(xùn)練：123456789=110;請(qǐng)看上邊的算式，為了使等式成立，需要在數(shù)字間填入加號(hào)或者減號(hào)（可以不填，但不能填入其它符號(hào)）。之間沒(méi)有填入符號(hào)的數(shù)字組合成一個(gè)數(shù)，例如：12+34+56+7-8+9就是一種合格的填法；123+4+5+67-89是另一個(gè)也許的答案。請(qǐng)你運(yùn)用計(jì)算機(jī)的優(yōu)勢(shì)，幫助警察叔叔快速找到所有答案。每個(gè)答案占一行。形如：12+34+56+7-8+9123+4+5+67-89......已知的兩個(gè)答案可以輸出，但不計(jì)分。各個(gè)答案的前后順序不重要。//遍歷所有情況publicstaticvoidfun(Stringv,intn){if(n==9){//修改到最后一位符號(hào)時(shí)輸出check(v);}else{//遞歸向后修改，數(shù)字變?yōu)閿?shù)字加符號(hào)fun(v.replace(n+"",n+"+"),n+1);fun(v.replace(n+"",n+"-"),n+1);fun(v,n+1);}}//驗(yàn)證并輸出publicstaticvoidcheck(Stringstr){String[]s=str.split("[\\+]");intsum=0;for(Stringt:s){String[]sub=t.split("[\\-]");intnum=Integer.parseInt(sub[0]);//計(jì)算負(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="";fun(str,1);//調(diào)用函數(shù)，從1開始修改}46算法實(shí)現(xiàn)全排列遞歸算法：將數(shù)據(jù)分為兩部分，遞歸將數(shù)據(jù)從左側(cè)移右側(cè)實(shí)現(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); }}運(yùn)營(yíng)結(jié)果：abcacbbacbcacabcba方法二：publicclassAllSort{ publicstaticvoidperm(String[]buf,intstart,intend){ if(start==end){//當(dāng)只規(guī)定對(duì)數(shù)組中一個(gè)字母進(jìn)行全排列時(shí)，只要按該數(shù)組輸出即可 for(inti=0;i<=end;i++){ System.out.print(buf[i]); } System.out.println(); } else{//多個(gè)字母全排列 for(inti=start;i<=end;i++){ Stringtemp=buf[start];//互換數(shù)組第一個(gè)元素與后續(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);}}運(yùn)營(yíng)結(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); }}運(yùn)營(yíng)結(jié)果：abcacbbacbcacbacab58.遞歸全排列帶分?jǐn)?shù)100可以表達(dá)為帶分?jǐn)?shù)的形式：100=3+69258/714還可以表達(dá)為：100=82+3546/197注意特性：帶分?jǐn)?shù)中，數(shù)字1~9分別出現(xiàn)且只出現(xiàn)一次（不包含0）。類似這樣的帶分?jǐn)?shù)，100有11種表達(dá)法。題目規(guī)定：從標(biāo)準(zhǔn)輸入讀入一個(gè)正整數(shù)N(N<1000*1000)程序輸出該數(shù)字用數(shù)碼1~9不反復(fù)不漏掉地組成帶分?jǐn)?shù)表達(dá)的所有種數(shù)。注意：不規(guī)定輸出每個(gè)表達(dá)，只記錄有多少表達(dá)法！例如：用戶輸入：100程序輸出：11再例如：用戶輸入：105程序輸出：6資源約定：峰值內(nèi)存消耗（含虛擬機(jī)）<64MCPU消耗<3000ms請(qǐng)嚴(yán)格按規(guī)定輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入...”的多余內(nèi)容。所有代碼放在同一個(gè)源文獻(xiàn)中，調(diào)試通過(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.全排列排列組合數(shù)組列表m個(gè)字符的n個(gè)字符排列/**1~9個(gè)數(shù)中的n位數(shù)全排列*/staticintcount=0;//總個(gè)數(shù)/***全排列*@paramlis記錄組合*@paramstart為0~9(lis所用的下標(biāo))*@paramend為9*/publicstaticvoidf(List<Integer>lis,intstart){if(start>=lis.size()){System.out.println(lis);//輸出排列組合count++;//計(jì)數(shù)return;}for(inti=1;i<=9;i++){if(!lis.contains(i)){lis.set(start,i);//修改元素}else{continue;}f(lis,start+1);//遞歸修改每個(gè)元素lis.set(start,-1);//還原}}publicstaticvoidmain(String[]args){intn=5;//1~9個(gè)數(shù)中選5個(gè)全排列List<Integer>lis=newArrayList<Integer>();for(inti=0;i<n;i++){//初始化lis長(zhǎng)度lis.add(-1);}f(lis,0);//全排列System.out.println("總個(gè)數(shù):"+count);}運(yùn)營(yíng)結(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]總個(gè)數(shù):15120方法二:對(duì)以上程序的(數(shù)字排列)擴(kuò)展為(字符排列)看下程序:importjava.util.ArrayList;importjava.util.List;publicclassT13{staticintcount=0;//記錄個(gè)數(shù)//m排n全排列publicstaticvoidf(List<Character>lis,char[]c,intn){if(n==0){count++;//記錄個(gè)數(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{//否則跳過(guò)continue;}f(lis,c,n-1);//遞歸lis.set(lis.size()-n,'0');//還原}}publicstaticvoidmain(String[]args){longstar=System.currentTimeMillis();intn=3;//任選n個(gè)字符的排列組合char[]c="".toCharArray();//要排列的字符List<Character>lis=newArrayList<Character>();for(inti=0;i<n;i++){lis.add('0');//初始化lis的長(zhǎng)度}f(lis,c,n);//進(jìn)入全排列System.out.println("排列個(gè)數(shù):"+count);System.out.println("花費(fèi)時(shí)間:"+(System.currentTimeMillis()-star)+"毫秒");}}運(yùn)營(yíng)結(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]排列個(gè)數(shù):504花費(fèi)時(shí)間:19毫秒方法三:/**m個(gè)字符的n個(gè)字符排列*/importjava.util.ArrayList;importjava.util.List;publicclassm個(gè)字符的n個(gè)字符排列{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個(gè)字符的n個(gè)字符排列().plzh("",iL,m);System.out.println("total:"+total);}}運(yùn)營(yíng)結(jié)果:1234123512361237123812391243............9867987198729873987498759876total:3024106.全排列遞歸排列組合排列平方數(shù)若干不同的數(shù)字，排列組合后能產(chǎn)生多少個(gè)平方數(shù)？下面的代碼解決了這個(gè)問(wèn)題。對(duì)于：1,6,9排列后，可產(chǎn)生3個(gè)平方數(shù)：169196961請(qǐng)閱讀下面的代碼，填寫缺失的部分（下劃線部分）。注意：請(qǐng)把填空的答案（僅填空處的答案，不涉及題面）存入考生文獻(xiàn)夾下相應(yīng)題號(hào)的“解答.txt”中即可。直接寫在題面中不能得分。*/publicclassT{publicstaticvoidf(int[]a,intn){if(n==a.length-1){intk=0;//把a(bǔ)里的數(shù)字組合為一個(gè)數(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.排列的個(gè)數(shù)計(jì)算3個(gè)A，2個(gè)B可以組成多少種排列的問(wèn)題（如：AAABB,AABBA）是《組合數(shù)學(xué)》的研究領(lǐng)域。但有些情況下，也可以運(yùn)用計(jì)算機(jī)計(jì)算速度快的特點(diǎn)通過(guò)巧妙的推理來(lái)解決問(wèn)題。下列的程序計(jì)算了m個(gè)A，n個(gè)B可以組合成多少個(gè)不同排列的問(wèn)題。請(qǐng)完善它。*/publicclass排列的個(gè)數(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));}}運(yùn)營(yíng)結(jié)果:10|||全排列李白打酒類型38.全排列奇怪的比賽（低碳生活大獎(jiǎng)賽）某電視臺(tái)舉辦了低碳生活大獎(jiǎng)賽。題目的計(jì)分規(guī)則相稱奇怪：每位選手需要回答10個(gè)問(wèn)題（其編號(hào)為1到10），越后面越有難度。答對(duì)的，當(dāng)前分?jǐn)?shù)翻倍；答錯(cuò)了則扣掉與題號(hào)相同的分?jǐn)?shù)（選手必須回答問(wèn)題，不回答按錯(cuò)誤解決）。每位選手都有一個(gè)起步的分?jǐn)?shù)為10分。某獲勝選手最終得分剛好是100分，假如不讓你看比勝過(guò)程，你能推斷出他（她）哪個(gè)題目答對(duì)了，哪個(gè)題目答錯(cuò)了嗎？假如把答對(duì)的記為1，答錯(cuò)的記為0，則10個(gè)題目的回答情況可以用僅具有1和0的串來(lái)表達(dá)。例如：就是也許的情況。你的任務(wù)是算出所有也許情況。每個(gè)答案占一行。 publicclassTi_38{ publicstaticvoidmain(String[]args){ //TODOAuto-generatedmethodstub //定義一個(gè)10個(gè)數(shù)的數(shù)組保存十個(gè)題目 intx[]=newint[10]; f(x,0); } privatestaticvoidf(int[]x,inti){ //TODOAuto-generatedmethodstiub //假如i大于數(shù)組的長(zhǎng)度就說(shuō)明數(shù)組賦值完畢開始輸出 if(i>=x.length){ show(x); return; } //調(diào)用兩次遞歸實(shí)現(xiàn)全排列逐步填充 x[i]=0; f(x,i+1); x[i]=1; f(x,i+1); } //按規(guī)定打印數(shù)組 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個(gè)A國(guó)人，3個(gè)B國(guó)人，3個(gè)C國(guó)人坐成一排。規(guī)定不能使連續(xù)的3個(gè)人是同一個(gè)國(guó)籍。求所有不同方案的總數(shù)？*/publicclassT13{staticintsum=0;//不同方案總個(gè)數(shù)//檢查是否有同一國(guó)人連續(xù)3個(gè)publicstaticbooleancheck(char[]c){intcount=1;//初始個(gè)數(shù)for(inti=0;i<c.length-1;i++){if(c[i]==c[i+1]){count++;}else{count=1;//初始個(gè)數(shù)}if(count>=3)returntrue;}returnfalse;}//全排列publicstaticvoidallSort(char[]c,intstart,intend){if(start>end){if(!check(c)){//檢查是否有同一國(guó)人連續(xù)3個(gè)sum++;//不同方案總個(gè)數(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次冪的展開式中各項(xiàng)的系數(shù)很有規(guī)律，對(duì)于n=2，3，4時(shí)分別是：121，1331，14641。這些系數(shù)構(gòu)成了著名的楊輝三角形：11112113311464115101051下列的程序給出了計(jì)算第m層的第n個(gè)系數(shù)的計(jì)算方法，試完善之（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.漢諾塔思想遞歸泊松分酒泊松是法國(guó)數(shù)學(xué)家、物理學(xué)家和力學(xué)家。他一生致力科學(xué)事業(yè)，成果頗多。有許多著名的公式定理以他的名字命名，比如概率論中著名的泊松分布。有一次閑暇時(shí)，他提出過(guò)一個(gè)有趣的問(wèn)題，后稱為：“泊松分酒”。在我國(guó)古代也提出過(guò)類似問(wèn)題，遺憾的是沒(méi)有進(jìn)行徹底探索，其中流傳較多是：“韓信走馬分油”問(wèn)題。有3個(gè)容器，容量分別為12升，8升，5升。其中12升中裝滿油，此外兩個(gè)空著。規(guī)定你只用3個(gè)容器操作，最后使得某個(gè)容器中正好有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個(gè)數(shù)據(jù)，分別表達(dá)12，8，6升容器中的油量第一行表達(dá)初始狀態(tài)，第二行表達(dá)把12升倒入8升容器后的狀態(tài)，第三行是8升倒入5升，...當(dāng)然，同一個(gè)題目也許有多種不同的對(duì)的操作環(huán)節(jié)。本題目的規(guī)定是，請(qǐng)你編寫程序，由用戶輸入：各個(gè)容器的容量，開始的狀態(tài)，和規(guī)定的目的油量，程序則通過(guò)計(jì)算輸出一種實(shí)現(xiàn)的環(huán)節(jié)（不需要找到所有也許的方法）。假如沒(méi)有也許實(shí)現(xiàn)，則輸出：“不也許”。例如，用戶輸入： 12,8,5,12,0,0,6用戶輸入的前三個(gè)數(shù)是容器容量（由大到?。酉聛?lái)三個(gè)數(shù)是三個(gè)容器開始時(shí)的油量配置，最后一個(gè)數(shù)是規(guī)定得到的油量（放在哪個(gè)容器里得到都可以）則程序可以輸出（答案不唯一，只驗(yàn)證操作可行性）： 12,0,0 4,8,0 4,3,5 9,3,0 9,0,3 1,8,3 1,6,5每一行表達(dá)一個(gè)操作過(guò)程中的油量狀態(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){ //輸出當(dāng)前的三個(gè)瓶子中的情況System.out.println(cur1+""+cur2+""+cur3);//假如每一個(gè)瓶子都是6瓶就成功了if(cur1==m||cur2==m||cur3==m){System.out.print("findthekey！");return;}if(cur2!=0&&cur3!=b3){//瓶子2有酒并且瓶子三不滿 //假如瓶子2+瓶子3的不超過(guò)小瓶子的酒量就把瓶子2中的酒倒進(jìn)瓶子三if(cur2+cur3<=5)Backtrack(cur1,0,cur2+cur3);//否則就用瓶子2中的把瓶子3填滿瓶子1不動(dòng)elseBacktrack(cur1,cur2-(5-cur3),b3);}elseif(cur3==b3){//瓶子3滿的，這時(shí)就要把就倒入到瓶子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是空的時(shí)候從瓶子1倒入酒if(cur1>=b2)//當(dāng)?shù)谝粋€(gè)瓶子大于5的時(shí)候，就把第二個(gè)瓶子倒?jié)MBacktrack(cur1-b2,b2,cur3);else//假如第一個(gè)瓶子小于5的時(shí)候就所有倒進(jìn)第二個(gè)瓶子Backtrack(0,cur1,cur3);}}}51.漢諾塔類型振興中華小明參與了學(xué)校的趣味運(yùn)動(dòng)會(huì)，其中的一個(gè)項(xiàng)目是：跳格子。地上畫著一些格子，每個(gè)格子里寫一個(gè)字，如下所示：（也可參見p1.jpg）從我做起振我做起振興做起振興中起振興中華比賽時(shí)，先站在左上角的寫著“從”字的格子里，可以橫向或縱向跳到相鄰的格子里，但不能跳到對(duì)角的格子或其它位置。一直要跳到“華”字結(jié)束。規(guī)定跳過(guò)的路線剛好構(gòu)成“從我做起振興中華”這句話。請(qǐng)你幫助小明算一算他一共有多少種也許的跳躍路線呢？答案是一個(gè)整數(shù)，請(qǐng)通過(guò)瀏覽器直接提交該數(shù)字。注意：不要提交解答過(guò)程，或其它輔助說(shuō)明類的內(nèi)容。/**振興中華*/publicclassTest002{privatestaticchar[][]a={{'從','我','做','起','振'},{'我','做','起','振','興'},{'做','起','振','興','中'},{'起','振','興','中','華'}};privatestaticintcount;//計(jì)數(shù)變量publicstaticvoidmain(String[]args){count=0;char[]b=newchar[8];jump(0,0,0,b);System.out.println(count);}/***模擬小明跳躍格子的遞歸方法**@paramstep跳格子通過(guò)的步數(shù)，范圍是0-7*@paramx向下跳的位置，范圍是0-3*@paramy向右跳的位置，范圍是0-4*@paramb暫存跳過(guò)路線的一維數(shù)組*/privatestaticvoidjump(intstep,intx,inty,char[]b){//*******遞歸出口**********if(x>3){return;}if(y>4){return;}if(step>7){return;}//記錄跳過(guò)的字b[step]=a[x][y];if(step==7){//剛好走到8個(gè)字的位置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)系。舞臺(tái)上報(bào)幕員所站的位置大約就是舞臺(tái)寬度的0.618處，墻上的畫像一般也掛在房間高度的0.618處，甚至股票的波動(dòng)據(jù)說(shuō)也能找到0.618的影子....黃金分割數(shù)是個(gè)無(wú)理數(shù)，也就是無(wú)法表達(dá)為兩個(gè)整數(shù)的比值。0.618只是它的近似值，其真值可以通過(guò)對(duì)5開方減去1再除以2來(lái)獲得，我們?nèi)∷囊粋€(gè)較精確的近似值：0.618034有趣的是，一些簡(jiǎn)樸的數(shù)列中也會(huì)包含這個(gè)無(wú)理數(shù)，這很令數(shù)學(xué)家震驚！134711182947....稱為“魯卡斯隊(duì)列”。它后面的每一個(gè)項(xiàng)都是前邊兩項(xiàng)的和。假如觀測(cè)前后兩項(xiàng)的比值，即：1/3,3/4,4/7,7/11,11/18...會(huì)發(fā)現(xiàn)它越來(lái)越接近于黃金分割數(shù)！你的任務(wù)就是計(jì)算出從哪一項(xiàng)開始，這個(gè)比值四舍五入后已經(jīng)達(dá)成了與0.618034一致的精度。請(qǐng)寫出該比值。格式是：分子/分母。比如：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次冪的展開式中各項(xiàng)的系數(shù)很有規(guī)律，對(duì)于n=2，3，4時(shí)分別是：121，1331，14641。這些系數(shù)構(gòu)成了著名的楊輝三角形：11112113311464115101051下列的程序給出了計(jì)算第m層的第n個(gè)系數(shù)的計(jì)算方法，試完善之（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填充問(wèn)題82.遞歸打印回型嵌套/*************************************************************************觀測(cè)這個(gè)圖形，它是由一系列正方形的星號(hào)方框嵌套而成。在上邊的例子中，最外方框的邊長(zhǎng)為11。本題的任務(wù)就是從標(biāo)準(zhǔn)輸入獲得一個(gè)整數(shù)n(1<n<100)程序則生成嵌套著的回字型星號(hào)方框。其最外層方框的邊長(zhǎng)為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);//矩陣范圍縮小2,起始賦值位置加2}publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);System.out.println("輸入獲得一個(gè)整數(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ù)是指一個(gè)n位數(shù)(n≥3)，它的每個(gè)位上的數(shù)字的n次冪之和等于它自身。（例如：1^3+5^3+3^3=153）/**求21位數(shù)的水仙花數(shù)*/importjava.math.BigInteger;publicclassDemo01_BigInteger{//求每個(gè)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;}//對(duì)當(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();//程序開始時(shí)間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é)束時(shí)間System.out.println((endTime-startTime)/1000f+"秒");//運(yùn)營(yíng)總時(shí)間}}20.方陣順時(shí)針旋轉(zhuǎn)遞歸求解比迭代求解更簡(jiǎn)樸對(duì)一個(gè)方陣轉(zhuǎn)置，就是把本來(lái)的行號(hào)變列號(hào)，本來(lái)的列號(hào)變行號(hào)例如，如下的方陣：12345678910111213141516轉(zhuǎn)置后變?yōu)椋?5913261014371115481216但，假如是對(duì)該方陣順時(shí)針旋轉(zhuǎn)（不是轉(zhuǎn)置），卻是如下結(jié)果：13951141062151173161284publicclassDemo03{//矩陣順時(shí)針旋轉(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);//遞歸解決下一行}//輸出矩陣publicstaticvo