どうも、引き続き、競プロをやっております。
さて今回は最大公約数をパッと求めるアルゴリズムを知ったので、それを紹介します。
ユークリッドのアルゴリズムです。
結論、以下のような再帰的な関数を定義することで、最大公約数を出せます。
コード
irb(main):001* def gcd(a, b)
irb(main):002* b == 0 ? a : gcd(b, a % b)
irb(main):003> end
=> :gcd
irb(main):007> gcd(100, 12)
=> 4
irb(main):008> gcd(100, 50)
=> 50
irb(main):009> gcd(100, 37)
=> 1
こんなシンプルに出せるんだというのが、びっくりですね。
理屈で理解して、いざという時に思い出せるようにしておきたいです。
普段の業務で使うことは…なさそう。
では。
