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;
}

通过使用记忆化搜索技术，我们显著提高了计算斐波那契数列的效率。这种方法不仅适用于斐波那契数列，还可以应用于其他需要大量重复计算的场景。