最大公約数をrubyに翻訳した。

アルゴリズム事典「最大公約数」をrubyで翻訳してみた。

書籍の中では「ユークリッドの互除法」を使って最大公約数を計算している。
これは、「与えられた2数の割り算を行って余りを求め、今度はその余りを使って更に割り算し次の余りを求める」という計算を次々に行っていく手法。
wikipediaではアニメーション付きで説明してくれている。

ユークリッドの互除法 - Wikipedia

再帰的に関数を呼び出して計算する方法も紹介されているが、今回はループによる処理を実行しているものを翻訳した。

def gcd(x, y)
    while y != 0 do
        x, y = y, x % y
    end
    x
end

def ngcd(a)
    d = a.shift
    a.each do |ai|
        d = gcd ai, d
        break if d == 1
    end
    d
end

loop do
    a = []
    puts "整数を入力してください: "
    100.times do
        s = gets.to_i
        break if s == 0 || s < 0
        a << s
    end
    break if a.empty?
    puts "最大公約数 = #{ngcd a}"
end

---

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)

posted with amazlet at 18.06.14

奥村 晴彦
技術評論社
売り上げランキング: 201,446

Amazon.co.jpで詳細を見る