Project Eulerを始めてみました
Project Euler というのはこんなサイトです→ http://projecteuler.net/
素晴らしいことに日本語のサイトもあります→ http://odz.sakura.ne.jp/projecteuler/
プログラムで解くことの出来る数学の問題がたくさん登録されており、それをみんな好きな言語で解いて遊ぶというサイトです。
昨日、今日でちょこちょこやって、今正答数が 23/290 です。
しかし問題はどんどん難しくなっていき、数学者じゃないと解けない問題とか出てくるような気がしています。いつまで続けられるか…という感じですね。
素数の話が多いので、エラトステネスの篩をちょいと実装しました。Rubyだとほんと簡単にかけてしまうので、すごく楽です。ただ、パフォーマンスは悪いと思うので、気が向いたら C++ でも実装して速度比較してみるのも面白いかなと思っています。
def primes(maxnum) return [2] if maxnum == 2 prime = (3..maxnum).select{|t| t%2 != 0} (3..(Math.sqrt(maxnum).to_i)).each do |f| prime.delete_if {|t| t!=f && t%f == 0} end [2] + prime end
ちなみに、愚直に実装するとループ数がとんでもないことになるので工夫するというのが基本的な方針なのですが、実際、どのくらいのループ数なら問題を解けるか？というのをちょっと試してみました。
測定スペックは以下です。
(1..10**8).each {|t|t} # => 16s (1..10**8).inject {|s,t|s+t} # => 72s
よく使うのは inject なので、injectの速度が問題なのですが、10**9 で12分、10**10で2時間、10**11で20時間。
…このくらいが限界のようですね。C言語を使えばもう少しがんばれるのかもしれませんが。
ちなみに、一番最近の問題は以下です。
問題はすごく短いのですが、いまいちどうすればいいか分かりません・・・。
http://projecteuler.net/index.php?section=problems&id=290
簡単な問題を１つずつ解いていくと、そのうちこういうのも解けるようになるのかなぁと今は思っています。
まるでプログラミングのバッティングセンターみたいですね。
っと思ったら、こんなことをつぶやいている人がいましたorz
http://twitter.com/rng_58/status/13136901518
