ユークリッドの互助法って何でしょか？

質問

学校の問題で、その方法を再帰呼び出しを持って実践するプログラムを作りなさい、と言うのが出て、そのまずユークリッドが分からないで八方塞がりｉｎｇです。　　　　余り知識が無いんで簡潔に説明して戴けたら、これ、幸いであります。

回答No.2

ymmasayan · ベストアンサー

簡潔に説明しましょう。
ユークリッド・・大昔の数学の大家。ユークリッド幾何学、非ユークリッド幾何学の名で有名。
ユークリッドの互除法・・２つの数の最大公約数を求めるのに、最も早い、すばらしい方法。互除法というのはお互いに除算（割り算）をすると言う意味。互助法ではありません。
［ユークリッドの互除法］
（１）２つの数を、Ａ、Ｂとします。仮にＡが大きいとします。
（２）ＡをＢで割って余りをＲとします。
（３）Ｒが０なら、Ｂが答え（最大公約数）で終わり。
（４）ＢとＲのうち大きいほうをＡに入れ、小さいほうをＢに入れます。
（５）前の（２）へ飛びます。

例をあげましょう。Ａ＝１８、Ｂ＝１２とします。
Ｒ＝ｍｏｄ（１８，１２）＝６
Ａ＝１２、Ｂ＝６
Ｒ＝ｍｏｄ（１２，６）＝０　→　終わり　　Ｂ＝６が答え（最大公約数）
どうです。簡単でしょう。

割り算の代わりに引き算を繰り返し使う方法もあります（ＣＡＳＬなどでは）

この問題で、再帰処理を使うメリットは感じませんが、練習として使う事は可能です。再帰処理は質問に入っていないので、省略します。過去にも再帰処理の質問は出ています。頑張ってください。

お礼

ご回答どうも有り難う御座いました！　ナカナカ分かり易かったです。　感謝です。

回答No.1

TAGOSAKU7

どもども田吾作７です。

再帰法で再起不能
↑おっさんギャグ

まぁそれはそれとして、
再帰法はわかりますか？

簡単な例題を出します。
５０平方の画用紙を、ある裁断機に入れると半分の大きさになります。
１平方メートル以下の大きさになるには何回通るでしょう？

VBではDO～LOOPを使う方法がありますが、再帰法で行うことも出来ます。
Option Explicit

'カット回数を表すカウンタ
Private CutCount　　As Long

Public Sub Main()
　　'ペーパーのサイズ
　　Dim PaperSize　 As Double

　　'基本の大きさ
　　PaperSize = 50

　　'カットした回数の初期値
　　CutCount = 0

　　'裁断機にかける
　　Call CutPaper(PaperSize)

　　MsgBox CutCount
End Sub

'裁断機
Private Sub CutPaper(inParper As Double)

　　'用紙サイズが１m2以下なら終了
　　If inParper < 1 Then Exit Sub

　　'用紙サイズが１m2以上であれば裁断機にかけるて自分自身を呼び出す
　　'（カウンタを増やし、自分自身を呼び出す）
　　inParper = inParper / 2
　　CutCount = CutCount + 1
　　Call CutPaper(inParper)
End Sub

このように条件を満たすまで、自分自身を呼び出すのが再帰法です。
例題があまりよくないので、これはDO～LOOPの方が好ましいかも知れません。

実際使用するとしたら、「あるフォルダ以下を全て書き込み禁止にしなさい」といった処理を行う時に、再帰法がベストだと思います。フォルダの中のファイルを書込み禁止にして、その中にフォルダが存在していたら、更にそのフォルダ内を書込み禁止にして・・・・とフォルダが存在する限り、その関数を走り続けるようになります。(サンプルはちょっと面倒なので勘弁して)

この一つ目の例題と二つ目の大きな差は、同じレベルか、それとも下のレベルかという点にあります。

ペーパーはあくまで裁断されても、単に小さいペーパーであって、最初の５０平方メートルのペーパーを指します。
しかしフォルダ内の書込み禁止は、フォルダの中のサブフォルダ、またはさらにその中のサブフォルダ・・・と階層があるわけです。

前置きが長くなりましたが、ユーグリッド法はわかりませんが、ユーグリッドの互助法はこの概念と共通してます。
「ある条件が満たされるまで、一つのパターンを繰り返して行く」
まさに再帰法です。

下記URLにユーグリッドの互助法による、最大公約数の求め方がありますので、そちらをのぞいてみては？
そちらにも例題があります。
[a][b][r][r1]とか書いてありますが、例題の具体例を紙に書いてやってみると、同じこと繰り返しをしているだけで、結構単純であることに気付くと思いますよ。

参考URL：

http://math1.edu.mie-u.ac.jp/~motokioh/ucurid.htm

お礼

ご回答有り難う御座います！　少し分かったような、分からないような・・・　　勉強します！！