Hatena::Grouphaskell

すばらしき functional programming

 | 

2008-08-01合理的な預かり金額(Part4)

コードの第1版

billsJPY :: [Integer]
billsJPY = [10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1]

unfold :: Integer -> [Integer] -> [Integer]
unfold 0 _  = []
unfold r [] = error ("Give me coin:" ++ show r)
unfold n (b1:bs) | n < b1 = unfold n bs
unfold n (b1:bs)          = b1:unfold (n-b1) (b1:bs)

commonbills :: [Integer] -> [Integer] -> Bool
commonbills [] _ = False
commonbills _ [] = False
commonbills (a1:as) (b1:bs) | a1 == b1 = True
commonbills (a1:as) (b1:bs) | a1 <  b1 = commonbills (a1:as) bs
commonbills (a1:as) (b1:bs) | a1 >  b1 = commonbills as (b1:bs)

reasonable :: Integer -> Integer -> Bool
reasonable amount collect | amount == collect = True
reasonable amount collect | amount > collect = False
reasonable amount collect = not (commonbills (unfoldJPY collect)
                                             (unfoldJPY (collect - amount)))
                            where unfoldJPY a = unfold a billsJPY

注: どのような出し方をしても、ちょうどの金額を出せば合理的、足りないのは不合理

テスト

Main> unfold 251 billsJPY
[100,100,50,1]
Main> commonbills [10, 5, 1] [100, 2]
False
Main> commonbills [10000, 10, 5] [5, 1]
True
Main> reasonable 251 300
True
Main> reasonable 251 301
True
Main> reasonable 251 500
True
Main> reasonable 251 1001
True
Main> reasonable 251 270
False
Main> reasonable 251 400
False
Main> reasonable 251 20000
False
Main> reasonable 3600 6100
True

とりあえず、よさそうです。でもちょっと気になるのは

1. 預かり金をもっとも少ない枚数の紙幣硬貨の組み合わせで表す

という部分。出し方がわからないのにこの仮定はいいんでしょうか。

3. お釣をもっとも少ない枚数の紙幣硬貨の組み合わせで表す

はよさそうです。610円の買い物に[1000, 50, 50, 10]円出したりするのは500円玉をお釣としてもらうことを期待しています。「500円玉切らしちゃってるんですよー」とか言われたら、すごすごと50円玉を引っ込めるしかありません。

でも、3600円の買い物に[5000, 1000, 100]円出したりは普通しませんよね。2000円札が却ってくる可能性はほとんどありませんから。でも、2000円札はほとんど流通していないという事情は考慮しなくていいことにしましょう。

ところで、ジンバブエってご存じですか?

[つづく...]

 |