🐢
[鉄則A27] Calculate GCD (ユークリッドの互除法)
自然数の最大公約数を求める問題。
問題を要約する
- A, B の最大公約数(GCM)は？
- A, B は自然数なので 0 除算は考慮しないでよい
ユークリッドの互除法とは？
- 大きい方を小さい方で割った余りにする
- 0 になったらもう一方が答え
単純な実装
A, B = gets.split.collect(&:to_i) # => [33, 88]
max = 0
(1..[A, B].min).each do |i|
if A.modulo(i).zero? && B.modulo(i).zero?
max = i
end
end
max # => 11
1, 2, 3, ... と増やしながら両方が割り切れる最大値を調べる方法。共通の約数は最大でも A, B の小さい方までなので上限を [A, B].min としている。処理がわかりやすい反面、再帰版と比べると約40倍遅い。
ユークリッドの互除法
非再帰版
A, B = gets.split.collect(&:to_i) # => [33, 88]
def gcd(a, b)
loop do
if a.zero?
break b
end
if b.zero?
break a
end
if a > b
a = a.modulo(b) # => 11
else
b = b.modulo(a) # => 22, 0
end
end
end
gcd(A, B) # => 11
再帰版
A, B = gets.split.collect(&:to_i) # => [33, 88]
def gcd(a, b)
[a, b] # => [88, 33], [33, 88], [22, 33], [11, 22], [0, 11]
a.zero? ? b : gcd(b.modulo(a), a)
end
gcd(B, A) # => 11
大きい方を小さい方で割るはずなのに、どこにも比較演算子がないのはどういうことだろう？ 仮に gcd(88, 33) で呼ぶと最初の b % a では 33 % 88 となってしまう。
これはうまくできていて、余りは 33 なので次の再帰は gcd(33, 88) で呼ばれる。つまり比較しなくても自動的に「小さい方, 大きい方」に並び換えられるのである。
組み込みメソッドを使う場合
A, B = gets.split.collect(&:to_i) # => [33, 88]
A.gcd(B) # => 11
上の再帰版に比べると約2倍速い。
Discussion