フィボナッチ数列Pythonを使うと簡単に計算できます。まずは、一番有名なところから・・100以下の数字を計算します。
#1 定義通りの方法でn以下のフィボナッチ数列を計算する
a, b = 0, 1
while b < 100:
print(b,end=' ')
a, b = b, a+b1 1 2 3 5 8 13 21 34 55 89たった4行で計算できるのは恐るべきことです。4行目のような代入計算は素晴らしいです。関数にして10番目までのフィボナッチ数列を求めます。
#2 n番目までのフィボナッチ数列をリストにする関数
def fib_l(cnt):
a, b = 0, 1
fib_l=[]
while cnt:
cnt-=1
fib_l.append(b)
a, b = b, a+b
return fib_l
fib_l(10)[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
次に10番目の値を再帰関数を使って計算します。答えは55です。
#3 再帰関数でn番目のフィボナッチ数列を計算する
def fib_r(seq):
if seq <= 1:
return seq
return(fib_r(seq-1) + fib_r(seq-2))
fib_r(10) 再帰関数の傑作です。しかし、これだけでは計算量が多すぎて、40番目くらいでもえらく時間がかかります。このため、メモ化という技術を使います。答えは、102334155です。
#4 再帰関数のメモ化を利用してフィボナッチ数列を計算する
memo = {}
def fib_m(seq):
if seq < 3:
return 1
if seq not in memo:
memo[seq] = fib_m(seq-1) + fib_m(seq-2)
return memo[seq]
print(fib_m(40)) あっという間に答えは求まりますが、辞書を使っているので結構複雑です。そこでPythonにはlru_cacheキャッシュという恐るべきデコレーターがあります。LRUとは、Least Recently Usedの略で#3の効率の悪い再帰関数のプログラムもメモ化の機能を取り込んでくれます。
#5 lru_cacheを使って再帰関数の計算を高速化する
from functools import lru_cache
@lru_cache(maxsize=1024)
def fib_r(seq):
if seq <= 1:
return seq
return(fib_r(seq-1) + fib_r(seq-2))
fib_r(100) 100番目のフィボナッチ数列も瞬く間に、354224848179261915075と計算されます。
import sympy
fib = sympy.fibonacci(100)
fibSymPyモジュールにはfibonacci関数があります。計算すると前のプログラムの結果と合致します。
#6 SymPyモジュールによるフィボナッチ数列の計算
import sympy
fib = sympy.fibonacci(100)
fib
