« Project Euler - Problem 35 : 1.0s (Ruby 1.9) | トップページ | Project Euler - Problem 37 : 0.09s (Ruby 1.9) »

2009年7月21日 (火)

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

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


問題を素直にコーディングすると次のようになると思います。

なお、「先頭に0を含めて回文にすることは許されない」という文面から、「2 進法で表した際に先頭と最後の数字は 1 でなければならない」ということが分かります。従って調べる対象となる数は奇数に限定されます。

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

require 'math_tool' ans = Array.new (1 .. 99_9999).step(2) do |i| ans.push(i) if (i.palindromic? and i.to_a(2).palindromic?) end puts ans.inject(:+)

この考え方でも、そこそこの時間で解答が得られます。(Ruby 1.9 で約 0.6 秒でした)

ただし、ちょっと無駄な計算が多い気がします。


例えば、1 〜 100万までの数の中で、10 進法で回文数になる数はたった 1998 個しかありません。

このことは irb で、"math_tool.rb" 読み込んだ上で

(1 .. 100_0000).select{|i| i.palindromic?}.size

とすると分かります。


そこで、まず 10 進法の回文数を作って、その数が 2 進法でも回文数になるかを調べてみましょう。(ここでも偶数は予め除外しました)

require 'math_tool' ans = Array.new (1 .. 999).each do |n| [:odd, :even].each do |flag| a = n.make_palindromic(flag) break if a.even? ans.push(a) if a.to_a(2).palindromic? end end puts ans.inject(:+)

この方法だと、Ruby 1.9 で約 0.1 秒で答が出ます。

いきなり問題を解こうとするのではなく、じっくり腰を据えてアルゴリズムを吟味してみるのも面白いと思いませんか?

« Project Euler - Problem 35 : 1.0s (Ruby 1.9) | トップページ | Project Euler - Problem 37 : 0.09s (Ruby 1.9) »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 35 : 1.0s (Ruby 1.9) | トップページ | Project Euler - Problem 37 : 0.09s (Ruby 1.9) »

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

最近のトラックバック

無料ブログはココログ