Rubyでアルゴリズムを実装する:Day 1 -ユークリッドの互除法-

アルゴリズムについて学ぶために自分の持ち合わせた知識を用いてコーディングします。
続くかわからない１日目

ユークリッドの互除法とは

最も有名といっても過言ではないアルゴリズムの１つ。もはや説明不要だろう。
２つの自然数aとbについて最大公約数を求めるもの。
方法はaとbの剰余を求める。
次にｂと剰余の剰余を求める。
そして剰余の剰余と、剰余の剰余の剰余を求める。
剰余が０になるまで繰り返した時の除数がaとbの公約数となる。

仕組みがわかったら、早速コーディング

Euclid.rb

def euclid(a, b)
  while b != 0
    mod = a % b
    a = b
    b = mod
  end
  a
end

print "aの値:"
a = gets.to_i
print "bの値:"
b = gets.to_i

puts "aとbの最小公約数は#{euclid(a,b)}です"                                         

aとbを入力しメソッドの引数とする。

modにaとbの余りを代入
aにbを代入
bにmodを代入

これをbが0より大きい時だけ繰り返す

おそらく問題ないはず

最後に

簡単なコードだから間違いはないはず
有識者のみなさんに求めるものは
・コードの簡略化
・処理速度の短縮化
思い付きで行ってるので実行可能かは知りませんが、よろしくお願いします

明日はバブルソートの実装をします。