编程之美_008斐波那契数列
// 斐波那契数列// f(n) = f(n-1) + f(n-2);// n<=0 f(n)=0; f(1)=1; f(2)=1;public class Test{ public static void main(String[] args) { for (int i = 0; i < 10; i++) { System.out.println("f(" + i + ")=" + fibonacci1(i)); } System.out.println("------------------------"); for (int i = 0; i < 10; i++) { System.out.println("f(" + i + ")=" + fibonacci2(i)); } } // 递归算法 static int fibonacci1(int n) { if (n <= 0) { return 0; } else if (n == 1) { return 1; } else { return fibonacci1(n - 1) + fibonacci1(n - 2); } } // 查找算法 static int size = 9999; static double[] fResult = new double[size + 1]; static { // fResult初始化fResult数组 fResult[0] = 0; fResult[1] = 1; for (int i = 2; i <= size - 1; i++) { fResult[i] = fResult[i - 1] + fResult[i - 2]; } } static double fibonacci2(int n) { return fResult[n]; } // 通项公式 F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5】 // 分治策略}