如预期中的Ruby在使用动态规划

我是新来的宝石，所以我这里大概做了非常错误的新手解决了斐波那契序列的程序无法正常工作的返回值，但我想谷歌搜索答案，不能图出这个代码给怪异行为的原因。此代码非常简单，并使用基本的动态编程将中间结果存储到散列，以便稍后用于加速计算。如预期中的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，因为使一个呼叫到撒谎（1）和FIB（0），它们分别返回2和1，然后加入到为3但输出为1和2 。

来源

2011-02-06 Ken Li

Hash.values_at返回一个数组，所以当代码不fib(1) + fib(0)，它的串联阵列[2]和[1]在一起，从而导致了答案[2, 1]。相反的：

return $existingSequence.values_at n;

...你应该这样做，而不是：

return $existingSequence[n]

BTW，斐波那契序列传统上与0和1，而不是1和2

来源

2011-02-06 06:10:14 Claw

第二行开始的fib应改为：

return $existingSequence[n]

，而不是

return $existingSequence.values_at n

将puts $existingSequence添加到文件末尾以查看区别。

来源

2011-02-06 06:11:34

稍微偏离主题，这里的基本上是做同样的事情，但使用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

注意：我自己没有提出这个，我从here偷了它。

来源

2011-02-06 16:03:08

如预期中的Ruby在使用动态规划

回答

相关问题