C++函数模板的经典案例之一是计算斐波那契数列。以下是一个使用函数模板计算斐波那契数列的示例:
#include
// 定义函数模板
template
int fibonacci(int n) {
if (n <= 1)
return n;
else
return fibonacci(n-1) + fibonacci(n-2);
}
int main() {
int n = 10; // 想要计算的斐波那契数列项数
std::cout << "Fibonacci number at position "<< n << " is: " << fibonacci(n) << std::endl;
return 0;
}
然而,上述代码虽然使用了函数模板,但存在显著的缺点:它进行大量的重复计算,导致效率低下。为了优化这个问题,可以使用记忆化搜索技术来存储已经计算过的斐波那契数列项,从而避免重复计算。
以下是一个使用记忆化搜索优化后的示例:
#include
#include
// 定义函数模板
template
int fibonacci(int n, std::unordered_map& memo) {
if (n <= 1)
return n;
else if (memo.find(n) != memo.end()) // 如果已经计算过该项,则直接返回结果
return memo[n];
else {
int result = fibonacci(n-1, memo) + fibonacci(n-2, memo); // 计算结果并存储在memo中
memo[n] = result; // 将结果存入unordered_map
return result;
}
}
int main() {
int n = 10; // 想要计算的斐波那契数列项数
std::unordered_map memo; // 创建一个unordered_map用于存储已经计算过的斐波那契数列项
std::cout << "Fibonacci number at position "<< n << " is: " << fibonacci(n, memo) << std::endl;
return 0;
}
通过使用记忆化搜索技术,我们显著提高了计算斐波那契数列的效率。这种方法不仅适用于斐波那契数列,还可以应用于其他需要大量重复计算的场景。