« Project Euler - Problem 1 再び | トップページ | Project Euler - Problem 44 »

2009年4月18日 (土)

Project Euler - Problem 4 再び

以前、「Problem 4」に関する記事を書いた際に、「二重ループで探すのは時間がかかる」と書いたのですが、それは私の思い違いであることが分かりました。

正確に書くと、「工夫次第でかなり速くなる」のが分かりました。

前回投稿した後、いろいろなブログを見ていて、次のようなコード見つけました(記憶を元に私が再構成したので、元のコードとは違う部分があると思いますが、アルゴリズムは同じはずです)。

class Integer def palindrome? s = self.to_s return s == s.reverse end end max = 0 999.downto(100) do |i| 999.downto(100) do |j| num = i * j break if (num <= max) max = num if (num.palindrome? and (num > max)) end end puts max

このコードでポイントとなるのは、大きい数から探していくことと、12 行目の "break" です。

その時点で分かっている最大値より小さい値の計算を飛ばすことによって、全体の計算量を減らしています。

調べてみたら、"num = i * j" の計算は 9200 回しか行われていませんでした。

アルゴリズムも、コードも自分が考えていたものよりもシンプルでわかりやすいと思います。

「ちょっとした工夫」を考えつけなかったのが非常に悔しいです……。

« Project Euler - Problem 1 再び | トップページ | Project Euler - Problem 44 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler - Problem 1 再び | トップページ | Project Euler - Problem 44 »

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

最近のトラックバック

無料ブログはココログ