ユークリッドの互除法について
概要
- 最大公約数を求めるアルゴリズム
- greatest common divisorの頭文字をとってgcdと表記されることがある
コード
1 2 3 4 5 |
def gcd(x,y): if y==0: #[1]yが0の時はxを返す return x else: #[2]y=0以外の時 return gcd(y,x%y) |
[1]yが0の時
yが0の時、xを返します。すでに最大公約数が求まっている状態です。
[2]yが0以外の時
xの値をyとし、yの値をxをyで割ったときの余りとして再度この関数を呼び出します。
xでyが割り切れる、つまり[1]のようにyが0になるまで再帰的に処理を繰り返します。
また、Pythonではmathモジュールを使うことで簡単に最大公約数を求めることもできます。
1 2 3 4 5 6 7 |
import math a=6 b=3 gcd = math.gcd(a,b) print(gcd) #3 |
参考
こちらの書籍を用いて学習しています。
問題が書籍の中にあります。図を使って各頂点と各辺のコストが示されているので、書籍を手元に準備すると理解しやすくなると思います。
また、こちらのサイトも学習に利用しています。
Pythonで最大公約数と最小公倍数を算出・取得 | note.nkmk.me
Atcoderに最大公約数を求める問題があります。
022 – Cubic Cake(★2) (atcoder.jp)
こちらの記事で上記の問題を解いてみました。
【Atcoder】競プロ典型問題90問に挑戦 | Best Practice (find-best-practice.com)
コメント