« Project Euler - Problem 52 : 0.4s (Ruby 1.9) | トップページ | Project Euler - Problem 54 »

2009年8月13日 (木)

Project Euler - Problem 53 : 0.1s (Ruby 1.9)

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


自作の "math_tool.rb" には組み合わせの場合の数を計算する "Integer#combination_size" があるので、それを使用しても良かったのですが、この問題では階乗の計算が繰り返し行われるので、階乗の計算をメモ化してみました。

class Integer @@fact = {0 => 1} def fact ans = @@fact[self] if ans return ans else ans = self * (self - 1).fact @@fact[self] = ans return ans end end def comb(r) return self.fact / (r.fact * (self - r).fact) end end ans = 0 (1 .. 100).each do |n| (1 .. n).each do |r| ans = ans + 1 if n.comb(r) > 100_0000 end end puts ans

自作の Integer#combination_size は下降階乗冪を使用しているため、問題に書いてある「組み合わせの計算方法」よりずっと速いのですが、階乗の計算をメモ化するとさらに速くなりました。

« Project Euler - Problem 52 : 0.4s (Ruby 1.9) | トップページ | Project Euler - Problem 54 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler - Problem 53 : 0.1s (Ruby 1.9):

« Project Euler - Problem 52 : 0.4s (Ruby 1.9) | トップページ | Project Euler - Problem 54 »

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            
フォト

最近のトラックバック

無料ブログはココログ