最近いろいろなアルゴリズムを短く短くすることにはまっています。今日はその一環でユークリッドの互除法を扱いました。
ユークリッドの互除法とは何か
ユークリッドの互除法は最大公約数を探す定番アルゴリズムです。シンプルながら非常に強力で、しかも世界最古のアルゴリズムというすごいやつです。
具体的な手順は次のようになります。*1
R1≧R2
を満たすふたつの自然数R1
とR2
について、R1÷R2
のあまりR3
を求める。R2
とR3
のあまりR4
を求める。- step.1とstep.2を
Rn = 0
になるまで繰り返す。 Rn-1
がR1
とR2
の最大公約数となる。
ちょっとわかりづらいので、具体例を見てみましょう。ユークリッドの互除法を利用して69と18の最大公約数を求めてみましょう。
- 69 ÷ 18 = 3 ... 15
- 18 ÷ 15 = 1 ... 3
- 15 ÷ 3 = 5 ... 0
よって69と18の最大公約数は3と求まるわけです。
具体的な実装
具体的な手順が理解できたところで、実際にコードのレベルにアルゴリズムを落とし込んでいきます。
ではa = 69, b = 18
として、先ほどの具体例を表に表してみます。
a | b | 商 | あまり |
---|---|---|---|
69 | 18 | 3 | 15 |
18 | 15 | 1 | 3 |
15 | 3 | 5 | 0 |
3 | 0 | ? | ? |
上の表からいえるのは
a
は1段階前のb
の値である。b
は1段階前のあまり
の値である。b
が0になったら処理終了。- 逆に言えば
b
が0より大きい間は処理を続けるということである。
- 逆に言えば
- 求める最大公約数は
a
にあらわれる。
以上をプログラミングに当てはめていくと、次のようになるはずです。
def gcd(a,b) while b > 0 a,b = b,a%b end return a end
def gcd(a,b) a,b = b,a%b while b > 0 a end
随分とすっきりしましたね。具体的には次のようなことを行っています。
- 後置
while
を利用する。 - メソッドの戻り値に
return
を必ずしも用いない
このふたつはrubyらしさを演出する(?)要素なので積極的に使っていきたいところです。
おまけ
その1
なおa
とb
の値を逆、すなわちa = 18, b = 69
としても、最大公約数は求めることができます。
a | b | 商 | あまり |
---|---|---|---|
18 | 69 | 0 | 18 |
69 | 18 | 3 | 15 |
18 | 15 | 1 | 3 |
15 | 3 | 5 | 0 |
3 | 0 | ? | ? |
仮にa ≦ b
だとしても1回目の処理で必然的にa
とb
がスワップされるので、a ≦ b
と同じ結果が得られるというわけです。
その2
ちなみに同じことをC言語で実装すると以下のようになります――というかなるはずです(実はあまりCは詳しくない)。もっと簡潔にかけるかも……?
int gcd(int num1, int num2){ int temp1, temp2; while (num2 > 0){ temp1 = num2; temp2 = num1 % num2; num1 = temp1; num2 = temp2; } return num1; }
その3
最大公約数がわかると、最小公倍数は簡単に求められます。説明するまでもないレベルなので、rubyのコードだけ書いておきますね。
def lcm(a,b) a * b / gcd(a,b) end