2013年8月9日金曜日

フィボナッチ数

とあるテレビドラマでフィボナッチ数について触れられていました。
前の日記にも書きましたが、私は数学の知識があまりなくて、フィボナッチ数とは何か興味を持ちました。

n番目のフィボナッチ数を Fnと表すと
$$F_0 = 0\,$$ $$F_1 = 1 \,$$ $$F_{n+2} = F_n + F_{n+1} \quad (n \ge 0)$$ で定義されるそうです。

この数列はフィボナッチ数列と呼ばれ、
0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,…
と続きます。最初の二項は0,1と定義され、以後どの項もその前の2つの項の和となっています。

フィボナッチ数の一般項が次の様な式で表わされるそうです。

$$\frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} = {{\phi^n - (-\phi)^{-n}} \over \sqrt{5}}$$

ただし、$$\phi = \frac{1+\sqrt{5}}{2}$$ ここで数学音痴の私は、 $$(-\frac{1+\sqrt{5}}{2})^{-1}= \frac{-2}{1+\sqrt{5}}= \frac{-2(1-\sqrt{5})}{(1+\sqrt{5})(1-\sqrt{5})}= \frac{-2(1-\sqrt{5})}{-4}= \frac{1-\sqrt{5}}{2} $$ と手計算してみないと上の式が納得出来ませんでした。

そこで次のような簡単なプログラムで計算してみました。
#include<iostream>
#include<cmath>

int main()
{
    const double phi=(1+sqrt(5))/2;

    for (int n=0; n<17; n++)
    {
        double f=(pow(phi,n)-pow(-phi,-n))/sqrt(5);
        std::cout << "F" << n << "=" << f << std::endl;
    }

    return 0;
}

結果は、
F0=0
F1=1
F2=1
F3=2
F4=3
F5=5
F6=8
F7=13
F8=21
F9=34
F10=55
F11=89
F12=144
F13=233
F14=377
F15=610
F16=987
となり意外と誤差もなく綺麗に出力されました。たぶん表示桁数を増やすと誤差が出てくるのではと思いますが。

0 件のコメント:

コメントを投稿