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
となり意外と誤差もなく綺麗に出力されました。たぶん表示桁数を増やすと誤差が出てくるのではと思いますが。

2013年8月1日木曜日

Libeofficeとか

日記しばらく更新してませんでしたが一応生きています。

UbuntuにもLibreOfficeを入れているんですが、デフォルトで入ってるバージョンを消して、インストールしようとしたら、どうにもならない感じに壊れたみたいで、Ubuntu13.10をクリーンインストールして、12.10の環境から必要なものを移すとかの作業をやってました。
 この際だからデフォルトのシェルはbashを試しに使ってみてます。補完機能がtcshに比べるとすっきり行かない感じがしますが、なんとか使えてます。gccは4.7.3のままです。後2ヶ月するとUbuntu13.10が出てgcc4.8がデフォルトで入ると思うので、そこまでC++11を使ってない僕には4.7.3でもまあ大丈夫です。たまにコンパイル通らないのがありますが、そこは書き換えてみるとかでやってます。
とりあえず、近状報告でした。