如預期中的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在使用動態規劃

回答

相關問題