C++函數模板有何經典案

C++函數模板的經典案例之一是計算斐波那契數列。以下是一個使用函數模板計算斐波那契數列的示例：

#include <iostream>

// 定義函數模板
template<int N>
int fibonacci(int n) {
    if (n <= 1)
        return n;
    else
        return fibonacci<N-1>(n-1) + fibonacci<N-2>(n-2);
}

int main() {
    int n = 10;  // 想要計算的斐波那契數列項數
    std::cout << "Fibonacci number at position "<< n << " is: " << fibonacci<n>(n) << std::endl;
    return 0;
}

然而，上述代碼雖然使用了函數模板，但存在顯著的缺點：它進行大量的重復計算，導致效率低下。為了優化這個問題，可以使用記憶化搜索技術來存儲已經計算過的斐波那契數列項，從而避免重復計算。

以下是一個使用記憶化搜索優化后的示例：

#include <iostream>
#include <unordered_map>

// 定義函數模板
template<int N>
int fibonacci(int n, std::unordered_map<int, int>& memo) {
    if (n <= 1)
        return n;
    else if (memo.find(n) != memo.end())  // 如果已經計算過該項，則直接返回結果
        return memo[n];
    else {
        int result = fibonacci<N-1>(n-1, memo) + fibonacci<N-2>(n-2, memo);  // 計算結果并存儲在memo中
        memo[n] = result;  // 將結果存入unordered_map
        return result;
    }
}

int main() {
    int n = 10;  // 想要計算的斐波那契數列項數
    std::unordered_map<int, int> memo;  // 創建一個unordered_map用于存儲已經計算過的斐波那契數列項
    std::cout << "Fibonacci number at position "<< n << " is: " << fibonacci<n>(n, memo) << std::endl;
    return 0;
}

通過使用記憶化搜索技術，我們顯著提高了計算斐波那契數列的效率。這種方法不僅適用于斐波那契數列，還可以應用于其他需要大量重復計算的場景。