<アルゴリズムの基本⑩> 繰り返し処理(8) ユークリッドの互除法

アルゴリズム その他

今回は、ユークリッドの互除法を使った2つの数値の最大公約数を求めるアルゴリズムについてまとめます。

ユークリッドの互除法について

まずはユークリッドの互除法について、おさらいです。

ユークリッドの互除法(ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。ウィキペディア:ユークリッドの互除法より

擬似コード例

擬似コード例を以下に示します。

Procedure GCD(A, B)
    R ← A÷Bの剰余
    while R is not 0 do # 余りが0になるまで繰り返す
          A ← B
          B ← R
          R ← A÷Bの剰余
    end-while
    return B

Pythonコード例

Pythonのコード例を以下に示します。繰り返し処理を使った場合と、再帰処理を使った場合それぞれ記載しました。(コードはこちらにアップロードしてあります)

# 繰り返し処理版
>>> def iterative_gcd(a, b):
...     r = a % b
...     while(r != 0):
...         a = b
...         b = r
...         r = a % b
...     return b

# 再帰処理版
>>> def recursive_gcd(a, b):
...     r = a % b
...     if r == 0:
...         return b
...     else:
...         return recursive_gcd(b, a % b)

実行結果


# 繰り返し処理版
>>> iterative_gcd(24, 36)
12

# 再帰処理版
>>> recursive_gcd(24, 36)
12

まとめ

今回はユークリッド互除法を用いた最大公約数の求め方についてのアルゴリズムについてまとめました。繰り返し処理を使った基本的なアルゴリズムについては一旦ここまでにして、次回からは並べ替え(ソート)アルゴリズムについてまとめる予定です。

Learn more...

書籍でもう少し詳しく学びたい場合はこちらもどうぞ。筆者もかなり参考にさせてもらっています!

シェアする
ひびきをフォローする
Hbk project

コメント

  1. 最近Pythonで遊び始めたおじさん より:

    最近Pythonで遊び始めたのですが、
    なかなか面白いプログラミング言語ですよね。

    ループの継続条件をr != 0からb != 0に変え、
    ループ内での剰余計算をループの先頭に移動させ、
    さらにリターン値をbからaに変えれば、
    ループ前に剰余計算を行う必要が無くなります。

    def iterative_gcd(a, b):
    while(b != 0):
    r = a % b
    a = b
    b = r
    return a

    さらに、Python特有の多重代入を使えば、
    剰余計算用の変数rも不要となり、ここまでコンパクトに。

    def iterative_gcd(a, b):
    while(b != 0):
    a, b = b, a % b
    return a

    再帰・三項演算子を使わずに
    ここまですっきり書けるのはPythonならではですよね。

    • Auther より:

      ご教示ありがとうございます!
      なるほど、確かに効率的ですっきりした書き方ですね。
      参考にさせていただきます!
      #記事中に例示したコードが(お恥ずかしいことに)そもそもb=0の場合を考慮できていませんでした。。