« Project Euler - Problem 29 | トップページ | Project Euler : Problem 31 ~ 両替問題 »

2010年6月13日 (日)

Project Euler : Problem 30

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

 

 この問題は、以前も書きましたが 7 桁未満の整数の範囲を調べれば答えが出せます。
 まずは brute force 版。

-- 整数をリストに変換 (radix : 基数) integralToList :: Integral a => a -> a -> [a] integralToList radix n = iter n [] where iter n prd | n < radix = n : prd | otherwise = iter (div n radix) (rem n radix : prd) problem030 :: Integer problem030 = sum $ filter check [2 .. limit] where limit = 6 * 9 ^ 5 check n = sum [x ^ 5 | x <- integralToList 10 n] == n main :: IO () main = print problem030
 さすがにちょっと時間がかかります。(約 0.9 秒ほど)

 

 毎回 5 乗を計算するのは無駄な気がしたので、配列によるメモ化も試してみました。

import Data.Array -- 整数をリストに変換 (radix : 基数) integralToList :: Integral a => a -> a -> [a] integralToList radix n = iter n [] where iter n prd | n < radix = n : prd | otherwise = iter (div n radix) (rem n radix : prd) problem030 :: Integer problem030 = sum $ filter check [2 .. limit] where limit = 6 * 9 ^ 5 n5 = listArray (0, 9) [x ^ 5 | x <- [0 .. 9]] check n = n == sum [n5 ! x | x <- integralToList 10 n] main :: IO () main = print problem030
 ちょっとだけ速くなって、約 0.45 秒ほどで答えが出ました。

 

 自分で考えついた方法はこれくらいだったのですが、もっといい方法は無いものかとインターネットを調べていたら、こちらのブログにおもしろい解法が載っていました。「重複組み合わせを使って使う数字を選んで、その5乗和の数字をソートしたら元に戻れば OK」という方法です。
 さっそく自分でもこの方法を使ったコードを書いてみました。

import Data.Array import Data.List -- 重複組み合わせ repComb :: [a] -> Int -> [[a]] repComb xs n = loop (func ([], xs)) n where loop xss 1 = [xs | (xs, _) <- xss] loop xss n = loop (concatMap func xss) (n - 1) func (xs, ys) = [(xs ++ [z], zs) | zs@(z : _) <- tails ys] -- 整数をリストに変換 (radix : 基数) integralToList :: Integral a => a -> a -> [a] integralToList radix n = iter n [] where iter n prd | n < radix = n : prd | otherwise = iter (div n radix) (rem n radix : prd) problem030 :: Int problem030 = sum $ concatMap ns [2 .. 6] where ns m = [n | xs <- repComb [0 .. 9] m, let n = calc xs, check xs n] n5 = listArray (0, 9) [x ^ 5 | x <- [0 .. 9]] calc ys = sum $ map (n5 !) ys check ys n = (sort $ integralToList 10 n) == ys main :: IO () main = print problem030
 このコードは調べる数が少ないので、約 0.04 秒で答えが出ました。前のコードの約 10 倍のスピードです。(ちなみにオリジナルのコードの約 1.5 倍)
 やっぱりアルゴリズムの選択って重要ですよね。

« Project Euler - Problem 29 | トップページ | Project Euler : Problem 31 ~ 両替問題 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: 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            
フォト

最近のトラックバック

無料ブログはココログ