フィボナッチ数列

Python

「博士の愛した数式」という本に影響されて数学関係の本を読んでたら「フィボナッチ数列」というのを知りました。
「１つ後ろの数 ＋ ２つ後ろの数 ＝ 自分の数」
という規則に従って並んだ数列のことをフィボナッチ数列と呼ぶのだそうです。

1,1,2,3,5,8,13,21,34,...

こんな感じ。
1番目と2番目の数は両方とも1なのだそうです。


「プログラムで書いてみよう」という気になり、最近勉強中のpythonで書いてみました。

1から100までのフィボナッチ数を出力するプログラム

#!/usr/bin/python
# -*- coding: utf-8 -*-

# n番目のフィボナッチ数を計算する関数
def fibo( n ):
  # 1番目は1
  if n == 1:
    return 1
  
  # 2番目も1
  if n == 2:
    return 1
  
  # 3番目以降は１つ後ろの数＋２つ後ろの数
  return fibo( n - 1) + fibo( n - 2 )


# ここからスタート
for i in range( 1, 101 ):
  print i, '\t',  fibo( i )

実行してみるとこんな感じで順調に出力されているように見えました。

1 	1
2 	1
3 	2
4 	3
5 	5
6 	8
7 	13
8 	21
9 	34
10 	55
...

遅い

30くらいまでは順調に出力されたのですが、40からスピードが落ちてきて、ジャンプを買いに行って帰ってきて読み終わってもまだ計算を続けていました。
これはいけません。なんとか改良しましょう。

一回計算した値を覚えておこう

例えば10番目の数を計算するとき、人間が紙の上で計算するんだったら「あぁ、34+21で55だな」と一瞬で分かるのですが、上のプログラムだと「10番目の数」を計算するために「9番目の数」と「8番目の数」の数を計算によって求めないといけなくて、「9番目の数」を計算するためにはまた「8番目の数」と「7番目の数」を計算しないといけなくて、さらに「8番目の数」を計算するには…、というように、膨大な数の計算をしないといけないのでとても効率が悪かったようです。
人間がやるのと同じように一度計算した数をメモしておいて、次に「n番目の数」が必要になったときはそのメモを参照するようにしたら効率がよいのではないかと思いました。

改良したプログラム

#!/usr/bin/python
# -*- coding: utf-8 -*-

# フィボナッチ数列のクラス
class Fibonacci:
  nums = {} # 計算した数を入れておくマップ。

  # コンストラクタ
  def __init__( self ):
    self.nums[1] = 1 # 先頭の数は1
    self.nums[2] = 1 # 2番めの数も1

  # n番目のフィボナッチ数を計算する関数
  def calc( self, n ):
    # 計算したことのない数だったら計算してnumsに入れておく
    if n not in self.nums:
      self.nums[n] = self.calc( n - 1 ) + self.calc( n - 2 )
    return self.nums[n]


# ここからスタート
f = Fibonacci()
for i in range( 1, 101 ):
  print i, '\t',  f.calc( i )

改良したプログラムを実行してみたら、1時間走らせても終わらなかった計算が1秒もかからずに100まで完了してしまいました。すばらしいです。