Remrinのpython攻略日記

python3に入門しました。python3についてあれこれとサンプルコードとか。

フィボナッチ数列

フィボナッチ数列について。
 

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return b

print([fib(i) for i in range(10)])  
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

 
メモ化した場合

fib_memo = {}
def fib(n):
    if n < 3: return 1
    if n not in fib_memo:
        fib_memo[n] = fib(n-1) + fib(n-2)
    return fib_memo[n]

print(fib(10)) # 55

 
このメモ化だと、fib_memoという辞書が使用後も残ってしまったり、
n>1000だとrecursive errorが出たりする。
 
@lru_cacheデコレータ(Least-recently-used cache decorator)を使う。
関数の引数と戻り値を記憶し、同じ引数で呼ばれたら関数を実行せずに値を返す。
同じ引数で何度も呼び出す関数だと劇的に速くなる。

counter = 0
def fib1(n):
    global counter
    counter += 1
    if n in [0, 1]:
        return 1
    return fib1(n - 1) + fib1(n - 2)

print(fib1(24))
print(counter, "回の関数呼び出し")
# 75025
# 150049 回の関数呼び出し
    
    
from functools import lru_cache
counter = 0
@lru_cache(maxsize=1024)
def fib2(n):
    global counter
    counter += 1
    if n in [0, 1]:
        return 1
    return fib2(n - 1) + fib2(n - 2)

print(fib2(24))
print(counter, "回の関数呼び出し")
# 75025
# 25 回の関数呼び出し

 
lru_cacheなしだと関数を15万回呼び出していたが、lru_cacheありだと25回で済む。
 
 
一般項の公式
f:id:rare_Remrin:20170519152551p:plain
より、ループなしでフィボナッチ数列の項を求めることもできます。

def fib(n):
    f = ((1 + 5**0.5) / 2)**n / 5**0.5 + 0.5
    return int(f)

print(fib(10)) # 55

 
2項間の比を調べてみると

import numpy as np
import matplotlib.pyplot as plt

x = np.arange(20)
y = np.array([fib(i + 1) / fib(i) for i in range(20)])
plt.plot(x, y, "ro-")
plt.show()

 
f:id:rare_Remrin:20170519145736p:plain

1.62くらいに収束してます。