« Project Euler - Problem 3 | トップページ | Project Euler - Problem 5 »

2009年6月 3日 (水)

Project Euler - Problem 4

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


ここにも書きましたが、二重ループを使って 3 桁の整数 × 3 桁の整数をすべて求めて、その中から最大の回文数を探すのは計算量が多くなるので大変だと思っていました。

そこで、大きい順に 6 桁または 5 桁の回文数をつくって、それが 3 桁の整数 × 3 桁の整数で表せるかをどうかを調べる方法を考えました。

require 'math_tool' # 3 桁の約数の組を探す。 def find_div(n) mid = sqrt(n).to_i mid.step(100, -1) do |i| if n.modulo(i).zero? and (n / i) < 1000 then return true end end return false end # 大きい順に回文数を作り、3 桁の約数の組を持って入れば、 # 答として表示する。 def check [true, false].each do |flag| 997.step(100, -1) do |n| p_num = n.make_palindromic(flag) return p_num if find_div(p_num) end end end puts(check)

このコードでも、Ruby 1.9 なら 0.08 秒ほどで答が出るのですが、他のブログを見て回ったところ、二重ループを使う方法でも、 break をうまく使うと、計算量を減らせることがわかりました。

require 'math_tool' v_max = 0 999.downto(100) do |i| i.downto(100) do |j| a = i * j break if a <= v_max v_max = a if a > v_max and a.palindromic? end end puts(v_max)

こちらのほうは、Ruby 1.9 で 0.05 秒ほどで答が出ます。私が最初に考えたコードよりシンプルでかつ速いですね。

« Project Euler - Problem 3 | トップページ | Project Euler - Problem 5 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 3 | トップページ | Project Euler - Problem 5 »

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

最近のトラックバック

無料ブログはココログ