申論題 - 阿摩線上測驗

申論題資訊

試卷：99年 - 099年警察人員及99年交通事業鐵路人員員級_資訊處理#34123
科目：程式設計
年份：99年
排序：0

申論題內容

三、改寫下列程式碼的遞迴呼叫（recursive call）為迴圈疊代（iteration）（即不使用遞
迴呼叫，但必須完成相同功能）。（25 分）
…
int main() {
int num = 100;
…
cout ＜＜ fib(num);
return 0;
}
int fib(int num) {
If (num == 0 || num == 1)
return num;
else
return fib(num – 1) + fib(num – 2);
}

詳解 (共 1 筆)

詳解提供者：hchungw

將遞迴方法改寫為迴圈疊代的方式計算費波那契數列，可以提高效率，特別是對於大數值的計算。以下是使用迴圈疊代方式實現費波那契數列的C++程式碼，它避免了遞迴的重複計算問題：

#include <iostream>
using namespace std;

int fib(int num) {
if (num == 0) return 0;
if (num == 1) return 1;

int prevPrev = 0; // 前前一個數
int prev = 1; // 前一個數
int current = 0; // 目前的數

for (int i = 2; i <= num; i++) {
current = prevPrev + prev;
prevPrev = prev;
prev = current;
}

return current;
}

int main() {
int num = 100;
cout << "Fib(" << num << ") = " << fib(num);
return 0;
}
在這個迴圈版本中，我們初始化了兩個變數prevPrev和prev來分別存儲計算過程中的Fib(n-2)和Fib(n-1)的值。然後，我們從i=2開始迴圈，直到達到目標數num。在每次迴圈的過程中，我們計算當前費波那契數current為prevPrev + prev，然後更新prevPrev和prev的值以便於下一輪迴圈的計算。

這種方法只需要O(n)的時間複雜度，相比於遞迴方法的指數時間複雜度，這是一個顯著的改進。此外，它也避免了遞迴可能導致的堆棧溢出問題。