はじめに
フィボナッチ数列が好きすぎるので 前回の記事 に引き続いてフィボナッチ数列に関する記事です。前回記事を読了したことを前提として書いているので、まだの方は是非お読みになってから本記事をご覧ください。
前回は普通のフィボナッチ数列をPythonで実装する方法を方法別に紹介しました。フィボナッチ数列プログラミング好きの私としてはこれでは飽き足らず、今回からは拡張された(一般化された)フィボナッチ数列をPythonで実装する方法を考えていきます。
私が調べた限り、プログラミングで一般化フィボナッチ数列を扱っている文献は(少なくとも使用プログラミング言語:Python、文献の言語:日本語では)存在しませんでした。この記事を機にフィボナッチ数列プログラミングの世界が広がっていけばいいなと思っています。
タイトルにPart1と書きました。つまり、Part2以降も続くということです。予定はこちら。
- Part0:Pythonによるフィボナッチ数列の色々な求め方 (前回記事)
- Part1:負の数番を考える (イマココ)
- Part2:項数の一般化
- Part3:初期値の一般化
ではPart1の今回は負数番に対応したフィボナッチ数列をPython3で実装していきましょう。
負の数番への拡張
ご存知の通り、フィボナッチ数列は非負の整数nについて二つの初期条件(初項$F_0=0$,第二項$F_1=1$)を持つ漸化式$F_n=F_{n-1}+F_{n-2}$で表される数列です。しかし、nの範囲は負数を含む整数全体に拡張することができます。
例えば$F_{-1}=1$とすれば$F_1=F_0+F_{-1}=0+1=1$なので漸化式を満たします。このように負の整数nに関しても漸化式を適用すると、下表のように負数番のフィボナッチ数が定義できます。
| $F_{-1}$ | $F_{-2}$ | $F_{-3}$ | $F_{-4}$ | $F_{-5}$ | $F_{-6}$ | $F_{-7}$ | $F_{-8}$ | $F_{-9}$ | $\cdots$ |
|---|---|---|---|---|---|---|---|---|---|
| $1$ | $-1$ | $2$ | $-3$ | $5$ | $-8$ | $13$ | $-21$ | $34$ | $\cdots$ |
では、具体的にPythonでの実装法を考えていきます。
定理を使おう
表を見てお気づきの方もいると思いますが、負数番のフィボナッチ数には次の定理があります。
F_{-n}=(-1)^{n+1}F_n~~~(nは非負の整数)
この定理を使えば簡単に負数番に対応した実装が可能です。
では$F_i~(iは整数)$を求める関数Fib(i)を実装しましょう1。
def Fib(i):
a, b = 0, 1
if i == 0:
positiveResult = a
elif abs(i) == 1:
positiveResult = b
else:
for j in range(abs(i)-1):
a, b = b, a + b
positiveResult = b
if i > 0:
return positiveResult
else:
return positiveResult*(-1)**(abs(i)+1)
定理を素直に実装したらこうなります。
しかし、$i=-1$ でも $i=1$ でも $F_i=1$ ですし、0に正負の概念は(ここでは)ないため以下のように変更できます。
def Fib(i):
a, b = 0, 1
if i == 0:
return a
elif abs(i) == 1:
return b
else:
for j in range(abs(i)-1):
a, b = b, a + b
if i > 0:
return b
else:
return b*(-1)**(abs(i)+1)
では出力を確認してみましょう。
print([Fib(i) for i in range(-9,10)])
# [34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
正しい値が出力できているようです。
ここでは反復法による関数を定理を使って負数まで拡張しましたが、再帰法による関数も同様に変更できます。
やっぱり再帰で
ここまで読んで「負数番のフィボナッチ数も漸化式を満たすんだから、漸化式がそのまま実装されている 前回記事の再帰的な解法 をそのまま使えば、特別なことをしなくても整数全体に拡張できるんじゃない？」と思った方がいるかもしれません。
物は試しです。やってみましょう。
def Fib(n):
if n == 1:
return 0
elif n == 2:
return 1
else:
return Fib(n-1)+Fib(n-2)
print(Fib(-5))
# RecursionError: maximum recursion depth exceeded in comparison
駄目でした。再帰エラーが出てしまいます。何故でしょう？
return Fib(n-1)+Fib(n-2)であるため、Fib(-5)は再帰的にFib(-6)とFib(-7)を呼び出します。Fib(-6)はFib(-7)とFib(-8)を呼び出します。Fib(-7)は...
一向に初期値にたどり着きません。無限再帰に陥ってしまうのです。
それでも諦めてはいけません。引数が負のときに用いる漸化式を工夫すれば解決できます。
$F_n=F_{n-1}+F_{n-2}$ を移項して $F_{n-2}=F_{n}-F_{n-1}$ すなわち $F_{n}=F_{n+2}-F_{n+1}$ と変形できます。これならば引数が負数でも初期値にたどり着き、無限再帰を回避できます。
このことを使って再帰法を整数全体に拡張しましょう。
def Fib(i):
if i == 0:
return 0
elif i == 1:
return 1
elif i > 0:
return Fib(i-1)+Fib(i-2)
else:
return Fib(i+2)-Fib(i+1)
出力を確認してみます。
print([Fib(i) for i in range(-9,10)])
# [34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
成功です。
一般項の式は使える？
フィボナッチ数列には以下のような一般項がありました。
F_n=\frac{1}{\sqrt{5}}\left\{\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right\}
これを使えば整数全体に拡張した関数が書けそうです。やってみましょう。
前回記事の一般項を用いる解法 を少し変えるだけで書けます。
import sympy as sym
def Fib(i):
x = sym.symbols('x',integer=True)
Fib=1/sym.sqrt(5)*(((1+sym.sqrt(5))/2)**(i)-((1-sym.sqrt(5))/2)**(i)) #n-1ではなくiにします
result=Fib.subs(x,i)
result=result.evalf(int(3*abs(i)/14)+1) #abs()を忘れずに
return int(result)
出力を確認してみましょう。
print([Fib(i) for i in range(-9,10)])
# [34, -21, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
成功しています。ほとんどそのまま使うだけなので整数全体への拡張はこの方法が一番簡単ですね。
おわりに
今回はフィボナッチ数$F_k$の$k$の範囲を「非負の整数全体」から「整数全体」に拡張しました。
Part2はフィボナッチ数列の項数を増やします。今回よりも数学要素が強くなります。
誤字脱字や誤った記述、更に良いアルゴリズム、気づいたこと、分かりにくい箇所、感想などがあればぜひコメントをください。
参考文献
-
前回記事と異なり、
Fib(i)はそのまま$F_i$のことを指します。 ↩