JAVA遞歸試題庫

1、遞歸一 基礎(chǔ)知識(shí)<1> 遞歸中每次循環(huán)都必須使問題規(guī)模有所縮小。 <2> 遞歸操作的每兩步都是有緊密的聯(lián)系，如在“遞歸”的“歸操作時(shí)”，前一次的輸出就是后一次的輸入。<3> 當(dāng)子問題的規(guī)模足夠小時(shí)，必須能夠直接求出該規(guī)模問題的解，其實(shí)也就是必須要有結(jié)束遞歸的條件。 二 遞歸要解決什么問題呢?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 sta

2、tic 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 看一看得出 其實(shí)功能相

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); 根據(jù) 2 與 3 的比較明顯的看得出 使用遞歸明顯的縮短了代碼的使用量 4 遞歸的使用框架返回值類型 f(形參)if(終止條件)return 結(jié)果;elsereturn f(形參遞減或者遞增);5遞歸算法一般用于解決三類問題：(1)數(shù)據(jù)的定義是按遞歸定義的。（Fibonacci函數(shù)）(2)問題解法按遞歸算法實(shí)現(xiàn)

4、。這類問題雖則本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比迭代求解更簡單，如漢諾塔(3)數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。如二叉樹、廣義表等，由于結(jié)構(gòu)本身固有的遞歸特性，則它們的操作可遞歸地描述。三 經(jīng)典 案例1 斐波納契數(shù)列 斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(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)（n2，nN*）public static int

5、 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 + "->

6、;" + 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)串的方法很多。下面就是其中的一種方法，代碼十分簡潔（

7、甚至有些神秘），請(qǐng)聰明的你通過給出的一點(diǎn)點(diǎn)線索補(bǔ)充缺少的代碼。把填空的答案（僅填空處的答案，不包括題面）存入考生文件夾下對(duì)應(yīng)題號(hào)的“解答.txt”中即可。 */思路 就是每次保存最后一位并且放在第一個(gè)上返回或者 每次保存第一個(gè)并且放在最后一個(gè) public class Demo03 public static String reverseString(String s)if(s.length()<2|s=null) return s;/每一次將第一位放在最后，將第二位放在倒數(shù)第二位然后進(jìn)行遞歸return reverseString(s.substring(1)+s.charAt(0);

8、/ return s.charAt(s.length()-1) +reverseString(s.substring(0,s.length()-1);public static void main(String args)String s = "123456"String ss = reverseString(s);System.out.println(ss);運(yùn)行結(jié)果：654321132、遞歸 把串s中第一個(gè)出現(xiàn)的數(shù)字的值返回。如果找不到數(shù)字，返回-1 例如：s = "abc24us43" 則返回2s = "82445adb5" 則

9、返回8s = "ab" 則返回-1 public static int getFirstNum(String s)if(s=null | s.length()=0) return -1;char c = s.charAt(0);if(c>='0' && c<='9') return c-'0' /填空return getFirstNum(s.substring(1); /填空public static void main(String args) String s = "abs7c24us

10、43"System.out.println(getFirstNum(s);102.遞歸的定義 試數(shù) 連續(xù)數(shù) 以下程序打印出09的數(shù)字，請(qǐng)補(bǔ)充缺少的代碼。 */ public class 遞歸連續(xù)數(shù) public static void f(int begin, int end) if(begin>end) return; / 填空 System.out.println(begin); f(begin + 1, end); public static void main(String args) f(0, 9); 運(yùn)行結(jié)果:0 1 2 3 4 5 6 7 8 9113.遞歸定義

11、題意理解 公交車標(biāo)價(jià) * 公交車票價(jià)為5角。假設(shè)每位乘客只持有兩種幣值的貨幣：5角、1元。 * 再假設(shè)持有5角的乘客有m人，持有1元的乘客有n人。由于特殊情況，開始的時(shí)候，售票員沒有零錢可找。 * 我們想知道這m+n名乘客以什么樣的順序購票則可以順利完成購票過程。 * 顯然，m < n的時(shí)候，無論如何都不能完成，m >=n的時(shí)候，有些情況也不行。比如，第一個(gè)購票的乘客就持有1元。 * 下面的程序計(jì)算出這m+n名乘客所有可能順利完成購票的不同情況的組合數(shù)目。 * 注意：只關(guān)心5角和1元交替出現(xiàn)的次序的不同排列，持有同樣幣值的兩名乘客交換位置并不算做一種新的情況來計(jì)數(shù)。 */ publ

12、ic class 公交車票價(jià) / m: 持有5角幣的人數(shù) / n: 持有1元幣的人數(shù) / 返回：所有順利完成購票過程的購票次序的種類數(shù) public static int f(int m, int n) if (m < n) return 0; if (n = 0) return 1; return f(m-1,n) +f (m,n-1); / 填空 public static void main(String args) System.out.println(f(10, 8); 運(yùn)行結(jié)果:11934147遞歸 以下程序打印出09的數(shù)字，請(qǐng)補(bǔ)充缺少的代碼。public class MyT

13、estpublic static void f(int begin, int end)If(begin > end) return;System.out.println(begin);f(begin+1, end);public static void main(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種情況。public class AllPermutationpub

14、lic static void main(String args)/使用遞歸完成全排列char source=new char'A','B','C'char result=new charsource.length;allPermutation(0,source,result);/* * * param index當(dāng)前考慮的數(shù)的下標(biāo)(從0開始) * param source * param result */public static void allPermutation(int index,char source,char result)/當(dāng)

15、源數(shù)據(jù)中只有一個(gè)字符時(shí)，將該字符加入結(jié)果數(shù)組，并輸出if(source.length=1)resultindex=source0;show(result);return ;/for(int i=0;i<result.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);/* *

16、 生成去掉指定字符的新源數(shù)據(jù)數(shù)組 * param source 原來的源數(shù)據(jù)數(shù)組 * param c 指定去掉的字符 * return */public static char getNewSource(char source,char c)char newSource=new charsource.length-1;for(int i=0,j=0;i<source.length;i+)if(sourcei!=c)newSourcej=sourcei;j+;return newSource;42.全排列 遞歸 Stringbuffer警察智力訓(xùn)練 匪警請(qǐng)撥110,即使手機(jī)欠費(fèi)也可撥通！

17、為了保障社會(huì)秩序，保護(hù)人民群眾生命財(cái)產(chǎn)安全，警察叔叔需要與罪犯斗智斗勇，因而需要經(jīng)常性地進(jìn)行體力訓(xùn)練和智力訓(xùn)練！ 某批警察叔叔正在進(jìn)行智力訓(xùn)練： 1 2 3 4 5 6 7 8 9 = 110; 請(qǐng)看上邊的算式，為了使等式成立，需要在數(shù)字間填入加號(hào)或者減號(hào)（可以不填，但不能填入其它符號(hào)）。之間沒有填入符號(hào)的數(shù)字組合成一個(gè)數(shù)，例如：12+34+56+7-8+9 就是一種合格的填法；123+4+5+67-89 是另一個(gè)可能的答案。 請(qǐng)你利用計(jì)算機(jī)的優(yōu)勢(shì)，幫助警察叔叔快速找到所有答案。 每個(gè)答案占一行。形如：12+34+56+7-8+9123+4+5+67-89. 已知的兩個(gè)答案可以輸出，但不計(jì)分。

18、 各個(gè)答案的前后順序不重要。 / 遍歷所有情況 public static void fun(String v, int n) 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)證 并 輸出 public static void check(String str) String s = s

19、tr.split("+"); int sum = 0; for(String t:s) String sub = t.split("-"); int num = Integer.parseInt(sub0); / 計(jì)算負(fù)數(shù) for(int i=1;i<sub.length;i+) num -= Integer.parseInt(subi); sum += num; / 正數(shù)或負(fù)數(shù)結(jié)果 加到 總和上 if(sum = 110) System.out.println(str); public static void main(String args)

20、String str = "123456789" fun(str,1); / 調(diào)用函數(shù)，從1開始修改 46算法 實(shí)現(xiàn)全排列遞歸算法：將數(shù)據(jù)分為兩部分，遞歸將數(shù)據(jù)從左側(cè)移右側(cè)實(shí)現(xiàn)全排列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();/ 遞歸排列publ

21、icstaticvoid sort(List datas,List target,int n)if(target.size()=n)print(target);return;for(int i=0;i<datas.size();i+)List newDatas = new ArrayList(datas);List newTarget = new ArrayList(target);newTarget.add(newDatas.get(i);newDatas.remove(i);sort(newDatas,newTarget,n);/ 主函數(shù)publicstaticvoid main(S

22、tring args)String s = "a","b","c"sort(Arrays.asList(s),newArrayList(),s.length);運(yùn)行結(jié)果：abcacbbacbcacabcba方法二：publicclassAllSortpublicstaticvoid perm(String buf,int start,int end) if(start=end)/當(dāng)只要求對(duì)數(shù)組中一個(gè)字母進(jìn)行全排列時(shí)，只要按該數(shù)組輸出即可for(int i=0;i<=end;i+) System.out.print(bufi);

23、System.out.println(); else/多個(gè)字母全排列for(int i=start;i<=end;i+) String temp=bufstart;/交換數(shù)組第一個(gè)元素與后續(xù)的元素 bufstart=bufi; bufi=temp;perm(buf,start+1,end);/后續(xù)元素遞歸全排列 temp=bufstart;/將交換后的數(shù)組還原 bufstart=bufi; bufi=temp; publicstaticvoid main(String args) String buf="a","b","c"pe

24、rm(buf,0,buf.length-1); 運(yùn)行結(jié)果：abcacbbacbcacbacab47.遞歸 字符串全排列 字符串全排列publicclassT03/ 輸出字符數(shù)組publicstaticvoid print(char arr)for(int i=0;i<arr.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=sta

25、rt;i<=end;i+)/ 換位char c = arrstart;arrstart = arri;arri = c;/ 遞歸perm(arr,start+1,end);/ 恢復(fù)數(shù)組原位c = arrstart;arrstart = arri;arri = c;/ 字符串轉(zhuǎn)字符數(shù)組publicstaticvoid f(String s)char arr = s.toCharArray();perm(arr,0,arr.length-1);publicstaticvoid main(String args)String s = "abc"f(s);運(yùn)行結(jié)果：abcac

26、bbacbcacbacab58.遞歸 全排列 帶分?jǐn)?shù) 100 可以表示為帶分?jǐn)?shù)的形式：100 = 3 + 69258 / 714還可以表示為：100 = 82 + 3546 / 197注意特征：帶分?jǐn)?shù)中，數(shù)字19分別出現(xiàn)且只出現(xiàn)一次（不包含0）。類似這樣的帶分?jǐn)?shù)，100 有 11 種表示法。題目要求：從標(biāo)準(zhǔn)輸入讀入一個(gè)正整數(shù)N (N<1000*1000)程序輸出該數(shù)字用數(shù)碼19不重復(fù)不遺漏地組成帶分?jǐn)?shù)表示的全部種數(shù)。注意：不要求輸出每個(gè)表示，只統(tǒng)計(jì)有多少表示法！例如：用戶輸入：100程序輸出：11再例如：用戶輸入：105程序輸出：6資源約定：峰值內(nèi)存消耗（含虛擬機(jī)）< 64MCPU

27、消耗< 3000ms請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入.”的多余內(nèi)容。所有代碼放在同一個(gè)源文件中，調(diào)試通過后，拷貝提交該源碼。public class MyTest private static Set<Integer> all = new HashSet<Integer>(); private static Set<Integer> temp1 = new HashSet<Integer>(); private static Set<Integer> temp2 = new HashSet<Intege

28、r>(); public static void main(String args) for(int i= 1; i<9876; i+) all.clear(); if(isDuplicate(i, temp1) continue; for(int j = 2; j<100; j+) if(!isDuplicate(j*i, temp1) int y = 100-j; if(!isDuplicate(y, temp2) && all.size()=9) System.out.println(100 + "=" + y + "+&q

29、uot; + j*i + "/" + i); else all.removeAll(temp1); private static boolean isDuplicate(int n, Set<Integer> temp) temp.clear(); int i = 0; boolean flag = false; while(n>0) int x = n % 10; temp.add(x); n = n/10; i+; if(temp.contains(0) | temp.size()<i | temp.removeAll(all) flag = t

30、rue; else all.addAll(temp); return flag; 92. 全排列 排列組合 數(shù)組列表 m個(gè)字符的n個(gè)字符排列/* * 19個(gè)數(shù)中的n位數(shù)全排列 */ static int count = 0; / 總個(gè)數(shù) /* * 全排列 * param lis 記錄組合 * param start 為09(lis所用的下標(biāo)) * param end 為9 */ public static void f(List<Integer> lis,int start) if(start>=lis.size() System.out.println(lis); / 輸出

31、排列組合 count+; / 計(jì)數(shù) return ; for(int i=1;i<=9;i+) if(!lis.contains(i) lis.set(start, i); / 修改元素 else continue; f(lis,start+1); / 遞歸修改每個(gè)元素 lis.set(start, -1); / 還原 public static void main(String args) int n = 5; / 19個(gè)數(shù)中選5個(gè)全排列 List<Integer> lis = new ArrayList<Integer>(); for(int i=0;i<

32、;n;i+) / 初始化lis長度 lis.add(-1); f(lis,0); / 全排列 System.out.println("總個(gè)數(shù):"+count); 運(yùn)行結(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ò)展為

33、(字符排列)看下程序:import java.util.ArrayList; import java.util.List; public class T13 static int count = 0; / 記錄個(gè)數(shù) / m排n全排列 public static void f(List<Character> lis,char c,int n) if(n=0) count+; / 記錄個(gè)數(shù) System.out.println(lis); / 輸出 return ; for(int i=0;i<c.length;i+) if(!lis.contains(ci) / 不包含,則添加

34、 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個(gè)字符的排列組合 char c = "123456789".toCharArray(); / 要排列的字符 List<Character> lis = new A

35、rrayList<Character>(); for(int i=0;i<n;i+) lis.add('0'); / 初始化 lis 的長度 f(lis,c,n); / 進(jìn)入全排列 System.out.println("排列個(gè)數(shù):"+count); System.out.println("花費(fèi)時(shí)間:"+(System.currentTimeMillis()-star)+"毫秒"); 運(yùn)行結(jié)果:1, 2, 3 1, 2, 4 1, 2, 5 1, 2, 6 1, 2, 7 1, 2, 8 1, 2,

36、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è)字符排列 */ import java.util.ArrayList; import java.util.List; public class m個(gè)字符的n個(gè)字符排列 private static char is = new char '1', '2', '3', '4', '5', &#

37、39;6', '7', '8', '9' private static int total; private static int m = 4; private void plzh(String s, List<Integer> iL, int m) if(m = 0) System.out.println(s); total+; return; List<Integer> iL2; for(int i = 0; i < is.length; i+) iL2 = new ArrayList<Intege

38、r>(); 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<Integer> iL = new ArrayList<Integer>(); new m個(gè)字符的n個(gè)字符排列().plzh("", iL, m); System.out.println("total : " + total); 運(yùn)行結(jié)果:1234 12

39、35 1236 1237 1238 1239 1243 . . . 9867 9871 9872 9873 9874 9875 9876 total : 3024 106.全排列 遞歸 排列組合 排列平方數(shù) 若干不同的數(shù)字，排列組合后能產(chǎn)生多少個(gè)平方數(shù)？ 下面的代碼解決了這個(gè)問題。 對(duì)于：1,6,9 排列后，可產(chǎn)生3個(gè)平方數(shù)： 169 196 961 請(qǐng)閱讀下面的代碼，填寫缺失的部分（下劃線部分）。 注意：請(qǐng)把填空的答案（僅填空處的答案，不包括題面）存入考生文件夾下對(duì)應(yīng)題號(hào)的“解答.txt”中即可。 直接寫在題面中不能得分。 */ public class Tpublic static voi

40、d f(int a, int n) if (n = a.length - 1) int k = 0; / 把a(bǔ)里的數(shù)字組合為一個(gè)數(shù)字k for(int i=0; i<a.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 < a.length; i+) int t = an; an = ai; ai = t; f(a, n+1); / 填空2 t = an; an

41、 = ai; ai = t; public static void main(String args) int a = 1, 9, 6 ; f(a, 0); 117.排列的個(gè)數(shù) 計(jì)算3個(gè)A，2個(gè)B可以組成多少種排列的問題（如：AAABB, AABBA）是組合數(shù)學(xué)的研究領(lǐng)域 。但有些情況下，也可以利用計(jì)算機(jī)計(jì)算速度快的特點(diǎn)通過巧妙的推理來解決問題。 下列的程序計(jì)算了m個(gè)A，n個(gè)B可以組合成多少個(gè)不同排列的問題。請(qǐng)完善它。 */ public class 排列的個(gè)數(shù) public static int f(int m, int n) if(m=0 | n=0) return 1; return f

42、(m-1,n)+f(m,n-1); / 填空 public static void main(String args) System.out.println(f(3,2); 運(yùn)行結(jié)果:10 |全排列李白打酒類型38. 全排列 奇怪的比賽（低碳生活大獎(jiǎng)賽） 某電視臺(tái)舉辦了低碳生活大獎(jiǎng)賽。題目的計(jì)分規(guī)則相當(dāng)奇怪：每位選手需要回答10個(gè)問題（其編號(hào)為1到10），越后面越有難度。答對(duì)的，當(dāng)前分?jǐn)?shù)翻倍；答錯(cuò)了則扣掉與題號(hào)相同的分?jǐn)?shù)（選手必須回答問題，不回答按錯(cuò)誤處理）。每位選手都有一個(gè)起步的分?jǐn)?shù)為10分。某獲勝選手最終得分剛好是100分，如果不讓你看比賽過程，你能推斷出他（她）哪個(gè)題目答對(duì)了，哪個(gè)題目答

43、錯(cuò)了嗎？如果把答對(duì)的記為1，答錯(cuò)的記為0，則10個(gè)題目的回答情況可以用僅含有1和0的串來表示。例如：0010110011 就是可能的情況。你的任務(wù)是算出所有可能情況。每個(gè)答案占一行。public class Ti_38public static void main(String args) / TODO Auto-generated method stub/ 定義一個(gè)10 個(gè)數(shù)的數(shù)組 保存十個(gè)題目int x = new int10;f(x,0);private static void f(int x, int i) / TODO Auto-generated method stiub/ 如果 i 大于數(shù)組的長度就說明數(shù)組賦值完畢開始輸出if(i >= x.length)show(x);return;/ 調(diào)用兩次遞歸實(shí)現(xiàn)全排列 逐步填充xi = 0;f(x,i+1);xi = 1;f(x,i+1);/ 按要求打印數(shù)組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(