ruby - 在使用动态编程解决斐波那契数列的程序中，返回值在 Ruby 中未按预期工作

Question

我是 ruby​​ 新手，所以我可能在这里犯了一个非常新手的错误，但我尝试谷歌搜索以获得答案，但无法弄清楚这段代码给出奇怪行为的原因。这段代码非常简单，并使用基本的动态编程将中间结果存储到哈希中，以便以后使用它来加快计算速度。

$existingSequence = {0 => 1, 1 => 2}


def fib(n)
  if $existingSequence.has_key? n
    return $existingSequence.values_at n;
  end

  if n == 0
    return 1;
  elsif n == 1
    return 2;
  end

  $existingSequence[n] = fib(n - 1) + fib(n - 2)
  return $existingSequence[n];
end

n = fib(2)
puts n

我希望这段代码输出 3，因为这会调用 fib(1) 和 fib(0)，分别返回 2 和 1，然后添加为 3。但输出是 1 和 2。

Answer 1

Hash.values_at返回一个数组，所以当代码执行时fib(1) + fib(0)，它会将数组连接[2]在一起[1]，从而得到答案[2, 1]。代替：

return $existingSequence.values_at n;

...你应该这样做：

return $existingSequence[n]

顺便说一句，斐波那契数列传统上从 0 和 1 开始，而不是 1 和 2。

Answer 2

有点跑题了，这里有一种有趣的方式来做本质上相同的事情，但是使用Hash默认值机制Hash不仅可以用于缓存，还可以用于计算值：

fibs = { 0 => 0, 1 => 1 }.tap do |fibs|
  fibs.default_proc = ->(fibs, n) { fibs[n] = fibs[n-1] + fibs[n-2] }
end

fibs[9]
# => 34

注意：这个不是我自己想出来的，我是从这里偷来的。

Answer 3

第二行fib应该是：

return $existingSequence[n]

代替

return $existingSequence.values_at n

添加puts $existingSequence到文件末尾以查看差异。