TarZの日記: 硬貨考(重たい財布、そして2進数) 5
自販機にて、1000円札で100円の飲み物を買ったら、お釣りに100円玉が9枚。
運悪く、たまたま100円玉以外にも小銭が多かったので、とてつもなく財布が厚く、
そして重くなってしまった。…くそう、900円玉を発明してくれ!>造幣局
# そう言えば、消費税が導入されて缶ジュースが\110になったときは、
# 「110円玉を発明してくれ」と冗談を言った記憶があるなあ。
… … … …
普段の買い物では、なるべく財布の中に小銭が少なくなるように支払っている。
実践している人も多いと思うが、支払いがxxx7円で財布の中に2円あれば、躊躇なく
その2円は支払いに使う。だから、お釣りが555円のようなケースもありうる。ここ
までぴったりだとニンマリだ。
しかし、前述のように自販機の場合には期待通りの釣銭が出るとは限らない。
まあ、この自販機のようなケースは除外できると仮定しよう。今、ここが、自販機も
清く正しく釣銭を返してくれる世界だったとする。つまり、50円玉が存在するのに
自販機が釣銭で10円玉を5枚返してきたとか、2000円札の流通量が少なくて1000円札
2枚を持つことになるといったケースは除外できるとする。
このような世界で、最悪のケースでも財布の中の硬貨の数をできるだけ少なくしたい。
どのような硬貨単位の体系にすれば良いだろうか。
直感的には2進数にすればよさそうだ。1円玉、2円玉、4円玉…512円玉が存在するような
硬貨体系の場合、1023円までは最悪のケースでも9枚の硬貨が財布の中にあれば良い。
一般的な書き方をすると、n円までは log2(n)を下回らない数の硬貨があればよい。
現在のような1円玉、5円玉、10円玉、50円玉…500円玉の場合では、1000円までで最悪の
ケース(999円)では 4+1+4+1+4+1 = 15枚の硬貨が必要だ。
2進硬貨が実現すれば、持たなければならない硬貨の数は劇的に減る。さらに、支払い
の際の硬貨の動きは、2進加減算と全く同じ挙動を示す。手持ち金額・支払い金額から、
支払うべき硬貨を求めるアルゴリズムも、実に簡単で済む。(興味のある方は考えてみて
ください)
おお、実にエキサイティング! こんな便利な硬貨の体系を実践している国がないとは
信じられない。
問題は…2進数方式は、硬貨の種類もlog2(n)種類必要ということか。イギリスのように
2進硬貨に近い体系(1,2,5,10,20...)を実現している国はあるが、貨幣の種類多すぎ!
さて、逃避はやめて仕事をするか…。
それって、どっかで見たな、、、 (スコア:1)
1, 2, 3, 5, 8, 13, 21, 34, 65, 99, ...
という、フィボナッチ数列でもよいはず。で、硬貨の種類が同じ10
の場合に、硬貨の数9でいくつまで表現できるかというと、、、
(プログラム中、、、)
494円と出ました。うーん。計算が面倒な割に、使い勝手が悪そうな
硬貨体系になってしまった。
#まぁ、フィボナッチの場合、(ほとんどの場合)次の硬貨は前の硬
#貨の倍より小さいですから、当然ですが。
Re:それって、どっかで見たな、、、 (スコア:1)
少なくとも私の頭では即答できないです…。
2進の方は回答 [srad.jp]を載せておきましたのでよろしければどうぞ。
Re:それって、どっかで見たな、、、 (スコア:1)
単にはなりそうもないです。
あ、999円まで全部テーブル参照にして、、、ドス!o=(=~=
#前ので、フィボナッチ数列を間違えてた、、、orz orz orz
硬貨じゃないですが (スコア:0)
コイン専用 (スコア:0)
別AC