フィボナッチ数を計算する方法をまとめてみた - yattのブログProject Eulerで巨大な数のフィボナッチ数(10^14番目ぐらい)の剰余を求める必要があったので、関連するアルゴリズムについてまとめました。行列を使った最適化については@nico_shindanninさんにヒントをいただきました。 定義通り求める すぐに限界のくる方法。一度の関数呼び出しで2度再帰することと、同じフィボナッチ数を何度も計算するので時間がかかる。 def fib_naive(n): if n in [0,1]: return 1 else: return fib_naive(n-1) + fib_naive(n-2) メモ化して求める ナイーブな方法より計算が減るので速くなるけど大きなフィボナッチ数を求めようとするとメモリをバカ喰いする。 def fib_memo(n, m={0:0,1:1}): if not n in m: m[n] = fib_memo(n-1
