#include <stdio.h>
// 記憶化數組
int memo[1000];
// 初始化記憶化數組
void initializeMemo() {
for (int i = 0; i < 1000; i++) {
memo[i] = -1;
}
}
// 記憶化 Fibonacci 函數，處理邊界條件
int fibonacci(int n) {
if (memo[n] != -1) {
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];
}
int main() {
int n = 10;
initializeMemo(); // 初始化記憶化數組
for (int i = 0; i < n; i++) {
printf("%d ", fibonacci(i));
}
return 0;
解釋優化後的算法
- 基礎情況處理：當 nnn 為 0 或 1 時，直接返回對應的 Fibonacci 數。
- 記憶化技術：使用 memo 陣列存儲已經計算過的 Fibonacci 數，避免重複計算。
- 遞迴展開：對於其他情況，通過 fibonacci(n - 1) + fibonacci(n - 2) 計算 Fibonacci 數，並將結果存儲在 memo 陣列中。
總結
遞迴演算法通過自我調用來解決問題，但正確處理邊界條件至關重要，以防止無限遞迴，保證計算結果的正確性和提高算法性能。以 Fibonacci 序列為例，基礎情況 F(0)=0F(0) = 0F(0)=0 和 F(1)=1F(1) = 1F(1)=1 確保了遞迴計算的正確展開。使用記憶化技術進一步優化了算法，避免重複計算，提高了效率。
阿摩線上測驗
登入