アルゴリズムについての問題

質問

(1)AとBは正の整数値とする。
(2)A=L,B=Sとして代入する。
(3)L:Sで比較したときにL>Sの場合はL-S→L(矢印は代入を表す)としてL<Sの場合はS-L→Sとする。
(4)どちらかの計算をした後にLとSを比較し、＝(イコール)の場合はLとして出力する。
(5)＝でない場合は(3)に戻る。LはA,Bに関してどのような関係であるか簡潔に答えよ。
という問題がありました。私はLはAとBの最大公約数と答えました。
あっていますでしょうか？またこのアルゴリズムの名前のようなものがあれば教えてください。

回答No.1

kiwa67 · ベストアンサー

あっています。

L と S の最大公約数は、L と S を割り切るので、
L-S または、S-L も割り切ります。質問文にある、
L, S を L-S, S-L に置き換えるアルゴリズムで最大公約数
を求めることができます。

補足

丁寧な説明ありがとうございました。

回答No.3

Tacosan

質問番号 5360312 で回答があって, しかもそれに対して「良回答」と出しているにもかかわらずまた同じ質問をしているのはなぜ? あっちの回答者に対する仁義はないの?
ちなみにこっちが本来の「ユークリッドの互除法」らしいよ.

参考URL：

http://oshiete1.goo.ne.jp/qa5360312.html

お礼

お礼ではありませんが、その時の質問と今回の質問は違うのでよく見てください。自分が善だと思っていてもまわりは偽善と見ていることもありますよ？
偽善は不愉快です。

回答No.2

hashioogi

「ユークリッド互除法」というキーワードでwebを検索されたらいかがでしょうか ?

お礼

ありがとうございました。参考になりました。