資料結構與演算法
以遞迴將求費氏數的函數 fib(n) 定義為「若 n 在1以下則回傳 n，否則回傳 fib(n−1) + fib(n−2)」。呼叫 fib(5) 時，含第一次呼叫在內，fib 被呼叫幾次？
- A6次
- B9次
- C15次
查看答案與解析
正確答案：C. 15次
設 fib(n) 的呼叫次數為 C(n)，則 C(0) = C(1) = 1、C(n) = 1 + C(n−1) + C(n−2)，因此 C(2) = 3、C(3) = 5、C(4) = 9、C(5) = 15。由於相同的值被反覆重新計算，次數會隨 n 呈指數增加，fib(30) 約需269萬次。若使用把算過的值記在表中的記憶化（動態規劃），只需計算 fib(0)～fib(5) 這6種，呼叫也減為9次（2n − 1）。6次是不同引數的個數，9次是記憶化時的呼叫次數。
- A. 這是不同引數 fib(0)～fib(5) 的個數，沒有計入相同值的重新計算。
- B. 這是記憶化後，已算過的值直接從表中回傳時的呼叫次數。
- C. 正確。由 C(n) = 1 + C(n−1) + C(n−2)，可得 C(5) = 15。