阅读量:0
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; } 通过使用记忆化搜索技术，我们显著提高了计算斐波那契数列的效率。这种方法不仅适用于斐波那契数列，还可以应用于其他需要大量重复计算的场景。
