感謝のプログラミング 10000時間

たどり着いた結果(さき)は、感謝でした。

【Python入門】ユークリッドの互除法とはどんなアルゴリズムか?


スポンサーリンク

概要

  • 紀元前300年頃にギリシァで考案された
  • ユークリッドの互除法は2つの整数 𝑎 と 𝑏 の最大公約数を求めるアルゴリズムである
  • 人類最古のアルゴリズムだが、今現在でも最先端で使われている
  • 最大公約数を求める上で最も効率の良いアルゴリズムである

どんなアルゴリズムか

  1. 𝑥 に 𝑎 を代入する
  2. 変数 𝑦 に 𝑏 を代入する./li>
  3. 𝑦 ≠ 0 である間は 4 ~ 7を繰り返す
  4. 𝑥 を 𝑦 で割ったときの商を 𝑞 とする
  5. 𝑥 を 𝑦 で割ったときの余りを 𝑟 とする
  6. 𝑥 に 𝑦 の値を代入する
  7. 𝑦 に 𝑟 の値を代入する
  8. 𝑛 に 𝑥 の値を代入する

Pythonで実装してみる

"2つの整数 a = 240, b = 144 の最大公約数をユークリッドの互除法で求める"

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from time import sleep


a = 240
b = 144

print("2つの整数 a = " + str(a) + ", b = " + str(b) + "の最大公約数をユークリッドの互除法で求める")

x = a
y = b

while y != 0:
    q = (x / y)
    r = (x % y)
    x = y
    y = r
    print("q=" + str(q) + ",r=" + str(r) + ",x=" + str(x) + ",y=" + str(y))
    sleep(1)
n = x

print ("最大公約数:" + str(n) )

結果:

2つの整数 a = 240, b = 144の最大公約数をユークリッドの互除法で求める
q=1,r=96,x=144,y=96
q=1,r=48,x=96,y=48
q=2,r=0,x=48,y=0
最大公約数:48