2013年 1月

ユークリッドの互除法 Euclidean Algorithm

Java

Java でユークリッドの互除法 Euclidean Algorithm をプログラミングしてみました。

再帰アルゴリズムを使ってます。

再帰アルゴリズムについてはこちらで簡単な覚え書きを残してあります。

再帰アルゴリズム その1

再帰アルゴリズム その2

ユークリッドの互除法とはいったいどんな仕組みなのか調べてみました。

ある二つの自然数の最大公約数を求めるのに非常に優れた方法らしいです。

名前に互除法とあるとおり互いに割り算を行って解を導き出す方法です。

簡単に説明すると自然数 r1 と r 2 ( r1 >= r2 ) の最大公約数を求めるとき ( 注意 : r の後の数字と n は小さい数字だと思ってください。)

r1 / r2 の余り r3 を求める。

次に r2 / r3 の余り r4 を・・・

これを rn が 0 になるまで繰り返す。

この時、 r(n-1) が最大公約数となる。

実にシンプルです。

数学的証明はここでは割愛させていただきます。

これを Java プログラムにするには再帰アルゴリズムを使えば簡単にできそうですね。

さっそく作ってみましょう。

euclidean_algorithm.Euclidean_Algorithm.java

 

非常にシンプルで解りやすいですね。

せっかくだからデバッグ実行させてプルグラムの流れを確認してみよう。

変数 x , y の値に注目です。

main() メソッドの引数二つを整数とし、大きさを比較し計算処理のため必要に応じて値を入れ替え、

再帰メソッドで答えが出るまで(再帰のループから抜ける条件になるまで)ひたすらぐるぐる回るってかんじ。

euclidean_algorithm

ユークリッドの互除法ってシンプルだけど良く考えられた素晴らしいものですね。

最後にすでにお気付きの方もいると思うのですが上記プログラムはちょっと手抜きの部分があります。

目的がユークリッドの互除法を試してみるということなのでご容赦のほどを(^_^;

ちなみに java.lang.NumberFormatException が・・・・・・です。(本当は忘れていたことは内緒です)

a_001

Hatena タグ:

再帰アルゴリズム その2

Java

再帰アルゴリズムの覚え書きの続きです。

再帰アルゴリズム その1

今回も、非効率的かつ非現実的な例題を利用して再帰アルゴリズムを理解していきましょう。

今回はフィボナッチ数列の特定項の値を求めるプログラムです。

フィボナッチ数列とは簡単に説明すると

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つの数を足し算すると、その上位の数になる数列です。

参考までに、フィボナッチ数は、ちょうど800年前に刊行された「算盤の書」(1202年)の中の有名な「兎の問題」から生まれました。

これをプログラムにするにはどうしたらいいでしょうか?

数学的手法でいくか?ループ文で和を取り値を入れ替えながら?

面倒なのでここは再帰アルゴリズムを使いましょう。(^_^;

計算処理負荷が非常に大きいことは秘密にしておきましょう。(ヲヒ

とりあえずサクッと作ってみたのでデバッグ実行させてプログラムの流れを確認してみましょう。

 

jp\yucchi.fibonacci.number.FibonacciNumber.java

 

上記のプログラムをデバッグ実行させます。

変数、n , ans の値、再帰呼び出し及び処理から戻ってくる時のプログラムの流れをしっかり確認してくださいませ。

しっかり確認できましたでしょうか?

概略図を作って流れを考察してみます。

fibonacci_number
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

さて、どちらが効率いいですか?

c_1_001

Hatena タグ:

再帰アルゴリズム その1

Java

再帰アルゴリズムについてちょっとしたメモを残しておきます。

まず再帰とは、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいうらしいです。

日本語って難しいですね。

プログラムを組む上でコーディングテクニックについては自分と同じ(自分自身)をある条件が満たされるまで呼び出し続けることのようです。

これって for 文もしくは while 文でもいけそうですね。

とりあえず非効率的かつ非現実的ではありますが 3 の階乗値を求めるプログラムを作ってみましょう。

 

jp.yucchi.recursion.example.RecursionExample.java

非常にシンプルです。

10 行目の標準出力処理の中にある fact(TARGET) メソッドで再帰メソッドを呼び出してます。

再帰メソッドが 13 行目の fact(int n) です。

14 行目から条件次第で再び呼び出されます。

全ての処理が帰ってきてから標準出力に fact(TARGET) の戻り値が出力されます。

これだったらループ文でも大差ないだろうと思った あ・な・た 正解です。(^_^;

しかし、この再帰アルゴリズムは奥が深いんです。

そのことはまた今度ってことで今回はこのシンプルなプログラムの流れをデバッガを使い確認してみます。

上記のプログラムのままでもいいのですが、ちょっと解りやすくするために下記のように変更します。

 

jp.yucchi.recursion.example.RecursionExample.java

それではプログラムの流れを変数 n , temp を確認しながらご覧ください。

どうですか?

処理が最初の呼び出し元に戻るまで追うことができましたでしょうか?

コードはすっきりとなってるけどプログラムの流れはけっこう追っていくのは大変です。

論理的に考えて組んでしまえばこのかったるい処理はコンピューターがやってくれるので非常に便利です。

今回は再帰アルゴリズムの基本中の基本のメモでした。

Hatena タグ:

A HAPPY NEW YEAR 2013

General

あけましておめでとうございます。

どうか本年も暖かい、もしくは生暖かい目で見守ってください。(^_^)

2013年はクラウディアさんと、ひときわ光り輝いている巨人の星をめざします。(ヲヒ

50_001

これだけだとさみしいので翻訳ソフトで英語にしてみた。

I congratulate you opening.

Please watch by a warm or lukewarm eye if you please this year also. (^_^)

I will aim at the star of the giant who is shining particularly with Claudia in 2013. (ヲヒ)


新しい記事 »