我试图了解备忘录在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 中添加新值。

10-08 15:59