はじめに
フィボナッチ数列とは、「最初の二項は 0, 1 であり、以後どの項もその直前の2つの項の和となっている数列」です。（ウィキベディアより）
フィボナッチ数列
0
1
1 （0 + 1）
2 （1 + 1）
3 （1 + 2）
5 （2 + 3）
8 （3 + 5）
13 （5 + 8）
この数列のn番目の項を求めるとき、そのまま実装するとこのようになります。
def fib(n):
"""
０始まりでn番目のフィボナッチ数を求める。
"""
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1) + fib(n-2)
print(fib(7)) # -> 13
実際に実行してみると、とても遅いことがわかります。
例えば、n=100でも相当な時間がかかります。
その原因は、詳細は割愛しますが、同じ計算を何度も行なっている点にあります。
例えば、fib(8)は、fib(7)とfib(6)をそれぞれ求めた上で足し合わせて求められますが、fib(7)を求めるためにはfib(6)を新たに求める必要があります。
「同じ計算を二度しない」をキーワードに、高速化をしてみましょう。
メモ化と動的計画法の二つのアルゴリズムを紹介します。
メモ化
一度計算した結果を保存しておきます。
使える場合はそれを使い、そうでない場合は新たに計算し、その結果を次回以降のために保存しておきます。
MAX_N = 100
MEMO = [None] * (MAX_N + 1) # 計算結果を保存する配列
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
# 計算済み？
if MEMO[n]:
return MEMO[n]
r = fib(n-1) + fib(n-2)
MEMO[n] = r # 計算結果を保存
return r
print(fib(100))
n=100の場合でもすぐに結果が帰ってきました。
動的計画法（DP）
再帰関数を使わなくても、nが小さい方から計算することで、フィボナッチ数を求めることができます。
MAX_N = 100
DP = [None] * (MAX_N + 1) # 計算結果を保存する配列
DP[0] = 0 # 定義より
DP[1] = 1 # 定義より
def fib(n):
# フィボナッチ数を2からnまで順に求めていく
for i in range(2, n + 1):
DP[i] = DP[i-1] + DP[i-2]
return DP[n]
print(fib(100))
動的計画法については、参考資料を見てください。