« Project Euler - Problem 31 | トップページ | Project Euler - Problem 33 »

2009年7月14日 (火)

Project Euler - Problem 32

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


ゆっくり考えると分かることですが、「掛けられる数」、「掛ける数」、「積」の組み合わせが 9 桁になるのは「1 桁 x 4 桁 = 4 桁」と「2 桁 x 3 桁 = 4 桁」のみです。

そこでまず総当たりで調べてみます。

(自作の "math_tool.rb" に関してはこちらをご覧ください)

require 'math_tool' def check(a_min, a_max, b_min, b_max) ans = Array.new (a_min .. a_max).each do |a| (b_min .. b_max).each do |b| c = a * b break if c > 9999 # 積は 4 桁でなければならない。 d = a.to_a + b.to_a + c.to_a ans.push(c) if (d.size == 9) and d.pandigital? end end return ans end ans = check(1, 9, 1234, 9876) + check(12, 98, 123, 987) puts ans.uniq.inject(:+)

これでも Ruby 1.9 で約 0.5 秒ほどで答えは出るのですが、例えば「1 x 1234」といった明らかに数字が重なる組み合わせも調べているので、少し無駄な気がします。


そこで重複を避けるために、順列を使って掛けられる数と掛ける数を作ってみます。

require 'math_tool' # m 桁 x n 桁の積を考える。 def product(m, n) ans = Array.new seq = (1 .. 9).to_a seq.permutation(m) do |arr_a| (seq - arr_a).permutation(n) do |arr_b| c = arr_a.to_i * arr_b.to_i break if c > 9999 # 積は 4 桁でなければならない。 ans.push(c) if (arr_a + arr_b + c.to_a).pandigital? end end return ans end ans = product(1, 4) + product(2, 3) puts ans.uniq.inject(:+)

この方法だと、掛けられる数と掛ける数に重複がないので、その分計算量が減らせます。 Ruby 1.9 で約 0.15 秒ほどで答えが出ます。


順列や組み合わせが手軽に使えるので、こういった問題を解くときは Ruby で解くと楽ですね。

« Project Euler - Problem 31 | トップページ | Project Euler - Problem 33 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 31 | トップページ | Project Euler - Problem 33 »

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

最近のトラックバック

無料ブログはココログ