fibonacci, pisano period
date: 2021-03-05 excerpt: フィボナッチ数列とピサーノ期間について
フィボナッチ数列について
フィボナッチ数列の定義
\[f(n) = f(n-1) + f(n-2)\]ただし
- \[f(0) = 0\]
- \[f(1) = 1\]
メモ化を利用したフィボナッチ数列の実装
def _fib(n, memo):
if not n in memo:
memo[n] = _fib(n-1, memo) + _fib(n-2, memo)
return memo[n]
def fib(n):
memo = {0:1, 1:1}
return _fib(n, memo)
n = 6
res = fib(n)
print(res) # 13
ピサーノ期間(pisano period)について
- ピサーノ期間とはフィボナッチ数列のモジュロを任意の数字で計算すると、周期性があること
例えば20までの2,3,4のモジュロを計算したものは以下のようになる
MOD=2, 周期=[0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1]
MOD=3, 周期=[0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2]
MOD=4, 周期=[0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1]
この性質を利用することで高速に計算することが可能になる