Hatena::Grouphaskell

すばらしき functional programming

 | 

2008-07-29合理的な預かり金額(Part3)

1000円は最初から出す必要がないからです。

このあたりにアルゴリズムの要があるような気がします。出す必要がないものを出していることを検出したい。

例を考えましょう。どのような金額でも、買い物の合計金額より10000円以上多い預かり金額は合理的ではありません。預かり金に10000円札が含まれていれば、その10000円札がいりませんし、含まれていなくてもその中でいちばん高額な紙幣または硬貨が少なくともいりませんね。仮にレジにいったん入れたとしても、

お釣として却ってきます。

出した物がお釣として却ってくる…。じゃあ、次のような考え方はどうでしょう。

  1. 預かり金をもっとも少ない枚数の紙幣硬貨の組み合わせで表す
  2. 預かり金額から買い物金額を引いてお釣を計算
  3. お釣をもっとも少ない枚数の紙幣硬貨の組み合わせで表す
  4. 預かり金の紙幣硬貨の内訳と、お釣の紙幣硬貨の内訳を比べ、共通の紙幣硬貨が含まれていれば合理的でない
billsJPY :: [Integer] -- 日本円の紙幣硬貨の種類(降順)
unfold :: Integer -> [Integer] -> [Integer] -- 紙幣硬貨内訳
commonbills :: [Integer] -> [Interger] -> Bool -- 共通紙幣を探す
reasonable :: Interger -> Integer -> Bool -- 目的の関数

を書いてみることにしましょう。

[つづく...]

 |