我试图了解备忘录在C++中的工作方式,所以我看了一个在Fib中使用的备忘录的示例。序列。
std::map<int, int> fibHash;
int memoized_fib (int n)
{
std::map<int, int>::iterator fibIter = fibHash.find(n);
if( fibIter != fibHash.end() ) return *fibIter;
int fib_val;
if( n <=1 ) fib_val = 1;
else fib_val = memoized_fib ( n-1 ) + memoized_fib ( n-2 );
fibHash[ n ] = fib_val;
return fib_val;
}
我对fibHash [n]的工作方式有些困惑。它是否仅保存每个fib(#)的各个值?另外,迭代器遍历索引以在表中查找正确的值并返回该值?例如fib(6)=查找已存储的fib(5)和fib(4),然后将它们添加起来?
最佳答案
该代码确实将每个fib_val
保存到fibHash
映射中。在fibHash
上调用的find方法搜索 map 以查看该值是否先前已计算。如果是这样,find
将对此值返回一个迭代器,并且函数将其返回(return *fibIter
)。fibHash[ n ] = fib_val;
在 map 中添加新值。