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

質問

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

回答No.2

ymmasayan · ベストアンサー

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

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

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

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

お礼

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