Javaでフィボナッチ数列のアルゴリズムを考えてみよう

今回もプログラムの基礎として学ぶことのあるアルゴリズムを勉強していこうと思います。

フィボナッチ数（Fibonacci number）とは、イタリアの数学者レオナルド・フィボナッチにちなんで名付けられた数である。


概要

n番目のフィボナッチ数をFnで表すと

F0=0
F1=1
Fn+2=Fn+Fn+1　(n>0)

で定義されます。

この数列はフィボナッチ数列（Fibonacci sequence）と呼ばれ、

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …と続く。

引用：フィボナッチ数 - Wikipedia

簡単に説明すると
A+B=C
B+C=D
C+D=E
ということです。

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

0　0
1　1
2　0+1=1
3　1+1=2
4　1+2=3
5　2+3=5
6　3+5=8
7　5+8=13
8　8+13=21
9　…と続く。

アルゴリズムをそのままコードにしてみました。

class Fibonacci {
    public static void main(String[] args) {
        long F0=1,F1=1,Fn;
        System.out.println(F0+"\n"+F1);
        for(int i=1;i<50;i++) {
            Fn=F0+F1;
            System.out.println(Fn);
            F0=F1;
            F1=Fn;
        }
    }
}

また、
F : フィボナッチ数
n : 項数
と定義することで
Fn = (Fn-2)+(Fn-1)
の式により再帰的にその項のフィボナッチ数を取得することが出来ます。

実際にコードに書き出してみました。

class Fibonacci2 {
    public static void main(String[] args) {
        System.out.println("第"+args[0]+"項:"+fibo(Integer.parseInt(args[0])));
    }
    static long fibo(int n) {
        long F;
        System.out.println("fibo("+n+")");
        if(n<=0) return 0;
        if(n==1 || n==2) return 1;
        F=(fibo(n-1)+fibo(n-2));
        System.out.println("return fibo("+n+")="+F);
        return F;
    }
}

起動する時に「java Fibonacci2 5」「java Fibonacci2 11」の様に引数を与えることで、その引数の位置のフィボナッチ数を取得出来ます。

例：n=5の場合
$ java Fibonacci2 5
fibo(5)
fibo(4)
fibo(3)
fibo(2)
fibo(1)
return fibo(3)=2
fibo(2)
return fibo(4)=3
fibo(3)
fibo(2)
fibo(1)
return fibo(3)=2
return fibo(5)=5
第5項:5

F5=F4+F3
=(F3+F2)+(F2+F1)
=((F2+F1)+1)+(1+1)
=((1+1)+1)+(1+1)
=(2+1)+2
=3+2
=5

F5-F4-F3-F2=1
| | |
| | LF1=1
| LF2=1
|
L F3-F2=1
|
LF1=1



おまけ

「フィボナッチ数の計算速度を向上させる」

参考：フィボナッチ数を「速く計算」する - 雑食系猫的楽書帳

class Fibonacci3 {
    public static void main(String[] args) {
        System.out.println("第"+args[0]+"項:"+fibo(Integer.parseInt(args[0])));
    }
    static long fibo(int n) {
        if(n<=0)return 0;
        if(n==1 || n==2)return 1;
        long F,Fn1,Fn2;
        F=1;Fn1=1;
        for(int i=3;i<=n;i++) {
            Fn2=Fn1;
            Fn1=F;
            F=Fn1+Fn2;
        }
        return F;
    }
}

再帰的だと1を足しあわせ続けることになる。
手計算の場合、直前の二項しか計算に使用しないので、それ以前の項は捨ててしまってもいいという考えのようです。