フィボナッチ (fibonacci) 数はイタリアの数学者レオナルド・フィボナッチにちなんで名付けられた数です。今回はフィボナッチが考案したウサギの問題を解いてみましょう。
１つがいのウサギがいます。ウサギは１ヶ月経つと１つがいの子ウサギを生みます。生まれたウサギは２ヶ月目には子ウサギを生むものとします。ウサギは死なないものとすると、１年後にウサギは何つがいになるでしょうか。
ウサギを親、子、生まれたウサギに分けて表を作ると次のようになります。
: 親 : 子 : 生 : 計 ---+----+----+----+----- 0 : 1 : 0 : 0 : 1 1 : 1 : 0 : 1 : 2 2 : 1 : 1 : 1 : 3 3 : 2 : 1 : 2 : 5 4 : 3 : 2 : 3 : 8 5 : 5 : 3 : 5 : 13 6 : 8 : 5 : 8 : 21 7 : 13 : 8 : 13 : 34 8 : 21 : 13 : 21 : 55 9 : 34 ; 21 : 34 : 89 10 : 55 : 34 : 55 : 144 11 : 89 : 55 : 89 : 233 12 :144 : 89 :144 : 377
１月に子ウサギを生むとすると、答えは 377 つがいになります。１月に子を生まない (まだ親ウサギになっていない) とすると 233 つがいになります。Fn を n ヵ月後のつがいの数とすると、Fn = Fn-1 + Fn-2 の関係が成立していることがわかります。数学では、次の漸化式で生成される数列を「フィボナッチ数列」といいます。
┌ 0; n = 0
F(n) = ┤ 1; n = 1
└ F(n-1) + F(n-2); n > 1
フィボナッチ数列は 0, 1, 1, 2, 3, 5, 8, 13 .... という直前の 2 項を足していく数列になります。
それでは、ここで問題です。
フィボナッチ数を求めるプログラムは簡単です。Python でプログラムすると次のようになります。
リスト : フィボナッチ数
def fibo(n):
a1, a2 = 0, 1;
while n > 0:
a1, a2 = a2, a1 + a2
n -= 1
return a1
i = 0
while True:
if fibo(i) >= 300000000: break
i += 1
print(i-1)
print(fibo(i-1))
答えは F42 = 267914296 になります。また、次のようにメモ化関数を使うと二重再帰のプログラムでも高速に求めることができます。
リスト : メモ化関数
def memoize(f):
table = {}
def func(*args):
if not args in table:
table[args] = f(*args)
return table[args]
return func
@memoize
def fibo(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibo(n - 2) + fibo(n - 1)
メモ化関数については、拙作のページ Algorithms with Python 再帰定義 をお読みくださいませ。
さらに、次の公式を使うと筆算でも簡単に求めることができます。参考 URL 3 によると、フィボナッチ数は次の近似式で求めることができるそうです。
Fn = φn / √5 (φ = (1 + √5) / 2)
したがって、n は次の式で求めることができます。
n = floor(log(300000000) / log(φ))
>>>> from math import * >>>> phi = (1 + sqrt(5)) / 2 >>>> phi 1.618033988749895 >>>> floor(log(300000000 * sqrt(5)) / log(phi)) 42.0
参考 URL 3 によると、上記近似式の誤差は 0.5 未満になるとのことなので、フィボナッチ数は次の式で求めることができます。
Fn = floor(φn / √5 + 0.5)
>>>> floor(phi ** 42 / sqrt(5) + 0.5) 267914296.0
Python の場合、内包表記を使うと簡単です。
>>>> sum([fibo(x) for x in xrange(43)]) 701408732
次の公式を使うともっと簡単に和を求めることができます。
F1 + F2 + ... + Fn = Fn+2 - 1
各項を Fn = Fn+2 - Fn+1 の関係を使って書き直すと次のようになります。
F1 = F3 - F2 F2 = F4 - F3 F3 = F5 - F4 ・・・・・ Fn-2 = Fn - Fn-1 Fn-1 = Fn+1 - Fn Fn = Fn+2 - Fn+1 -------------------------- ΣFn = Fn+2 - F2 = Fn+2 - 1
答えは F44 - 1 になります。
>>>> floor(phi ** 44 / sqrt(5) + 0.5) - 1 701408732.0
ご参考までに、偶数番目の項の総和と基数番目の項の総和の公式を示します。
F2 + F4 + ... + F2n = F2n+1 - 1 F1 + F3 + F5 + ... + F2n-1 = F2n
これらの公式は項 Fn を Fn-2 + Fn-1 に書き換えると求めることができます。
(F0 + F1) + (F2 + F3) + (F4 + F5) + ... + (F2n-2 + F2n-1) = F2n+1 - 1 (F2n-1 までの総和) F1 + (F1 + F2) + (F3 + F4) + ... + (F2n-3 + F2n-2) = F2n (F2n-2 までの和 + F1)
フィボナッチ数列は F1 = 1 (奇), F2 = 1 (奇) なので、F3 = 1 (奇) + 1 (奇) = 2 (偶), F4 = 1 (奇) + 2 (偶) = 3 (奇), F5 = 2 (偶) + 3 (奇) = 5 (奇), F6 = 3 (奇) + 5 (奇) = 8 (偶) になります。つまり、n が 3 の倍数のとき項の値は偶数になるわけです。
この性質を利用すると、偶数となる項の総和は次のように求めることができます。
>>>> sum([fibo(x) for x in xrange(43) if x % 3 == 0]) 350704366
偶数の項の総和を求める公式は、次のように導出することができます。
S = F3 + F6 + ... + F3(n-1) + F3n とし、各項を Fn = Fn-2 + Fn-1 の関係を使って書き直すと S = (F1 + F2) + (F4 + F5) + ... + (F3n-2 + F3n-1) 足し算すると 2S = F1 + F2 + F3 + ... + F3n-2 + F3n-1 + F3n (F3n までの総和) = F3n+2 - 1 => S = (F3n+2 - 1) / 2
このように、F3n までの偶数項の総和は F3n までの総和の半分になります。
>>>> (floor(phi ** 44 / sqrt(5) + 0.5) - 1) / 2 350704366.0
参考 URL 4 によると、『ゼッケンドルフの定理は、任意の正の整数が、連続するフィボナッチ数を含まないような形で、相異なる 1 つ以上のフィボナッチ数の和として一意に表現できるというものである。』 とのことです。これを「ゼッケンドルフの表現」と呼ぶそうです。正整数 N のゼッケンドルフの表現は、『各段階で可能な最大のフィボナッチ数を選ぶ貪欲法によって得ることができる。』 そうです。
これをそのまま単純にプログラムすると次のようになります。
リスト : ゼッケンドルフの表現
def solver(n):
def max_fibo(n):
i = 1
while fibo(i) <= n: i += 1
return fibo(i - 1)
print n, ":",
while n > 0:
x = max_fibo(n)
print x,
n -= x
300000000 : 267914296 24157817 5702887 2178309 46368 233 89 1
局所関数 max_fibo() で n 以下の最大のフィボナッチ数を求めます。あとは、max_fibo() でフィボナッチ数を求め、それを n から引き算していくだけです。