フィボナッチで再帰メモ化
先日、AtCoderの勉強会で強い人からメモ化再帰いいよーといわれたので学んでみる
今回は単純にフィボナッチ数列を求めるプログラムを作る
フィボナッチ数列は、初期値とその次の値を足した数字が続いていく数列である
1, 2, 3, 5, 8....
今回の仕様は以下の通り
・入力Nを受け取り、N個の数列を作成する
・プログラムを2本つくり、一つは再帰を用いた形、もう一つはそこにメモ化を加えた形
N = int(input()) def calc(x): if x == 1: return 0 elif x == 2: return 1 else: return calc(x-1)+calc(x-2) print(calc(N))
計算結果
N=30 222ms
N=33 893ms
N=36 3721ms
N=39 >10000ms
これでは時間がかかってしまい、Nが大きくなった時に対応できない
よって、ハッシュによるメモ化を実装する
計算した値をハッシュに登録し、結果をメモする
N = int(input()) dic = {1:1, 2:1} def calc(x): if x in dic: return dic[x] else: dic[x] = calc(x-1)+calc(x-2) return dic[x] print(calc(N))
計算結果
N=30 17ms
N=39 17ms
N=100 17ms
N=1000 18ms
ハハハ・・・・なんて違いだ。
再帰メモ化の恐ろしい強さを確認したところで、今回は終了