フィボナッチ数列
$ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ... といったように前$ 2つの数字を足したものが次の項の値になる数列をフィボナッチ数列という。
$ a_{n} = a_{n - 1} + a_{n - 2} \quad (n \geq 3, \quad a_1 = 1, \quad a_2 = 1)
フィボナッチ数列は、初項と第$ 2項が分かれば任意の項について求めることができる。
一般項は、$ a_n = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1 + \sqrt{5}}{2} \right) ^ n - \left( \frac{1 - \sqrt{5}}{2} \right) ^ n \right\} で表される。
母関数は、$ g(x) = \sum_{n=0}^{\infty} a_n x^n = \frac{x}{1 - x - x^2}で表される。
また、隣接する$ 2項の商が黄金比 $ \phi := \frac{1 + \sqrt{5}}{2}に収束する性質 $ \lim_{n \rightarrow \infty} \frac{a_n}{a_{n - 1}} = \phi が存在する。
フィボナッチ数列の逆数和は収束する。
また、任意のフィボナッチ数列の項 $ a_i は、$ a_i = a_1 * x + a_2 * y で表すことができる。
具体的には、
$ a_3 = a_2 + a_1
$ a_4 = a_3 + a_2 = 2a_2 + a_1
$ a_5 = a_4 + a_3 = 3a_2 + 2a_1
$ a_6 = a_5 + a_4 = 5a_2 + 3a_1
$ a_7 = a_6 + a_5 = 8a_2 + 5a_1
といった感じで、$ x, y に関してはあらかじめ計算しておくことが可能である。
この考えが後の行列累乗につながってきたりもする。
/icons/hr.icon
フィボナッチ数列の求め方
再帰で求めるフィボナッチ数列
とにかく遅い
絶対に書いてはいけない
$ 1年生のプログラミングの講義で出題されがち。
一応 C 言語でも書いたりしておく。
たぶん新入生はこれに苦戦してると思います。分からなければ気軽に DM でもしてください。 code:main.c
int fib(int n) {
if (n <= 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}
int main(void) {
int n;
scanf("%d", &n);
printf("%d\n", fib(n));
return 0;
}
code:main.py
def fib(n: int):
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
print(fib(int(input())))
/icons/hr.icon
メモ化再帰で求めるフィボナッチ数列
$ O(N) で計算ができるのでまあまあ早い
code:main.py
n = int(input())
for i in range(2, n):
/icons/hr.icon
行列累乗で求めるフィボナッチ数列
計算量は $ O(\log N)
繰り返し二乗法を使用して高速化
めちゃめちゃ速い
code:Fibonacci.py
def matrix_multi(a: list, b: list) -> list:
len_a, len_b, len_b_zero = len(a), len(b), len(b0) c = [0 * len(b0) for _ in range(len_a)] for i in range(len_a):
for j in range(len_b_zero):
for k in range(len_b):
return c
def matrix_pow(a: list, n: int) -> list:
len_a = len(a)
cnt = [0 * len_a for _ in range(len_a)] for i in range(len_a):
while n > 0:
if n & 1:
cnt = matrix_multi(a, cnt)
a = matrix_multi(a, a)
n >>= 1
return cnt
n = int(input())
mod = 998244353
fibonacci = 1, 1], [1, 0
fibonacci = matrix_pow(fibonacci, n)
# print(*fibonacci, sep="\n")
print(ans)
/icons/hr.icon
練習問題
Fibonacci-like Sequences
概要は以下の通り
$ a_{n + 2} = a_{n + 1} + a_n のフィボナッチ数列について、 $ K がフィボナッチ数列に含まれるような $ a_1, a_2 を出力せよ。
・$ 1 \leq K \leq 10^{8}
・$ 1 \leq L \leq R \leq K
・$ L \leq a_1, a_2 \leq R
解説
$ K が含まれるような数列の項数は高々 $ O(\log K) 項であるため、そこまでを全探索する。
仮に、$ a_i = a_{i -1} + a_{i - 2} = K を満たすような $ i が存在した場合、$ a_i = a_1x + a_2yを満たすような$ a_1, a_2を考える。
ここで、$ a_2y = K - a_1x \geq K - Rx \Leftrightarrow a_2 \geq \frac{K - Rx}{y}を満たす $ a_2 を探す。
次に、$ a_1x = K - a_2y \Leftrightarrow a1 = \frac{K - a_2y}{x} を満たすような $ a_1 を求めれば、解が得られる。
code:main.py
K, L, R = map(int, input().split())
dp = 1, 0], [0, 1
for i in range(100):
for i in range(3, 100):
a2 = (K - R * x + y - 1) // y
if (K - a2 * y) % x != 0:
continue
a1 = (K - a2 * y) // x
if L <= a1 <= R and L <= a2 <= R:
if a1 * x + a2 * y == K:
exit(print(a1, a2))
print(-1)