Java
Java
再帰アルゴリズムの覚え書きの続きです。
再帰アルゴリズム その１
今回も、非効率的かつ非現実的な例題を利用して再帰アルゴリズムを理解していきましょう。
今回はフィボナッチ数列の特定項の値を求めるプログラムです。
フィボナッチ数列とは簡単に説明すると
F1 = 1
F2 = 1
F3 = 2
・
・
・
Fn = F(n – 2) + F(n – 1)
ただし、n = 1 または n = 2 のとき F(n) = 1 となる数列のことである。
つまり、1, 1, 2, 3, 5, 8, … と続く数列で、 隣り合う2つの数を足し算すると、その上位の数になる数列です。
参考までに、フィボナッチ数は、ちょうど８００年前に刊行された「算盤の書」（１２０２年）の中の有名な「兎の問題」から生まれました。
これをプログラムにするにはどうしたらいいでしょうか？
数学的手法でいくか？ループ文で和を取り値を入れ替えながら？
面倒なのでここは再帰アルゴリズムを使いましょう。(^_^;
計算処理負荷が非常に大きいことは秘密にしておきましょう。（ヲヒ
とりあえずサクッと作ってみたのでデバッグ実行させてプログラムの流れを確認してみましょう。
| jp\yucchi.fibonacci.number.FibonacciNumber.java |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
package jp.yucchi.fibonacci.number; /** * * @author Yucchi */ public class FibonacciNumber { private static final int TARGET = 5; private static int ans; public static void main(String[] args) { ans = fib(TARGET); System.out.println("フィボナッチ数列第 " + TARGET + " は " + ans + " です。"); } private static int fib(int n) { if (n == 1 || n == 2) { return 1; } else { ans = fib(n - 2) + fib(n - 1); return ans; } } } |
上記のプログラムをデバッグ実行させます。
変数、n , ans の値、再帰呼び出し及び処理から戻ってくる時のプログラムの流れをしっかり確認してくださいませ。
しっかり確認できましたでしょうか？
概略図を作って流れを考察してみます。
fib(5) から fib(5 – 2) そして fib(3 – 2)
処理を終え fib(5 – 2) に戻り次の fib(3 –1)
処理を終え fib(5 – 2) に戻り fib(5 – 2) の処理を終え fib(5) に戻る
そして fib(5 –1) へ、そして fib(4 – 2) へ、処理を終えて fib(5 – 1) へ戻る
次の fib(4 – 1) へ、そして fib(3 – 2) へ、処理を終えて fib(4 – 1) へ戻る
そして fib(3 – 1) へ、処理を終えて fib(4 – 1) へ戻る、処理を終えて fib(5 – 1) へ戻る、処理を終えて fib(5) に戻る
これでやっと呼び出し元に計算処理を結果を返せるって仕組みです。
あ～、しんど (~_~;)
再帰アルゴリズムってプログラムだとシンプルだけど流れを考えるとしんどいですね。
えっ？私だけ？
まぁ、いいか。
ちなみに再帰アルゴリズム使わないプログラムは下記のようになります。
| jp.yucchi.fibonacci.number2.FibonacciNumber2.java |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
package jp.yucchi.fibonacci.number2; /** * * @author Yucchi */ public class FibonacciNumber2 { private static final int TARGET = 5; public static void main(String[] args) { System.out.println("フィボナッチ数列第 " + TARGET + " は " + fib(TARGET) + " です。"); } private static int fib(int n) { int x = 1; int y = 1; for (int i = 2; i < TARGET; i++) { int z = x + y; y = x; x = z; } return x; } } |
さて、どちらが効率いいですか？
TAGS: Java |
2013年1月2日4:56 AM |
Java
再帰アルゴリズムについてちょっとしたメモを残しておきます。
まず再帰とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいうらしいです。
日本語って難しいですね。
プログラムを組む上でコーディングテクニックについては自分と同じ（自分自身）をある条件が満たされるまで呼び出し続けることのようです。
これって for 文もしくは while 文でもいけそうですね。
とりあえず非効率的かつ非現実的ではありますが 3 の階乗値を求めるプログラムを作ってみましょう。
| jp.yucchi.recursion.example.RecursionExample.java |
|
|
package jp.yucchi.recursion.example; /** * * @author Yucchi */ public class RecursionExample { private static final int TARGET = 3; public static void main(String[] args) { System.out.println("n の階乗値は " + fact(TARGET) +" です。"); } private static int fact(int n) { return n == 0 ? 1 : n * fact(n - 1); } } |
非常にシンプルです。
10 行目の標準出力処理の中にある fact(TARGET) メソッドで再帰メソッドを呼び出してます。
再帰メソッドが 13 行目の fact(int n) です。
14 行目から条件次第で再び呼び出されます。
全ての処理が帰ってきてから標準出力に fact(TARGET) の戻り値が出力されます。
これだったらループ文でも大差ないだろうと思った あ・な・た 正解です。(^_^;
しかし、この再帰アルゴリズムは奥が深いんです。
そのことはまた今度ってことで今回はこのシンプルなプログラムの流れをデバッガを使い確認してみます。
上記のプログラムのままでもいいのですが、ちょっと解りやすくするために下記のように変更します。
| jp.yucchi.recursion.example.RecursionExample.java |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
package jp.yucchi.recursion.example; /** * * @author Yucchi */ public class RecursionExample { private static final int TARGET = 3; public static void main(String[] args) { System.out.println("n の階乗値は " + fact(TARGET) +" です。"); } private static int fact(int n) { int temp = n == 0 ? 1 : n * fact(n - 1); return temp; } } |
それではプログラムの流れを変数 n , temp を確認しながらご覧ください。
どうですか？
処理が最初の呼び出し元に戻るまで追うことができましたでしょうか？
コードはすっきりとなってるけどプログラムの流れはけっこう追っていくのは大変です。
論理的に考えて組んでしまえばこのかったるい処理はコンピューターがやってくれるので非常に便利です。
今回は再帰アルゴリズムの基本中の基本のメモでした。
TAGS: Java |
2013年1月1日4:42 PM |
Java NetBeans
JDK 8 で待望の？ Lambda 式が使えるようになる予定です。
しかし、統合開発環境に慣れ親しんだものとしてはそれを試そうとするのはしんどいですね。
そこで我らがヒーロー、NetBeans が早くも対応をはじめてきたようです。
JDK8 Support in NetBeans
http://wiki.netbeans.org/JDK8
Java™ Platform, Standard Edition 8 Early Access with Lambda Support
http://jdk8.java.net/lambda/
ふっふっふっ！
どうだ！と言わんばかりにラムダ式にコンバートするチェックボックスがデフォで ON になってます。
さて、本当にコンバートしてくれるか試してみましょう。
ちょっと待て！
今日も明日も夜勤なのにこんなことしてていいのか？！
昨日は大きな災害が発生したというのに・・・
でも気になって眠れないといけないからちょっとだけ(^_^;
おおっ！ やってくれますね（＾＾）
ただ、どこまで対応してきるのか興味津々です。
おっと、そういえば Lambda って今の状況がどうなっているんだろう？
今年のお正月休みにでも時間があれば調べてみよう（＾＾）
楽しみ！楽しみ♪
TAGS: Java,NetBeans |
2012年12月20日11:53 AM |
Java NetBeans Solaris
Solaris 11.1 をお試しでインストールしたついでに Java 7 u 10 をインストールして NetBeans 7.3 Beta 2 もインストールしてみた。
HTML5 ってのがありますね。
サンプルプロジェクトを開いてみました。
とても綺麗に機能的によくできてます。
これでビジュアル編集とかできれば何も言うことはないでしょうが NetBeans のような高機能エディタを使う人は
HTML をガリガリするほうがしっくりくる人種なんでしょう。
CSS のプロパティもわかりやすくなってますね。
いたれりつくせりです！
プロジェクトを実行させてみようと思ったらこんなダイアログウィンドウが出てしまった（＞＜）
どうやら実行可能な環境に足らないものがあるようです。
とりあえず NetBeans 7.3 は HTML5 にも力をいれていくようです。
どんどん進化する NetBeans が楽しみですね（＾＾）
TAGS: Java,NetBeans,Solaris |
2012年12月12日5:39 PM |
Java
素数を求めるプログラムを作って処理時間を比較したけど
一番最初に作ったもので同様に素数の総数を検出し、表示させるだけの処理時間を計測した。
実行結果は次のようになった。
run:
105097564個の素数を検出しました。
87時間32分8秒6746568970265798
構築成功 (合計時間: 5,252 分 13 秒)
とてつもなく時間がかかりました。(°°;)
以上、おまけでした。
TAGS: Java |
2012年7月24日1:32 PM |
« 古い記事
新しい記事 »
