Ruby

【アルゴリズム3】フィボナッチ数列を解いてみよう!

アルゴリズム、計算量

事前準備

フィボナッチ数列というものがあります。
1, 1, 2, 3, 5, 8, 13, 21 ,,,


のように第n+2項が、 第n+1項と、第n項の和になるよう数列です。


この数列のn項目の数をもとめる関数fab(n)として以下のようなアルゴリズムを考えました。


def fib(n)
  if n == 0 || n == 1
    return 1
  end
  fib(n - 2) + fib(n - 1)
end

たしかにこのアルゴリズムで求めれるのですが、n=50や100になると計算が終わりません。(n=100の時、1秒間に100億回四則演算が可能なパソコンで400兆年ほどかかります。)
このアルゴリズムをn=1000や10000のときでも現実の時間で計算可能になるように工夫しましょう。


ヒント:
今のアルゴリズムでは同じ引数で複数回fib(n)関数を呼び出しています。一度fib(n)を実行したときにそのnとfib(n)の結果のペアをある領域に確保して、複数回fib(n)を実行することを避ければ、計算量は減りますね。

問題: 1

n=10000のときでも現実の時間で計算可能なfib(n)を定義しましょう。