« Project Euler : Problem 35 ~ 循環素数 | トップページ | Project Euler : Problem 36 ~ 十進法と二進法 »

2010年6月23日 (水)

Project Euler : Problem 34

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

 

 この問題は、「Problem 30」の応用編ですね。ということで同じ方法で解きました。
 まずは、「配列によるメモ化」です。

import Data.Array -- 階乗 factorial :: Integral a => a -> a factorial m = product [2 .. m] -- 整数をリストに変換 dexToList :: Integral a => a -> [a] dexToList n = iter n [] where iter n prd | n < 10 = n : prd | otherwise = iter (div n 10) (rem n 10 : prd) factSum :: Integer -> Integer factSum n = sum [factArray ! x | x <- dexToList n] where factArray = listArray (0, 9) [factorial x | x <- [0 .. 9]] problem034 :: Integer problem034 = sum [x | x <- [3 .. factorial 9 * 7], factSum x == x] main :: IO () main = print problem034

 次は、「重複組み合わせ」を使う方法です。

import Data.List import Data.Array -- 階乗 factorial :: Integral a => a -> a factorial m = product [2 .. m] -- 整数をリストに変換 dexToList :: Integral a => a -> [a] dexToList n = iter n [] where iter n prd | n < 10 = n : prd | otherwise = iter (div n 10) (rem n 10 : prd) -- 重複組み合わせ (repeated combination) -- ex : repComb [0..2] 2 => [[0,0],[0,1],[0,2],[1,1],[1,2],[2,2]] repComb :: [a] -> Int -> [[a]] repComb _ 0 = [[]] 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] problem034 :: Int problem034 = sum $ concatMap ns [2 .. 7] where ns m = [n | xs <- repComb [0 .. 9] m, let n = calc xs, check xs n] fn = listArray (0, 9) [factorial x | x <- [0 .. 9]] calc ys = sum $ map (fn !) ys check ys n = (sort $ dexToList n) == ys main :: IO () main = print problem034

« Project Euler : Problem 35 ~ 循環素数 | トップページ | Project Euler : Problem 36 ~ 十進法と二進法 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

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

« Project Euler : Problem 35 ~ 循環素数 | トップページ | Project Euler : Problem 36 ~ 十進法と二進法 »

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

最近のトラックバック

無料ブログはココログ