動的プログラミングを使用してフィボナッチシーケンスを解決するプログラムでRubyで戻り値が正しく機能しない

Question

私はRubyを初めて使うので、私はおそらく初心者のミスを犯しているでしょうが、このコードが奇妙な振る舞いをしている理由を説明してください。このコードは非常に簡単で、基本的な動的プログラミングを使用して中間結果をハッシュに格納するので、後で計算を高速化するために使用されます。それは3であることを添加し（1）、次いでそれぞれ2と1を返し、FIB（0）FIBを呼び出すため

$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 

Iは出力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

二行目で始まりますfibの読みください：

return $existingSequence[n] 

の代わり

を

return $existingSequence.values_at n 

ファイルの末尾に「puts $existingSequence」を追加してください。

Answer 3

ちょっとオフトピックは、ここでは基本的に同じことをやっての楽しい方法ですが、キャッシングのために、だけでなく、値を計算するためだけでなく、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からそれを盗んだ。