java遞歸演算法面試例子_java遞歸演算法的例子

⑴ 求經典的遞歸演算法以及案例（可用C#、PHP、java其中一種語言來寫）!

我用C#來寫（注意，更多的請直接到我的個人博客，點擊， http://www.cnblogs.com/serviceboy/archive/2009/07/19/1526590.html，收看）【例1】有甲、乙、丙、丁四人，從甲開始到丁，一個比一個大1歲，已知丁10歲，問甲幾歲？【分析】這是遞歸法的一道非常典型的題目——因為我們可以很顯然知道：假設要計算甲的年齡，那麼必須直到乙的年齡；同樣，算乙的必須直到丙的，算丙的必須知道丁的，因為丁已知，自然可以往前推算了。現在假設有一個數學模型（函數）可以計算出他們各自的年齡（方便期間我們給他們編號——甲＝1，乙＝2，丙＝3，丁＝4），那麼存在這一個F(X)函數，X表示某人的編號，其規律如下：F(1)=F(2)+1F(2)=F(3)+1F(3)=F(4)+1F(4)=10顯然，直到X=4的時候是一個終止值，其餘情況下都是返回F(X』)，F(X』』)……F(X』』……』)，且前者總是比後至大1，這也符合了X』和X總是呈現一定函數關系（設想一下，如果不是等差和等比，又怎麼可能在一個遞歸函數中進行計算？要知道，函數本身就是一個公式表示，既然是公式，那麼一定是一種函數關系Y=F(X)），此處顯然X和X』的關系是X=X』+1。根據規律式，我們可以寫出該遞歸函數：int AgeCal(int id)
{
if(id==4) return 10;
else
return (AgeCal(id+1)+1);
} 【例2】計算n！【分析】雖然這道題目不像例1一樣清晰明了告訴你使用「遞歸」法反推，但是我們有這樣一個常識——n！＝(n-1)!*n；(n-1)!=(n-2)!*(n-1)……n=0或1，返回1.顯然n與n-1，n-2也是線性的遞減數列（等差關系）。其規律如下：F(n)=F(n-1)*nF(n-1)=F(n-2)*(n-1)F(n-2)=F(n-3)*(n-2)……F(1)=1或者F(0)=1(防止別人直接輸入0)編寫其遞歸函數，如下：int Fac(int n)
{
if(n==1 || n==0)
{
return 1;
}
else
return Fac(n-1)*n;
} 【例3】求一組整數中的最大(小)值（整數是一個int[]數組，個數未知）。【分析】當數字只有兩個的時候，我們可以使用>和<直接比較；但是當數字超過2個的時候（假設3個），那麼我們可以使用一個預訂的函數（比如Max(1,2)和3進行比較），由於1，2兩個數比較的時候已經得到一個最大值，因此在回代到Max中又變成了兩個數的比較。這樣，我們可以發現一個規律：F(1,2,3,4……n)＝F(1,2,3,4……n-1)和n比較F(1,2,3,4……n-1)＝F(1,2,3,4……n-2)和n-1比較……F(1,2,3)=F(1,2)和3比較F(1,2)＝結果（並回代）相應的遞歸函數如下(C#)：Code
int Max(int[]numbers)
{
if(numbers.Length==2)
{
return (numbers[0]>numbers[1]?numbers[0]:numbers[1]);
}
else
{
int[]tempnumbers=new int[numbers.Length-1];
for(int i=0;i<numbers.Length-1;++i)
{
tempnumbers[i]=numbers[i];
}
return (Max(tempnumbers)>numbers[numbers.Length-1]? Max(tempnumbers): numbers[numbers.Length-1]
}
}

⑵ java 遞歸問題

(1) 遞歸就是在過程或函數里調用自身;
(2) 在使用遞歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
遞歸演算法一般用於解決三類問題：
(1)數據的定義是按遞歸定義的。(Fibonacci函數)
(2)問題解法按遞歸演算法實現。(回溯)
(3)數據的結構形式是按遞歸定義的。

下面這個例子以遞歸的方法計算n的階乘。
public class Test {
public static int factorial(int n){
if(n == 0){
return 1;
}else{
return n * factorial(n-1);
}

}

public static void main(String[] args) {
System.out.println(factorial(3));
}

}

⑶ java遞歸演算法的例子

十進制整數轉二進制字元串的遞歸寫法:

public String dtob(int n) {
if (n == 0 || n == 1) {
return Integer.toString(n);
} else {
return dtob(n / 2) + Integer.toString(n % 2);
}
}

⑷ java遞歸演算法的例子。

階乘：

要求：給定一個數值，計算出它的階乘值，例如5的階乘為5*4*3*2*1

實現：

[html] view plain

// 利用遞歸實現一個數的階乘值 private static BigDecimal getNum(BigDecimal inNum) { if (inNum.compareTo(BigDecimal.ONE) == 0) { return inNum; } return inNum.multiply(getNum(inNum.subtract(BigDecimal.ONE))); }

（2）Fibonacci數列：1，1，2，3，5，8，13……

要求：找出數列中指定index位置的數值

實現：

[html] view plain

// 利用遞歸實現了Fibonacci數列 private static int fab(int index) { if (index == 1 || index == 2) { return 1; } else { return fab(index - 1) + fab(index - 2); } }

（3）漢諾塔

要求：漢諾塔挪動

實現：

[html] view plain

private static final String DISK_B = "diskB"; private static final String DISK_C = "diskC"; private static final String DISK_A = "diskA"; static String from=DISK_A; static String to=DISK_C; static String mid=DISK_B; public static void main(String[] args) { String input=JOptionPane.showInputDialog("please input the number of the disks you want me move."); int num=Integer.parseInt(input); move(num,from,mid,to); }

[html] view plain

// 利用遞歸實現漢諾塔 private static void move(int num, String from2, String mid2, String to2) { if (num == 1) { System.out.println("move disk 1 from " + from2 + " to " + to2); } else { move(num - 1, from2, to2, mid2); System.out.println("move disk " + num + " from " + from2 + " to " + to2); move(num - 1, mid2, from2, to2); } }

（4）排列組合

要求：將輸入的一個字元串中的所有元素進行排序並輸出，例如：你給出的參數是"abc"，

則程序會輸出

abc

acb

bac

bca

cab

cba

實現：

[html] view plain

public static void permute(String str) { char[] strArray = str.toCharArray(); permute(strArray, 0, strArray.length - 1); }

[html] view plain

// 利用遞歸實現，將輸入的一個字元串中的所有元素進行排序並輸出 public static void permute(char[] list, int low, int high) { int i; if (low == high) { String cout = ""; for (i = 0; i <= high; i++) { cout += list[i]; } System.out.println(cout); } else { for (i = low; i <= high; i++) { char temp = list[low]; list[low] = list[i]; list[i] = temp; permute(list, low + 1, high); temp = list[low];

導航:首頁 > 源碼編譯 > java遞歸演算法面試例子

java遞歸演算法面試例子

與java遞歸演算法面試例子相關的資料