すずろぐ

人生大逆転を目指す、鈴木俊吾の成長日記

Java フィボナッチ数列を求めるプログラムを書いてみた

プログラミング

こんにちは、すずしんです。

今日はちょこっとプログラミングしまして…。 Java言語でフィボナッチ数列の指定した要素を求めるプログラムを書いてみました。 まぁ非常に簡単なものなのですけどね。

フィボナッチ数列とは?

フィボナッチ数列というのは、「前の2つの数を加えると次の数になる」数列のことを言います。 ただし、初項と第2項の値は1となっています。

例えば、第3項の値は初項と第2項の数の和になりますので2です。 第4項の値は第2項と第3項の数の和で3です。 これを繰り返していくと以下のような並びになります。

[text] 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... [/text]

ここで、フィボナッチ数列の第n項の値を求める関数をfib(n)とします。 フィボナッチ数列の条件を式で表すと以下のような感じになりますね。

[text] fib(1) = 1 fib(2) = 1 fib(n) = fib(n-2) + fib(n-1) (n >= 3) [/text]

フィボナッチ数列の要素を求めるプログラム

試しに、フィボナッチ数列の10、20、30、40、50番目の値を求めるサンプルプログラムFibTestを作成してみました。 ソースコードは以下のとおりです。

fibがフィボナッチ数列の第n項の値を求めるメソッドになっています。 forループの中で10ずつ増やしながらfibメソッドを呼び出すようにしています。 そして、計算して求めた結果をコンソールに出力します。

ちなみに、今回のプログラムではfibメソッドの実行時間をおまけで計測しています。 以前の記事「Java 処理の実行時間を計測するプログラムを書いてみた」で作成したTimerクラスを使っています。 fibメソッドを呼び出す前後で時間を計測して、その結果をフィボナッチ数列の要素の値と共に表示しています。 Timerクラスについての詳細は上記記事を参考にして下さい。

[java] package jp.suzushin7;

public class FibTest { public static void main(String[] args) { Timer timer = new Timer(Timer.MILLISECOND); long value; for(int i = 10; i <= 50; i += 10) { timer.start(); value = fib(i); timer.stop(); System.out.printf("fib(%d) = %d : %.3f ms%n", i, value, timer.getTime()); } }

public static long fib(int n) {
    if(n == 1 || n == 2) return 1;
    return fib(n-2) + fib(n-1);
}

} [/java]

実行結果

このサンプルプログラムFibTestを実行してみた結果は以下のとおりです。 正しく第n項の値が求められていますね。 また、fibメソッドの引数に与えるnが大きくなるにつれて、計算時間が増えていくことが分かります。 ちなみに計算時間の単位はミリ秒です。

[text] fib(10) = 55 : 0.017 ms fib(20) = 6765 : 0.922 ms fib(30) = 832040 : 8.660 ms fib(40) = 102334155 : 808.037 ms fib(50) = 12586269025 : 115598.251 ms [/text]

問題点

このサンプルプログラムFibTestの実行結果を見てもらえると分かると思いますが…。 fib(40)あたりから急激に計算時間がかかっていますよね。 これは、fibメソッド内部で再帰呼び出しを呼び出す回数が爆発的に増えることが主な原因です。 fib(50)にもなると、計算結果が出るまでだいぶ待たされてしまいます。 もしこれ以上先を求めようとすると、途方も無い計算時間がかかることになります。

非常に困りましたね…。 もっと高速に計算する方法は無いのでしょうか? これが実はあるんです! 詳しくは次回の記事を参照して下さい。

まとめ

今回の記事では、フィボナッチ数列の第n項の要素を求めるプログラムを作成してみました。 また、おまけでプログラムの計算時間も計測してみました。 正しく値を求めることができますが、今回のように何も考えず普通に実装すると計算時間がかなりかかってしまうことが分かりました。

そこで私は、この計算時間問題を改善したバージョンのフィボナッチ数列を求めるプログラムを新たに作成してみました。 これについては、次回の記事に詳しく書いてみようと思います。 楽しみにしていて下さいねっ!

関連記事

Java フィボナッチ数列を求めるプログラムを高速化してみた