ジンバブエは、最近そのすさまじいインフレで日本でもニュースに登場しています。年率220万%というすごさだとか。1000億ジンバブエドル札も発券されましたが、パン1斤は7月30日現在、2000億ジンバブエドル（以下、ZWD, $）だそうです。
このようなハイパーインフレは、何も生産することができないような国情という、単なる経済問題ではない生活の破壊を反映した現象です。エイズの蔓延のため平均寿命は30歳代、政治も3月下旬に行われた大統領選挙の結果が5月下旬まで公表されず、再選挙となるも野党候補は襲撃迫害を恐れて決選投票を辞退せざるをえませんでした。めちゃくちゃです。
ところで、デノミです。デノミとは、貨幣の呼び方を変えること。たとえばいままで100円と表現していたものの価値を1円と言い換えることです。うまい棒は10銭になります。月給は3000円とかでしょうか。日本には決済金額としての100分の1単位通貨がありませんから、デノミを行ってもドルやユーロなどの主要通貨と桁がそろっていいかもしれません。とくに利点は思い浮かびませんが…。
ジンバブエでは、ATMがあまりの高額紙幣を扱いきれなくなりそうなため、8月1日に100億分の1に呼び方を変えるデノミを行い、ジンバブエ準備銀行（中央銀行）は新しい紙幣を発行しました。ウェブサイトによると、新しい紙幣硬貨は $500紙幣, $100紙幣, $25硬貨, $20紙幣, $10紙幣と$10硬貨、$5紙幣と$5硬貨、$2硬貨、$1紙幣と$1硬貨、50セント, 20セント, 10セントの硬貨*1だそうです。
で、預かり金の問題に戻ります。
$31の買い物のときに、$41を出しました。$20紙幣2枚と、$1紙幣です。$10のお釣をもらうことを期待した、合理的な預かり金です。ところが、これを第1版のアルゴリズムにかけると、
Main> unfold 41 [500, 100, 25, 20, 10, 5, 2, 1] [25,10,5,1]
預かり金の中に$10が含まれていると計算され、$10のお釣に対して合理的な預かり金ではなくなってしまいます。さて、どうしましょう。
[つづく...]
*1：本稿では100分の1通貨単位 -セント- を扱いません。あしからず
コードの第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円札はほとんど流通していないという事情は考慮しなくていいことにしましょう。
ところで、ジンバブエってご存じですか?
[つづく...]
「合理的～」トピックをサスペンドしたまま雑談。
このブログでは、言語比較論争をしたり、むずかしい代数学の概念を扱ったりすることはありません。たぶん。そんな力もないですし。単なる練習問題として用意されたようなものではない、何らかのトピックを持ち出して、Haskellでコードを書いてみるというようにしたいと思っています。かなり初心者向きの話もできたらしてみたいです。
私がHaskellに出会ったのは今から15～6年は前のことです。"Haskell Report 1.2" などと1ページ目に書いてあるドキュメントを印刷して、ていねいに製本して読んだりしました。「演算子が自分で定義できるんだから、yaccじゃパース出来ねえじゃん」とか、「コンビネータのリダクションの話は結局なんの役に立つんだ?」とか愚痴っていました。
今では社内情報システム部門で「開発者は本当に索引を定義して性能評価したのか?」とか、「PCの管理者権限はユーザーにあるのに、IP Host-to-Host でファイアウォールの許可設定をするのって、何のセキュリティ?」とか愚痴っています。
まあ、このブログは自分で飽きないことを最大の目標にしようと思います。
1000円は最初から出す必要がないからです。
このあたりにアルゴリズムの要があるような気がします。出す必要がないものを出していることを検出したい。
例を考えましょう。どのような金額でも、買い物の合計金額より10000円以上多い預かり金額は合理的ではありません。預かり金に10000円札が含まれていれば、その10000円札がいりませんし、含まれていなくてもその中でいちばん高額な紙幣または硬貨が少なくともいりませんね。仮にレジにいったん入れたとしても、
お釣として却ってきます。
出した物がお釣として却ってくる…。じゃあ、次のような考え方はどうでしょう。
billsJPY :: [Integer] -- 日本円の紙幣硬貨の種類（降順） unfold :: Integer -> [Integer] -> [Integer] -- 紙幣硬貨内訳 commonbills :: [Integer] -> [Interger] -> Bool -- 共通紙幣を探す reasonable :: Interger -> Integer -> Bool -- 目的の関数
を書いてみることにしましょう。
[つづく...]
やりたいことは「なんとなく」解ってもらえたでしょうか。ただ、これだけでは曖昧すぎます。関数を定義するには、もっとちゃんとしたルールが必要でしょう。
まず、ルール1。
支払の全額は現金によって行う
ことにします。つまり、30円分の割引クーポンや、1050円分のプリペイドカードなどを使った支払は考慮しなくてよいことにします。支払は10000円札、5000円札、2000円札、1000円札、500円硬貨、100円硬貨、50円硬貨、10円硬貨、5円硬貨、1円硬貨の組み合わせによって行われるものとします。まあ、この制約を加えたところで、レジの付加機能としてまったく意味のないものになるということもないでしょう。
次に、ルール2。
明らかに合理的でない場合のみFalseを返す
つまり、2800円の買い物に対して4000円を出すことはアリです。なぜなら2000円札を2枚出しているかもしれないから。2000円札が存在しなかった場合、4000円は合理的ではありません。最も枚数が少なく支払われた場合でも、1000円札が4枚となり、1000円は最初から出す必要がないからです。紙幣硬貨のさまざまな組み合わせで4000円となっている場合でも、とにかく1000円分はいらないのです。もっとも、このルールがないとすべて1円玉で支払われる可能性を考慮して、1円でも多く支払われたらFalseを返すという面白くもなく役にも立たないプログラムになってしまいます。プログラムは第1種の誤りを犯すことは認められておらず、第2種の誤りを犯すことは認められている、ってことになるのでしょうね。
とくに断わっていませんが、預かり金は金額のみが入力され、紙幣硬貨の枚数の内訳は分からないとします。そんなの実際にレジでいちいち入力していられません。もちろん機械にかけてしまえば出来ないことはありませんが、機械に吸い込まれた1000円札が本当に10000円札ではなかったということをいつも客が納得してくれるかは分かりません。なんでも機械に任せればいいというものでもないようです。
で、結局合理的な預かり金かどうかって、どうやって決められるのでしょう？
[つづく...]