日: 2008年4月8日

Problem 31

今日は Problem 31。

 

　cf. Project Euler – Problem 31
　cf. Life Goes On – ３１問目

id:rst76さんのをちょっと改良して1pのコインがない場合にも対応できるようにしてみた。問題の解答には必要ないんだけど。

module Main (main) where

euler031 :: [Int] -> Int -> Int
euler031 (x:[]) m | m `mod` x == 0 = 1
                 | otherwise = 0
euler031 (x:xs) m = sum $ map (\n -> euler031 xs (m - x*n)) [0..(m `div` x)]

main :: IO ()
main = putStrLn $ show $ euler031 [200,100,50,20,10,5,2,1] 200
^o^ >runhaskell euler031.hs
73682

1pのコインがない場合：

*Main> euler031 [200,100,50,20,10,5,2] 200
1784