【独習】ユークリッド互除法とは

ユークリッド互除法とは?

ユークリッド互除法を理解しているだろうか。
聞いたことがある程度の人もいれば、それがアルゴリズムであることまでは分かる人も多いだろう。
今回は、ユークリッド互除法を書き溜め、
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

広告

ユークリッド互除法

ユークリッド互除法とは、
2つの自然数の最大公約数を求める手法の一つである。

ユークリッド互除法では、
自然数のある性質を利用して計算を行う。

その性質とは下記である。

2つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると
a と b との最大公約数は b と r との最大公約数に等しい。
(Wikipediaより)

割り算した余りを、再利用して計算を繰り返していくイメージだ。

ユークリッド互除法の手続き的記述

ユークリッド互除法を手続き的に記述すると次のようになる。

  1. 入力を a, b (a ≧ b) とする
  2. b = 0 なら、 a を出力し、処理を終了する
  3. a を b で割る
  4. (3)の結果の余りを、 a とする
  5. 元の a を、 b とする
  6. (2)にもどる

出力結果が最大公約数となる。

仕組みを視覚的に理解するには、次を参照されたい。

Pythonで記述する

ユークリッド互除法をPythonで記述すると下記のようになる。
(参考情報である。)

ユークリッド互除法を説明してください。

さて、先程の説明を読んだ人は、ユークリッド互除法を説明できますね。
ユークリッド互除法とは何か?そして、どのような性質を利用したアルゴリズムであるか?

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。


じゃあね〜〜〜。