フィボナッチ数列

fibonacci.png

フィボナッチ数列の問題は、東大の大学院の試験にも出たし、某MS社の入社試験でも聞かれた。
いや、某M社で出題されたのはパスカルの三角形だったかも?
ご縁がありますねぇ。

Lcrmini.jpg

フィボナッチ数列といえば、最近スーパーでロマネスコブロッコリが売られるようになりました。
買って調理してみたけど、あんまりうまくいかなかった。

フィボナッチ数列とは?

こういう数字の並び。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

最初の二項は0,1と定義され、以後どの項もその前の2つの項の和となっている。

n番目のフィボナッチ数列の数を求める。

よく出る問題が、「n番目のフィボナッチ数列の数を求めるアルゴリズムをかけ!」ってやつですよ。
数学の定義的には

(1)
\begin{align} F_{0}=0\\ F_{1}=1\\ F_{n+2}=F_{n}+F_{n+1} \end{align}

と漸化式になっているのである。
簡単に実装すると、再帰関数を使ってやるのが簡単である。

int fibonacchi(int i){
    if(i==0) return 0;//初期条件その1
    if(i==1) return 1;//初期条件その2
    return fibonacchi(i-1) + fibonacchi(i-2);//漸化式
}

しかし、この簡単に求める方法だと計算時間がかかってしまうのである。
そこで、他の方法もある。

動的計画法を使う方法

動的計画法って???簡単に言うと、記録つきの再帰である。

int *fib=new int[max];
int fibonacchi(int i){
    if(i==0) return 0;
    if(i==1) return 1;
    if(fib[i] !=0) return fib[i];//記録しておいた結果を返す
    fib[i]=fibonacchi(i-1)+fibonacchi(i-2);//結果を記録する
    return fib[i];
}

List of pages tagged with fibonacci:


dynamic-programming recursive

サポートサイト Wikidot.com dynamic-programmingrecursive