パスワードを忘れた? アカウント作成
547380 journal

TarZの日記: 硬貨考(重たい財布、そして2進数) (続き) 1

日記 by TarZ

先日(12/08)の日記「硬貨考(重たい財布、そして2進数)」より
  >手持ち金額・支払い金額から、支払うべき硬貨を求めるアルゴリズムも、実に簡単で済む。

読んでいる方が複数いらっしゃるようなので(←すいません、Friendsでない人の日記って
どうやって見つけるんですか!? 「最近更新した日記」を監視し続ける?)、答え合わせ
のためにメモ。勘違いがあったら突っ込んでおいてください。

… … … …

入力パラメータ(以降、入力パラメータや変数は字体を変えて表現する)
  - 手持ち金額
  - 支払い金額

条件
  - 話を簡単にするため、手持ち金額支払い金額よりも多いという前提とする。

支払い金額よりも、支払い後に手元に残る金額で考えたほうが簡単なので、変数を1つ導入する。

        残金 = 手持ち金額 - 支払い金額

手持ち金額残金を比較し、違ったビットがあればそれが出入りする硬貨なのだ、と考えれば
あとは楽。

手持ち金額にあって残金にないものが支払い硬貨に該当するビット。つまり、
        (手持ち金額 XOR 残金) AND 手持ち金額
これが支払い金額となる。

残金にあって手持ち金額にないものがお釣り硬貨に該当するビット。つまり、
        (手持ち金額 XOR 残金) AND 残金
これがお釣り。

「支払い後、財布の中に残る硬貨が最も少なくなるような計算である」ことを忘れてはいけない。
ここで求めているのは、支払える最小の金額ではない。
0b1101(13)円を持っていて、0b0011(3)円の買い物をしたとき、支払いは0b0100(4)円玉で十分だが、
お釣りで0b0001(1)円が帰ってくるので1円玉の重複が発生する。これを避けるためには、支払いは
4円玉と1円玉で0b0101(5)円とし、お釣りで0x0010(2)円をもらう。

… … … …

釣りが900円きたことから思わぬボリュームのコンテンツに育ったが、これでおしまい。ちなみに、
自販機以外はほとんどEDY決済なので小銭を使う機会がなかなかなく、現時点でも100円玉は
まだ8枚残ってます…。とほほ。orz

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by gm300 (14617) on 2005年12月09日 16時46分 (#845491) ホームページ 日記
    1 円から 1023 円までの商品が大体均等に分布しているとしてという前提ですよね。

    私は実践していませんが、もっと簡単な方法をしっています。
    用意する種類、個数において優れているだけではなく、計算処理の単純さおいても、みためにも効果があります。

    千円札で払って、「レシートも釣もいらん!袋もいらん。エコロジー万才」というのです。
    自動販売機は環境に優しくないので、その存在を否定しましょう。
    どうです? これなら、現状の貨幣制度での実行可能です。
typodupeerror

犯人はmoriwaka -- Anonymous Coward

読み込み中...