二、撰寫一遞迴函式Fibonacci（int n）計算費氏數列（Fibonacci number）的第n項fn之值。費氏數列定義為：f0= 0 , f1=1, fn= fn-1+ fn-2當n>1。請儘可能留意程式效率（加法執行次數），使效率與使用迴圈方式處在同一個等級。（20 分）

詳解 (共 2 筆)

詳解提供者：Triple w.

正確解法： 我們可以通過遞迴函式來計算第 n 項，但我們要考慮到效能。一般的遞迴解法雖然簡單，但會重複計算許多相同的值，導致效能下降。因此，這裡有兩種方法：

普通遞迴法： 這是最直觀的解法，但會有大量重複計算，效能較差。
使用記憶體化（Memoization）： 我們可以將已經計算過的值保存起來，避免重複計算，提高效能

詳解提供者：hchungw

為了提高遞迴計算費氏數列（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項，而不會因為深度遞迴導致的效率低下或棧溢出。

二、撰寫一遞迴函式Fibonacci（int n）計算費氏數列（Fibonacci number）的第n項fn之值 。費氏數列定義為：f0= 0 , f1=1, fn= fn-1+ fn-2當n>1。請儘可能留意程式效率（加法 執行次數），使效率與使用迴圈方式處在同一個等級。（20 分）

詳解 (共 2 筆)

其他申論題

二、撰寫一遞迴函式Fibonacci（int n）計算費氏數列（Fibonacci number）的第n項fn之值。費氏數列定義為：f0= 0 , f1=1, fn= fn-1+ fn-2當n>1。請儘可能留意程式效率（加法執行次數），使效率與使用迴圈方式處在同一個等級。（20 分）