4 
#include <vector>
std::vector<long int> as;

long int a(size_t n){
  if(n==1) return 1;
  if(n==2) return -2;
  if(as.size()<n+1)
    as.resize(n+1);
  if(as[n]<=0)
  {
    as[n]=-4*a(n-1)-4*a(n-2);
  }
  return mod(as[n], 65535);
}

上面的代码示例使用 memoization 根据一些输入计算递归公式n。我知道这使用了记忆化，因为我编写了一个使用相同公式的纯递归函数，但是对于更大的n. 我以前从未使用过向量，但我做了一些研究，我理解了它们的概念。我知道记忆应该存储每个计算的值，这样它就可以简单地检索已经计算过的值，而不是再次执行相同的计算。

我的问题是：这个记忆如何，它是如何工作的？我似乎无法在代码中看到它检查 n 的值是否已经存在。另外，我不明白if(as[n]<=0). 这个公式可以产生正值和负值，所以我不确定这个检查在寻找什么。

谢谢，我想我已经接近理解它是如何工作的了，它实际上比我想象的要简单一些。

我不认为序列中的值永远是 0，所以这应该对我有用，因为我认为 n 必须从 1 开始。

但是，如果零在我的序列中是一个可行的数字，那么我可以解决它的另一种方法是什么？例如，如果五个永远不会出现怎么办？我只需要用五个填充我的向量吗？

编辑：哇，我在检查代码和输入这个代码时收到了很多其他的回复。谢谢大家的帮助，我想我现在明白了。

4

5 回答 5

6

if (as[n] <= 0)是支票。如果像你说的那样有效值可能是负数，那么你需要一个不同的哨兵来检查。有效值可以为零吗？如果没有，那么只需进行测试if (as[n] == 0)。这使您的代码更容易编写，因为默认情况下ints 的向量用零填充。

于 2008-09-29T03:08:31.017 回答
1

代码似乎错误地检查了 is (as[n] <= 0)，并重新计算了函数的负值（看起来大约是每隔一个值）。这使得工作与 n 线性缩放，而不是递归解决方案的 2^n，因此它运行得更快。

不过，更好的检查是测试 if (as[n] == 0)，它在我的系统上运行速度似乎快了 3 倍。即使函数可以返回 0，0 值也只是意味着计算需要稍长的时间（尽管如果 0 是一个频繁的返回值，您可能需要考虑一个单独的向量来标记该值是否已被计算，而不是使用单个向量来存储函数的值以及是否已计算）

于 2008-09-29T03:36:01.403 回答
0

如果公式可以同时产生正值和负值，则此函数存在严重错误。检查应该if(as[n]<=0)是检查它是否已经缓存了这个计算值。但是如果公式可以是负数，这个函数会重新计算这个缓存值很多......

它真正想要的是 a vector<pair<bool, unsigned> >，其中 bool 表示该值是否已计算。

于 2008-09-29T03:30:23.507 回答
0

所发布的代码仅记忆大约 40% 的时间（恰好在记忆值为正时）。正如 Chris Jester-Young 指出的那样，正确的实现将改为检查if(as[n]==0). 或者，可以将记忆代码本身更改为读取as[n]=mod(-4*a(n-1)-4*a(n-2),65535);

（==0当记忆值为 0 时，即使检查也会花费精力。幸运的是，在你的情况下，这永远不会发生！）

于 2008-09-29T03:38:18.433 回答
0

这段代码有一个错误。当 as[n] <= 0 时，它将继续重新计算 as[n] 的值。它会记住结果为正的 a 的值。它比没有记忆的代码工作得快得多，因为 as[] 有足够的正值，因此递归很快终止。您可以通过使用大于 65535 的值作为哨兵来改善这一点。当向量扩展时，向量的新值被初始化为零。

于 2008-09-29T04:20:16.897 回答