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

2009年7月12日 (日)

Project Euler - Problem 30

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


まず、調べる数の上限を探さなければいけません。

実際に計算してみると分かるのですが、元の数が 7 桁以上になると「各桁を 5 乗した和」の桁数が追いつかなくなります。

そこで、調べる数の上限は "95 x 6" となります。

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

require 'math_tool' LIMIT = 6 * (9 ** 5) def check?(n) sum = 0 n.to_a.each{|i| sum = sum + i ** 5} return n == sum end puts (2 .. LIMIT).select{|i| check?(i)}.inject(:+)

何の工夫もしていないこのコードでもそこそこ速いんですが、何か工夫をする余地はないのか、いろいろ考えてみました。


例えば……

123, 132, 213, 231 などの数は「各桁を 5 乗した和」が同じ値になります。

これらの同じ数で構成されている数の計算は重複していて無駄ですから、これを排除できないか?

結論から言うと、数の構成要素を調べたりすることでかなり時間をくってしまって実効速度はかえって遅くなってしまいました。


次に考えたのは、1234 の「各桁を 5 乗した和」は 123 の「各桁を 5 乗した和」に 4 の 5 乗を足したものですよね。

そこで、小さい順に数を調べていって、その結果を配列に溜め込んでいき、後の計算に利用することで、計算量を減らせないかと考えました。

この方法は結構うまくいきました。(ちなみに一桁の数を 5 乗したものが元の数と同じになることがないのは自明ですので初めからチェックしていません)

require 'math_tool' LIMIT = 6 * (9 ** 5) sum = (0 .. 9).map{|i| i ** 5} ans = Array.new (10 .. LIMIT).each do |n| q, r = n.divmod(10) s = sum[q] + sum[r] ans.push(n) if n == s sum[n] = s end puts ans.inject(:+)

何も工夫しないコードが約 2.5 秒かかっていたのが、このコードでは約 0.5 秒ほどで答が出ます。

そのかわり、約 35 万個の要素を持つ配列を使用するので、メモリーを消費することになりますが……。

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

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

0~9までの数字が左から右へ昇順に並んだ6ケタの数を生成する。
このリストは5005個できる。
リストの個々の要素Eの5乗和を計算しAとする。
Aを各桁のリストに戻し、そのリストをソートして辞書順に戻しBとする。
E=BならAは条件を満たす数である。
これにより5005の定数倍の計算量で計算が完了します。

コメントありがとうございます。

御指摘のアルゴリズムは、この記事と同じ問題を Haskell で解いた時に使ってみました。 (http://tsumuji.cocolog-nifty.com/tsumuji/2010/06/project-euler-2.html)

かなり高速なことが実証できています。

コメントを書く

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

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

トラックバック

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

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

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

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

最近のトラックバック

無料ブログはココログ