« Project Euler : Problem 30 | トップページ | Project Euler : Problem 32 »

2010年6月15日 (火)

Project Euler : Problem 31 ~ 両替問題

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

 

 まずは、「計算機プログラムの構造と解釈」に載っていた再帰による方法の Haskell 版です。

{- SICP によれば * n 種類の硬貨を使う, 金額aの両替の場合の数は: (a) 最初の種類の硬貨以外を使う, 金額aの両替の場合の数, 足す (b) d を最初の硬貨の額面金額[denomination]として, n種類の硬貨を使う, 金額 a - d の両替の場合の数 * 再帰の終了条件 (c) a がちょうど 0 なら, 両替の場合の数は 1 (d) a が 0 より少なければ, 両替の場合の数は 0 (e) n が 0 なら, 両替の場合の数は 0 -} countChange :: Integral a => a -> [a] -> a countChange 0 _ = 1 countChange _ [] = 0 countChange total coins | total < 0 = 0 | otherwise = a + b where a = countChange total (tail coins) b = countChange (total - head coins) coins problem031 :: Int problem031 = countChange 200 [200, 100, 50, 20, 10, 5, 2, 1] main :: IO () main = print problem031

 

 自力ではいい方法を考えつかなかったので、ネットを探してみたところ、こちらのブログにいい方法が載っていました。
 そのままでは面白くないので、場合の数を出すのではなく、パターンをすべて洗い出すコードを作り、そのパターンの数を数えてみました。

type Money = Int coins :: [Money] coins = [200, 100, 50, 20, 10, 5, 2] -- 合計金額 => [[(コインの額面, 枚数), (コインの額面, 枚数)...] ...] -- ex : exchange 5 => [[(1,5)],[(1,3),(2,1)],[(1,1),(2,2)],[(5,1)]] exchange :: Money -> [[(Money, Int)]] exchange total = map finish $ foldl func [(total, [])] coins where finish (n, xs) = [(c, i) | (c, i) <- (1, n) : xs, i /= 0] func xs c = concatMap (count c) xs count c (n, xs) = [(n - c * i, (c, i) : xs) | i <- [0 .. div n c]] problem031 :: Int problem031 = length $ exchange 200 main :: IO () main = print problem031

« Project Euler : Problem 30 | トップページ | Project Euler : Problem 32 »

Haskell」カテゴリの記事

Project Euler」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler : Problem 31 ~ 両替問題:

« Project Euler : Problem 30 | トップページ | Project Euler : Problem 32 »

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

最近のトラックバック

無料ブログはココログ