【Java】フィボナッチ数列を考える①

FizzBuzz問題と並んでプログラミング初心者向けにフィボナッチ数列というものがあります。実は自分で書いたことがなかったので今回はJavaで書いてみたいと思います。

配列で実装


フィボナッチ数列は1番目の値と2番目の値を足すと3番目の値になります。言い方を変えるとひとつ前とふたつ前の値を足した数が次の数ということです。

ということで言葉通りに実装したいと思います。方針としては可変の配列を作り、値を求めるためにひとつ前とふたつ前の値を取り出して足していきます。1番目の値は0、2番目の値は1として以下のように実装しました。

実行結果

ここの部分がひとつ前とふたつ前の数字を足して現在値を求めているところになります。

数列の意味をそのままソースに落としているのでよく読めばわかりやすいですが、どうも助長なような…もう少し良い書き方があるような気がもします。

 

フィボナッチ数列といえば再帰処理


フィボナッチ数列と言えば再帰処理です。再帰処理とは関数内で自分自身を呼び出すことを言います。

色々なサイトで詳しく書かれているのでここでは説明を省きますが、

Fn = (Fn-1) + (Fn-2)の式で再帰的にフィボナッチ数を求めることができます。

この式を使うと以下のように書けます。

実行結果

非常にすっきりしたコードになりました。直感でそのままプログラミングしてもいいのですが、こうした数学の知識や再帰処理といったものを使うことでここまでスマートに書けるのですね。

ただし、この再帰処理のコードですが、とても遅いのです…。何故なら毎回自分自身を呼び出すためとても無駄が多いです。

ということで次回は高速化に挑戦したいと思います。

スポンサーリンク

返信を残す

メールアドレスが公開されることはありません。