C++函數(shù)模板的經(jīng)典案例之一是計算斐波那契數(shù)列。以下是一個使用函數(shù)模板計算斐波那契數(shù)列的示例:
#include <iostream>
// 定義函數(shù)模板
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; // 想要計算的斐波那契數(shù)列項數(shù)
std::cout << "Fibonacci number at position "<< n << " is: " << fibonacci<n>(n) << std::endl;
return 0;
}
然而,上述代碼雖然使用了函數(shù)模板,但存在顯著的缺點:它進行大量的重復(fù)計算,導(dǎo)致效率低下。為了優(yōu)化這個問題,可以使用記憶化搜索技術(shù)來存儲已經(jīng)計算過的斐波那契數(shù)列項,從而避免重復(fù)計算。
以下是一個使用記憶化搜索優(yōu)化后的示例:
#include <iostream>
#include <unordered_map>
// 定義函數(shù)模板
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()) // 如果已經(jīng)計算過該項,則直接返回結(jié)果
return memo[n];
else {
int result = fibonacci<N-1>(n-1, memo) + fibonacci<N-2>(n-2, memo); // 計算結(jié)果并存儲在memo中
memo[n] = result; // 將結(jié)果存入unordered_map
return result;
}
}
int main() {
int n = 10; // 想要計算的斐波那契數(shù)列項數(shù)
std::unordered_map<int, int> memo; // 創(chuàng)建一個unordered_map用于存儲已經(jīng)計算過的斐波那契數(shù)列項
std::cout << "Fibonacci number at position "<< n << " is: " << fibonacci<n>(n, memo) << std::endl;
return 0;
}
通過使用記憶化搜索技術(shù),我們顯著提高了計算斐波那契數(shù)列的效率。這種方法不僅適用于斐波那契數(shù)列,還可以應(yīng)用于其他需要大量重復(fù)計算的場景。