JAVA递归试题库.doc

递归一 基础知识 递归中每次循环都必须使问题规模有所缩小。 递归操作的每两步都是有紧密的联系，如在“递归”的“归操作时”，前一次的输出就是后一次的输入。 当子问题的规模足够小时，必须能够直接求出该规模问题的解，其实也就是必须要有结束递归的条件。 二 递归要解决什么问题呢?1 不同的方法体之间的传递public static void main(String args) g();private static void g() f(3);private static int f(int i) return i+k(i);private static int k(int i) return i;2 相同的方法体 不同方法名之间的传递public static void main(String args) int i = g(4);System.out.println(i);private static int g(int i) return i*g1(3);private static int g1(int i) return i+g2(2);private static int g2(int i) return i*g3(1);private static int g3(int i) return i; 3 看一看得出 其实功能相同所以直接使用递归public static void main(String args) int i = g(4);System.out.println(i);private static int g(int i) if(i = 1)return i;return i*g(i-1); 根据 2 与 3 的比较明显的看得出 使用递归明显的缩短了代码的使用量 4 递归的使用框架返回值类型 f(形参)if(终止条件)return 结果;elsereturn f(形参递减或者递增);5递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。（Fibonacci函数）(2)问题解法按递归算法实现。这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如汉诺塔(3)数据的结构形式是按递归定义的。如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。三 经典 案例1 斐波纳契数列 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n2，nN*）public static int f(int x)if(x = 0)return 0;if(x = 1 | x = 2)return 1;return f(x-1)+f(x-2);2 阶乘public static int f(int x)if(x = 1)return 1;elsereturn x*f(x-1);3全排列4汉诺塔public static void hanoi(int n, char origin, char assist, char destination) 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”中即可。 */思路 就是每次保存最后一位并且放在第一个上返回或者 每次保存第一个并且放在最后一个 public class Demo03 public static String reverseString(String s)if(s.length()=0 & cend) return; / 填空 System.out.println(begin); f(begin + 1, end); public static void main(String args) f(0, 9); 运行结果:0 1 2 3 4 5 6 7 8 9113.递归定义 题意理解 公交车标价 * 公交车票价为5角。假设每位乘客只持有两种币值的货币：5角、1元。 * 再假设持有5角的乘客有m人，持有1元的乘客有n人。由于特殊情况，开始的时候，售票员没有零钱可找。 * 我们想知道这m+n名乘客以什么样的顺序购票则可以顺利完成购票过程。 * 显然，m =n的时候，有些情况也不行。比如，第一个购票的乘客就持有1元。 * 下面的程序计算出这m+n名乘客所有可能顺利完成购票的不同情况的组合数目。 * 注意：只关心5角和1元交替出现的次序的不同排列，持有同样币值的两名乘客交换位置并不算做一种新的情况来计数。 */ public class 公交车票价 / m: 持有5角币的人数 / n: 持有1元币的人数 / 返回：所有顺利完成购票过程的购票次序的种类数 public static int f(int m, int n) if (m end) return;System.out.println(begin);f(begin+1, end);public static void main(String args)f(0,9);II排列普通1 字符排序 全排列算法是这样的，如果给定N个不同字符，将这N个字符全排列，最终的结果将会是N!种。如：给定 A、B、C三个不同的字符，则结果为：ABC、ACB、BAC、BCA、CAB、CBA一共3!=3*2=6种情况。public class AllPermutationpublic static void main(String args)/使用递归完成全排列char source=new charA,B,C;char result=new charsource.length;allPermutation(0,source,result);/* * * param index当前考虑的数的下标(从0开始) * param source * param result */public static void allPermutation(int index,char source,char result)/当源数据中只有一个字符时，将该字符加入结果数组，并输出if(source.length=1)resultindex=source0;show(result);return ;/for(int i=0;iresult.length-index;i+)resultindex=sourcei;char newSource=getNewSource(source,sourcei);allPermutation(index+1, newSource,result);public static void show(char result)System.out.println(result);/* * 生成去掉指定字符的新源数据数组 * param source 原来的源数据数组 * param c 指定去掉的字符 * return */public static char getNewSource(char source,char c)char newSource=new charsource.length-1;for(int i=0,j=0;isource.length;i+)if(sourcei!=c)newSourcej=sourcei;j+;return newSource;42.全排列 递归 Stringbuffer警察智力训练 匪警请拨110,即使手机欠费也可拨通！ 为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！ 某批警察叔叔正在进行智力训练： 1 2 3 4 5 6 7 8 9 = 110; 请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67-89 是另一个可能的答案。 请你利用计算机的优势，帮助警察叔叔快速找到所有答案。 每个答案占一行。形如：12+34+56+7-8+9123+4+5+67-89. 已知的两个答案可以输出，但不计分。 各个答案的前后顺序不重要。 / 遍历所有情况 public static void fun(String v, int n) if(n=9) / 修改到最后一位符号时输出 check(v); else / 递归向后修改，数字 变为 数字加符号 fun(v.replace(n+, n+),n+1); fun(v.replace(n+, n+-),n+1); fun(v,n+1); / 验证 并 输出 public static void check(String str) String s = str.split(+); int sum = 0; for(String t:s) String sub = t.split(-); int num = Integer.parseInt(sub0); / 计算负数 for(int i=1;isub.length;i+) num -= Integer.parseInt(subi); sum += num; / 正数或负数结果 加到 总和上 if(sum = 110) System.out.println(str); public static void main(String args) String str = 123456789; fun(str,1); / 调用函数，从1开始修改 46算法 实现全排列递归算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列import java.util.Arrays;import java.util.List;import java.util.ArrayList;publicclassT06 / 输出publicstaticvoid print(List target)for(Object o: target)System.out.print(o);System.out.println();/ 递归排列publicstaticvoid sort(List datas,List target,int n)if(target.size()=n)print(target);return;for(int i=0;idatas.size();i+)List newDatas = new ArrayList(datas);List newTarget = new ArrayList(target);newTarget.add(newDatas.get(i);newDatas.remove(i);sort(newDatas,newTarget,n);/ 主函数publicstaticvoid main(String args)String s = a,b,c;sort(Arrays.asList(s),newArrayList(),s.length);运行结果：abcacbbacbcacabcba方法二：publicclassAllSortpublicstaticvoid perm(String buf,int start,int end) if(start=end)/当只要求对数组中一个字母进行全排列时，只要按该数组输出即可for(int i=0;i=end;i+) System.out.print(bufi); System.out.println(); else/多个字母全排列for(int i=start;i=end;i+) String temp=bufstart;/交换数组第一个元素与后续的元素 bufstart=bufi; bufi=temp;perm(buf,start+1,end);/后续元素递归全排列 temp=bufstart;/将交换后的数组还原 bufstart=bufi; bufi=temp; publicstaticvoid main(String args) String buf=a,b,c;perm(buf,0,buf.length-1); 运行结果：abcacbbacbcacbacab47.递归 字符串全排列字符串全排列publicclassT03/ 输出字符数组publicstaticvoid print(char arr)for(int i=0;iarr.length;i+)System.out.print(arri);System.out.println();/ 递归遍历publicstaticvoid perm(char arr,int start,int end)if(start=end)print(arr);/ 输出elsefor(int i=start;i=end;i+)/ 换位char c = arrstart;arrstart = arri;arri = c;/ 递归perm(arr,start+1,end);/ 恢复数组原位c = arrstart;arrstart = arri;arri = c;/ 字符串转字符数组publicstaticvoid f(String s)char arr = s.toCharArray();perm(arr,0,arr.length-1);publicstaticvoid main(String args)String s = abc;f(s);运行结果：abcacbbacbcacbacab58.递归 全排列 带分数 100 可以表示为带分数的形式：100 = 3 + 69258 / 714还可以表示为：100 = 82 + 3546 / 197注意特征：带分数中，数字19分别出现且只出现一次（不包含0）。类似这样的带分数，100 有 11 种表示法。题目要求：从标准输入读入一个正整数N (N1000*1000)程序输出该数字用数码19不重复不遗漏地组成带分数表示的全部种数。注意：不要求输出每个表示，只统计有多少表示法！例如：用户输入：100程序输出：11再例如：用户输入：105程序输出：6资源约定：峰值内存消耗（含虚拟机） 64MCPU消耗 3000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入.”的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。public class MyTest private static Set all = new HashSet(); private static Set temp1 = new HashSet(); private static Set temp2 = new HashSet(); public static void main(String args) for(int i= 1; i9876; i+) all.clear(); if(isDuplicate(i, temp1) continue; for(int j = 2; j100; j+) if(!isDuplicate(j*i, temp1) int y = 100-j; if(!isDuplicate(y, temp2) & all.size()=9) System.out.println(100 + = + y + + + j*i + / + i); else all.removeAll(temp1); private static boolean isDuplicate(int n, Set temp) temp.clear(); int i = 0; boolean flag = false; while(n0) int x = 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); return flag; 92. 全排列 排列组合 数组列表 m个字符的n个字符排列/* * 19个数中的n位数全排列 */ static int count = 0; / 总个数 /* * 全排列 * param lis 记录组合 * param start 为09(lis所用的下标) * param end 为9 */ public static void f(List lis,int start) if(start=lis.size() System.out.println(lis); / 输出排列组合 count+; / 计数 return ; for(int i=1;i=9;i+) if(!lis.contains(i) lis.set(start, i); / 修改元素 else continue; f(lis,start+1); / 递归修改每个元素 lis.set(start, -1); / 还原 public static void main(String args) int n = 5; / 19个数中选5个全排列 List lis = new ArrayList(); for(int i=0;in;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 方法二:对以上程序的 (数字排列)扩展为(字符排列)看下程序:import java.util.ArrayList; import java.util.List; public class T13 static int count = 0; / 记录个数 / m排n全排列 public static void f(List lis,char c,int n) if(n=0) count+; / 记录个数 System.out.println(lis); / 输出 return ; for(int i=0;ic.length;i+) if(!lis.contains(ci) / 不包含,则添加 lis.set(lis.size()-n, ci); else / 否则跳过 continue; f(lis,c,n-1); / 递归 lis.set(lis.size()-n, 0); / 还原 public static void main(String args) long star = System.currentTimeMillis(); int n = 3; / 任选n个字符的排列组合 char c = 123456789.toCharArray(); / 要排列的字符 List lis = new ArrayList(); for(int i=0;in;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个字符排列 */ import java.util.ArrayList; import java.util.List; public class m个字符的n个字符排列 private static char is = new char 1, 2, 3, 4, 5, 6, 7, 8, 9; private static int total; private static int m = 4; private void plzh(String s, List iL, int m) if(m = 0) System.out.println(s); total+; return; List iL2; for(int i = 0; i is.length; i+) iL2 = new ArrayList(); iL2.addAll(iL); if(!iL.contains(i) String str = s + isi; iL2.add(i); plzh(str, iL2, m-1); public static void main(String args) List iL = new ArrayList(); new m个字符的n个字符排列().plzh(, iL, m); System.out.println(total : + total); 运行结果:1234 1235 1236 1237 1238 1239 1243 . . . 9867 9871 9872 9873 9874 9875 9876 total : 3024 106.全排列 递归 排列组合 排列平方数 若干不同的数字，排列组合后能产生多少个平方数？ 下面的代码解决了这个问题。 对于：1,6,9 排列后，可产生3个平方数： 169 196 961 请阅读下面的代码，填写缺失的部分（下划线部分）。 注意：请把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。 直接写在题面中不能得分。 */ public class Tpublic static void f(int a, int n) if (n = a.length - 1) int k = 0; / 把a里的数字组合为一个数字k for(int i=0; ia.length; i+) k = k*10 + ai; / 填空1 int m = (int) (Math.sqrt(k)+0.5); if (m * m = k) System.out.println(k); return; / 全排列 for (int i = n; i = x.length)show(x);return;/ 调用两次递归实现全排列 逐步填充xi = 0;f(x,i+1);xi = 1;f(x,i+1);/ 按要求打印数组private static void show(int x) / TODO Auto-generated method stubint s = 10;for(int i=0; i=x.length-1; i+)if(xi = 0)s -= (i+1);if(xi = 1)s *= 2;if(s = 100)for(int i:x)System.out.print(i);System.out.println();91. 全排列 李白打酒 排列组合排座位/* 排座位 要安排：3个A国人，3个B国人，3个C国人坐成一排。 要求不能使连续的3个人是同一个国籍。 求所有不同方案的总数？ */ public class