111年檢察事務官三等程式語言
|
三、若有一個遞迴函數如下： Procedure FIB(n) if n = 0, FIB = 0; if n = 1, FIB = 1; else FIB(n-1)+FIB(n-2) end if end 試問 FIB(4) 之值為多少？在計算 FIB(4) 值時，需要呼叫此 FIB(n) 函數多少次。（25分） |
答：
|
#include <iostream> using namespace std; int cnt = 0; // 呼叫次數 int FIB(int n) { cnt++; if (n == 0) { return 0; } if (n == 1) { return 1; } else { return FIB(n - 1) + FIB(n - 2); } } int main(void) { cout << "FIB(4) = " << FIB(4) << endl; cout << "呼叫次數 = " << cnt << endl; return 0; } |
執行結果：
FIB(4) = 3
呼叫次數 = 9
(一)FIB(4)的值
FIB(4) = FIB(4-1)+FIB(4-2) = FIB(3)+FIB(2)
FIB(3) = FIB(3-1)+FIB(3-2) = FIB(2)+FIB(1)
FIB(2) = FIB(2-1)+FIB(2-2) = FIB(1)+FIB(0) = 1+0 = 1
FIB(3) = FIB(2)+FIB(1) = 1+1 = 2
FIB(4) = FIB(3)+FIB(2)= 2+1 = 3
由以上得知 FIB(4) 的值為3。
(二)呼叫FIB(n)函數多少次
由上圖可知呼叫9次節點，所以是9次。
留言列表
國考資訊處理解答 (7)
