急…遞迴方式寫JAVA

Question

1.使用遞迴方式寫一個可以將陣列元素順序完全顚到的程式
(本是20,25,30,35 執行後為35,30,25,20)
2.不要用遞迴方式寫Fibonacci數列的程式：
(Fibonacci數列f1,f2,f3,....,fn，其中
f1=1，f2=1
n>2時，fn=fn-1+fn-2)

Answer 1

請參考我的做法1. 我用 Divide & Conquer 法將陣列分成兩小段，再持續用遞迴法分段直到其長度為 1 或 2。若為 1，則傳回該小段陣列；若為 2，則反轉後再傳回該陣列。public class A { public static int[] reverse(int[] ary) {  if (ary.length == 1) return ary; // 若長度為1，則傳回該陣列  if (ary.length == 2) return new int[]{ary[1], ary[0]}; // 若為2，反轉後傳回  int[] x = new int[ary.length/2]; // 若超過2，則切成2段再遞迴之  int[] y = new int[ary.length - x.length];  for (int i = 0; i < ary.length; i++) {   if (i < x.length) x[i] = ary[i];   else y[i-x.length] = ary[i];  }  x = reverse(x); // 遞迴前半段  y = reverse(y); // 遞迴後半段  for (int i = 0; i < ary.length; i++) { // 先讀後半段，再接前半段以完成反轉   if (i < y.length) ary[i] = y[i];   else ary[i] = x[i-y.length];  }  return ary; }  public static void main(String[] args) {  int[] ary = {20, 30, 40, 50, 65};  ary = reverse(ary);  for (int i = 0; i < ary.length; i++) {   System.out.print(ary[i] + " ");  } }}2. 不用遞迴法，則需用3個數字來儲存f(n)、f(n-1) 及 f(n-2)，再用累加的方式來求得 f(n)。public class B { public static int fibonacci(int x) {  if (x == 1 || x == 2) return 1;  int a = 1; // f(n-2)  int b = 1; // f(n-1)  int c = 0; // f(n)  for (int i = 3; i <= x; i++) {   c = a + b;   a = b;   b = c;  }  return c; }  public static void main(String[] args) {  System.out.println("f(3) = " + fibonacci(3));  System.out.println("f(4) = " + fibonacci(4));  System.out.println("f(5) = " + fibonacci(5));  System.out.println("f(6) = " + fibonacci(6));  System.out.println("f(7) = " + fibonacci(7));  System.out.println("f(8) = " + fibonacci(8));  System.out.println("f(9) = " + fibonacci(9));  System.out.println("f(10) = " + fibonacci(10));  System.out.println("f(15) = " + fibonacci(15));  System.out.println("f(20) = " + fibonacci(20)); }}

2006-06-19 17:17:20 補充：
Fibonacci 是義大利的數學家，詳見 Wikipedia 對他的簡介 (http://zh.wikipedia.org/wiki/%E6%AF%94%E8%90%A8%E7%9A%84%E5%88%97%E5%A5%A5%E7%BA%B3%E5%A4%9A)。而他所研究的 Fibonacci number，也可以在 Widipedia 上找到(http://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B8)