« Project Euler - Problem 4 | トップページ | Project Euler - Problem 6 »

2009年6月 3日 (水)

Project Euler - Problem 5

問題はこちらをご覧ください。


要するに「1 〜 20 のすべての最小公倍数」を求める問題ですよね。

ここにも書きましたが、2 数の最大公約数が分かれば最小公倍数も分かるので、「ユークリッドの互除法」を使った最大公約数を求めるメソッドを自作できればこの問題は解けます。

でも、Ruby には最大公約数を求める Integer#gcd や、最小公倍数を求める Integer#lcm が既にあるので、今回はこれを使っていきます。

a = 1 (2 .. 20).each{|i| a = a.lcm(i)} puts(a)

inject を使うこともできます。

puts((1 .. 20).inject{|n, i| n = n.lcm(i)})

あまりにも簡単に答えが出てしまうので、面白くない?

じゃあ、自分でメソッドを作ってみましょうか。

class Integer # # == 最大公約数を求める # # * ユークリッドの互除法を使用。 # def my_gcd(num) m = [self, num].max n = [self, num].min r = m.modulo(n) until r.zero? m, n = n, r r = m.modulo(n) end return n end # # == 最小公倍数を求める # def my_lcm(num) return self * num / self.my_gcd(num) end end puts((1 .. 20).inject{|n, i| n = n.my_lcm(i)})

こんな感じでどうでしょう?

« Project Euler - Problem 4 | トップページ | Project Euler - Problem 6 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/45222184

この記事へのトラックバック一覧です: Project Euler - Problem 5:

« Project Euler - Problem 4 | トップページ | Project Euler - Problem 6 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ