01

06

[Haskell] nセントを25,10,5,1セントで払うのに何通りあるか。

2013.01.06(22:47)

世界で闘うプログラミング力を鍛える150問
http://www.amazon.co.jp/dp/4839942390/
の問題9.8 をHaskellで解いてみた。

問題 9.8
25セント貨、10セント貨、5セント貨、1セント貨が無数にあるとして、
これらを使ってnセントを表現するすべての場合の数を計算するコードを書いてください。

nと硬貨のリスト[25,10,5,1]から何通りあるかを求める関数を作ることにする。
nと[1]だと、全部1セント貨で払うことになるので、1通りである。
5と[5,1]だと、5セント貨1枚と、1セント貨5枚、の2通り。
nを硬貨のリストの大きいほうから順に払ってゆき、残額を残った硬貨で払うように考える。

{-# OPTIONS -Wall -Werror #-}

-- | mセントをnセント硬貨で払うのに何通りあるかを残額のリストで求める。
-- | pat 100 25 = [100,75,50,25,0]
-- | pat 110 25 = [110,85,60,35,10]
-- | 100セントを25セント硬貨が0枚~4枚まで5種類で払うことができる。
-- | 110セントを25セント硬貨が0枚~4枚まで5種類で払うことができる。
patList :: [Int]->Int->Int->[Int]
patList xs m n = if m<0 then reverse xs
                    else patList (m:xs) (m-n) n
pat :: Int->Int->[Int]
pat m n = patList [] m n

-- | 上のpatは私が考えた冗長すぎる関数。
-- | 以下の3つはツイッターで教えてもらった関数で、ずっとシンプル。

-- | mセントをnセント硬貨で払うのに何通りあるかを残額のリストで求める。
-- | pat 100 25 = [100,75,50,25,0]
-- | pat 110 25 = [110,85,60,35,10] ★
-- | 100セントを25セント硬貨が0枚~4枚まで5種類で払うことができる。
-- | 110セントを25セント硬貨が0枚~4枚まで5種類で払うことができる。
pat1,pat2,pat3 :: Int->Int->[Int]
pat1 m n = takeWhile (>=0) $ iterate (subtract n) m
pat2 m n = takeWhile (>=0) [m-n*i|i<-[0..]]
pat3 m n = [m,m-n..0] -- この場合の0は0以上を意味するので、★のような場合もOK

{--
makeChange コイン種別  残額 
makeChange [25,10,5,1] 100 = makeChange [10,5,1] 100 -- 25セントが0枚
                           + makeChange [10,5,1] 75 -- 25セントが1枚
                           + makeChange [10,5,1] 50 -- 25セントが2枚
                           + makeChange [10,5,1] 25 -- 25セントが3枚
                           + makeChange [10,5,1] 0 -- 25セントが4枚
makeChange [10,5,1] 25 = makeChange [5,1] 25 -- 10セントが0枚
                       + makeChange [5,1] 15 -- 10セントが1枚
                       + makeChange [5,1] 5  -- 10セントが2枚
makeChange [5,1] 5 = makeChange [1] 5 -- 5セントが0枚で、残りは全部1セント
                   + makeChange [1] 0 -- 5セントが1枚で、残りは全部1セント

list=[10,20,30] から 
succ 10 + succ 20 + succ 30 を求めるには
foldl (+) 0 $ map succ list

pat [] 5 5 = [0,5] をもとめて分ける
makeChange [5,1] 5 = makeChange [1] 5 + makeChange [1] 0
pat [] 6 5 = [1,6] をもとめて分ける
makeChange [5,1] 6 = makeChange [1] 6 + makeChange [1] 1
pat [] 20 10 = [0,10,20]を求めて分ける
makeChange [10,5,1] 20 = makeChange [5,1] 20 
                       + makeChange [5,1] 10 
                       + makeChange [5,1] 0
--}

-- | [コイン種別]で金額を、何通りで払うことができるか求める関数
makeChange :: [Int]->Int->Int
makeChange []     _ = error "couldn't pay"
makeChange [1]    _ = 1
makeChange (c:cs) n = if c > n then makeChange cs n
                               else foldl (+) 0 $ map (makeChange cs) remains
                                    where remains = pat n c

-- | ------------------ main ----------------------
main :: IO ()
main = do
    print $ pat 100 25
    print $ pat 99 25
    print $ (pat 100 25) == (pat1 100 25)
    print $ (pat 100 25) == (pat2 100 25)
    print $ (pat 100 25) == (pat3 100 25)
    print $ (pat 99 25) == (pat1 99 25)
    print $ (pat 99 25) == (pat2 99 25)
    print $ (pat 99 25) == (pat3 99 25)
    print $ makeChange ([5,1]::[Int]) 5
    print $ makeChange ([10,5,1]::[Int]) 6
    print $ makeChange ([10,5,1]::[Int]) 10
    print $ makeChange ([25,10,5,1]::[Int]) 25
    print $ makeChange ([25,10,5,1]::[Int]) 100



実行結果
> :main
[100,75,50,25,0]
[99,74,49,24]
True
True
True
True
True
True
2
2
4
13
242
it :: ()
(0.02 secs, 573296 bytes)

プロフィール

島敏博

Shima Toshihiro 島敏博
信州アルプスハイランド在住。HaskellとElixirが好き。組み込みソフトウェアアーキテクト、C++プログラマ、山歩き、美術館巡り、和食食べ歩き、日本赤十字社救急法指導員、インデックス投資、クラシック音楽、SESSAME会員、状態マシン設計、モデル駆動開発、ソフトウェアプロダクトライン、Rubyist、実践ビジネス英語

■ ツイッター
http://twitter.com/saltheads
■ Facebook
http://www.facebook.com/saltheads
■ Qiita
http://qiita.com/saltheads

印刷する場合は、ブラウザの印刷メニューではなく、このページの上から3cmくらいの青いところにある、「印刷」を押してみてください。少しうまく印刷できます。まだ完全ではないのですが、これで勘弁してください。


カテゴリ
最新記事
月別アーカイブ
最新コメント
検索フォーム
リンク
sessame
RSSリンクの表示