D04 フィボナッチ数列
F1 = 1
F2 = 1
Fn+2 = Fn+1 + Fn (n = 1,2,...)
で定義されるフィボナッチ数列の一般項を返すコマンドを3通りの方法で作成してみます。
行列のn乗を用いる方法
行列のn乗を用いる方法
n = 8
m = x({ {1,1},{1,0} }^n (0,1))
本質的には3項間漸化式で述べた方法ですが、漸化式に定数項がないので2次の行列でプログラムでき、初期値を与える2次の列ベクトルの代わりに点の座標を用いています。出力オブジェクト m、入力オブジェクト n でツールも作成できます。
漸化式を解いた一般項を用いる方法
漸化式を解いた一般項を用いる方法
φ=(1+√5)/2 を黄金比とすると、フィボナッチ数列の第n項は、
Fn = (φn - (-φ)-n ) / √5
と書けることを利用すると、次のようにも定義できます。
n = 8
gr = (1+sqrt(5))/2
m = (gr^n - (-gr)^(-n)) / sqrt(5)
近似値を用いる方法
近似値を用いる方法
φ-n は0に近いことを利用すると、
Fn = (φn / √5 + 0.5) の整数部分
とも書けるので、
n = 8
m = floor( (1+sqrt(5))^n / (2^n sqrt(5)) + 0.5 )
とも定義できます。先ほどよりも誤差を吸収してくれる可能性はあります。