為了提高遞迴計算費氏數列（Fibonacci sequence）第
n 項的效率，我們可以使用"記憶化"（memoization）技術。記憶化是一種將過去操作的結果儲存起來，當再次需要同樣的計算時直接取用該結果，從而避免重複計算的技術。這種方法可以將費氏數列的遞迴計算效率提高到與迴圈方法相當的水平。
以下是一個實現這個想法的Java程式碼示例：
java
Copy code
public class Fibonacci {
// 使用一個靜態陣列來儲存計算過的費氏數列的值
private static long[] memo;
public static long fibonacci(int n) {
// 初始化記憶化儲存空間
if (memo == null || memo.length < n + 1) {
memo = new long[n + 1];
}
// 如果已經計算過這個值，直接返回結果
if (memo[n] != 0) {
return memo[n];
}
// 計算並記憶化費氏數列的值
if (n == 0) {
memo[n] = 0;
} else if (n == 1) {
memo[n] = 1;
} else {
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}
return memo[n];
}
public static void main(String[] args) {
int n = 50; // 舉例計算第50項
System.out.println("Fibonacci number at position " + n + " is: " + fibonacci(n));
}
}
這段程式碼定義了一個靜態陣列 memo 用於儲存計算過的費氏數列的值，這樣當計算到相同的
n 值時，可以直接從 memo 中取出結果，而不需要再次進行遞迴計算。這個方法顯著減少了重複計算，使得計算效率大幅提高。
請注意，為了處理更大的數值，我們在此使用 long 類型來儲存費氏數列的值，並且預設在 memo 陣列中未計算的項目為0（因為在Java中，數組的數值預設初始化為0）。這段程式碼可以高效計算較大的費氏數列項目，比如第50項，而不會因為深度遞迴導致的效率低下或棧溢出。
阿摩線上測驗
登入
