JAVA递归试题库完整

./递归一基础知识<1>递归中每次循环都必须使问题规模有所缩小。<2>递归操作的每两步都是有紧密的联系,如在"递归"的"归操作时",前一次的输出就是后一次的输入。<3>当子问题的规模足够小时,必须能够直接求出该规模问题的解,其实也就是必须要有结束递归的条件。二递归要解决什么问题呢? 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.递归的定义试数连续数以下程序打印出0~9的数字,请补充缺少的代码。*/publicclass递归连续数{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是另一个可能的答案。请你利用计算机的优势,帮助警察叔叔快速找到所有答案。每个答案占一行。形如：12+34+56+7-8+9123+4+5+67-89已知的两个答案可以输出,但不计分。各个答案的前后顺序不重要。//遍历所有情况publicstaticvoidfun<Stringv,intn>{if<n==9>{//修改到最后一位符号时输出check<v>;}else{//递归向后修改,数字变为数字加符号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]>;//计算负数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="123456789";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>{//当只要求对数组中一个字母进行全排列时,只要按该数组输出即可for<inti=0;i<=end;i++>{ System.out.print<buf[i]>; } System.out.println<>; }else{//多个字母全排列for<inti=start;i<=end;i++>{ Stringtemp=buf[start];//交换数组第一个元素与后续的元素 buf[start]=buf[i]; buf[i]=temp;perm<buf,start+1,end>;//后续元素递归全排列 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种表示法。题目要求：从标准输入读入一个正整数N<N<1000*1000>程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。注意：不要求输出每个表示,只统计有多少表示法！例如：用户输入：100程序输出：11再例如：用户输入：105程序输出：6资源约定：峰值内存消耗〔含虚拟机〕<64MCPU消耗<3000ms请严格按要求输出,不要画蛇添足地打印类似："请您输入..."的多余内容。所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。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="123456789".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>;}}运行结果:12341235123612371238123912439867987198729873987498759876total: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.全排列奇怪的比赛〔低碳生活大奖赛〕某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：每位选手需要回答10个问题〔其编号为1到10〕,越后面越有难度。答对的,当前分数翻倍；答错了则扣掉与题号相同的分数〔选手必须回答问题,不回答按错误处理〕。每位选手都有一个起步的分数为10分。某获胜选手最终得分刚好是100分,如果不让你看比赛过程,你能推断出他〔她〕哪个题目答对了,哪个题目答错了吗？如果把答对的记为1,答错的记为0,则10个题目的回答情况可以用仅含有1和0的串来表示。例如：0010110011就是可能的情况。你的任务是算出所有可能情况。每个答案占一行。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>; }//按要求打印数组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国人坐成一排。要求不能使连续的3个人是同一个国籍。求所有不同方案的总数？*/publicclassT13{staticintsum=0;//不同方案总个数//检查是否有同一国人连续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>>{//检查是否有同一国人连续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次幂的展开式中各项的系数很有规律,对于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.汉诺塔思想递归泊松分酒泊松是法国数学家、物理学家和力学家。他一生致力科学事业,成果颇多。有许多著名的公式定理以他的名字命名,比如概率论中著名的泊松分布。有一次闲暇时,他提出过一个有趣的问题,后称为："泊松分酒"。在我国古代也提出过类似问题,遗憾的是没有进行彻底探索,其中流传较多是："韩信走马分油"问题。有3个容器,容量分别为12升,8升,5升。其中12升中装满油,另外两个空着。要求你只用3个容器操作,最后使得某个容器中正好有6升油。下面的列表是可能的操作状态记录： 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升容器中的油量第一行表示初始状态,第二行表示把12升倒入8升容器后的状态,第三行是8升倒入5升,...当然,同一个题目可能有多种不同的正确操作步骤。本题目的要求是,请你编写程序,由用户输入：各个容器的容量,开始的状态,和要求的目标油量,程序则通过计算输出一种实现的步骤〔不需要找到所有可能的方法〕。如果没有可能实现,则输出："不可能"。例如,用户输入： 12,8,5,12,0,0,6用户输入的前三个数是容器容量〔由大到小〕,接下来三个数是三个容器开始时的油量配置,最后一个数是要求得到的油量〔放在哪个容器里得到都可以〕则程序可以输出〔答案不唯一,只验证操作可行性〕： 12,0,0 4,8,0 4,3,5 9,3,0 9,0,3 1,8,3 1,6,5每一行表示一个操作过程中的油量状态。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的时候,就把第二个瓶子倒满Backtrack<cur1-b2,b2,cur3>;else//如果第一个瓶子小于5的时候就全部倒进第二个瓶子Backtrack<0,cur1,cur3>;}}}51.汉诺塔类型振兴中华小明参加了学校的趣味运动会,其中的一个项目是：跳格子。地上画着一些格子,每个格子里写一个字,如下所示：〔也可参见p1.jpg〕从我做起振我做起振兴做起振兴中起振兴中华比赛时,先站在左上角的写着"从"字的格子里,可以横向或纵向跳到相邻的格子里,但不能跳到对角的格子或其它位置。一直要跳到"华"字结束。要求跳过的路线刚好构成"从我做起振兴中华"这句话。请你帮助小明算一算他一共有多少种可能的跳跃路线呢？答案是一个整数,请通过浏览器直接提交该数字。注意：不要提交解答过程,或其它辅助说明类的内容。/**振兴中华*/publicclassTest002{privatestaticchar[][]a={{'从','我','做','起','振'},{'我','做','起','振','兴'},{'做','起','振','兴','中'},{'起','振','兴','中','华'}};privatestaticintcount;//计数变量publicstaticvoidmain<String[]args>{count=0;char[]b=newchar[8];jump<0,0,0,b>;System.out.println<count>;}/***模拟小明跳跃格子的递归方法**paramstep跳格子经过的步数,X围是0-7*paramx向下跳的位置,X围是0-3*paramy向右跳的位置,X围是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...会发现它越来越接近于黄金分割数！你的任务就是计算出从哪一项开始,这个比值四舍五入后已经达到了与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次幂的展开式中各项的系数很有规律,对于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>;//矩阵X围缩小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转置后变为：15913261014371115481216但,如果是对该方阵顺时针旋转〔不是转置〕,却是如下结果：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>;//递归解决下一行}//输出矩阵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];//目标矩阵rotation<n,m,0,len-1>;//矩阵顺时针旋转System.out.println<"顺时针旋转结果:">;print<m>;//显示目标矩阵}}}639.递归益智玩具<汉诺塔>经典算法〔主要是原理弄懂〕汉诺塔〔又称河内塔〕问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上<可以借助第三根柱子做缓冲>。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。如图[1.jpg]是现代"山寨"版的该玩具。64个圆盘太多了,所以减为7个,金刚石和黄金都以木头代替了但道理是相同的。据说完成大梵天的命令需要太多的移动次数,以至被认为完成之时就是世界末日！你的任务是精确计算出到底需要移动多少次。很明显,如果只有2个圆盘,需要移动3次。圆盘数为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.递归排序有理数类有理数就是可以表示为两个整数的比值的数字。一般情况下,我们用近似的小数表示。但有些时候,不允许出现误差,必须用两个整数来表示一个有理数。这时,我们可以建立一个"有理数类",下面的代码初步实现了这个目标。为了简明,它只提供了加法和乘法运算。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>;请分析代码逻辑,并推测划线处的代码,通过网页提交52.递归有理数类有理数就是可以表示为两个整数的比值的数字。一般情况下,我们用近似的小数表示。但有些时候,不允许出现误差,必须用两个整数来表示一个有理数。这时,我们可以建立一个"有理数类",下面的代码初步实现了这个目标。为了简明,它只提供了加法和乘法运算。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