|
|
|
|
お釣り計算アルゴリズムここではお釣り最適の定義のページに書かれているルールにしたがって、最適な払い方を求めるためのアルゴリズムを説明します。 といっても、それほど難しいものではなく、単純に払う硬貨枚数とお釣りとして受け取る硬貨枚数を計算し、支払い後の硬貨枚数が最も少なくなるような払い方を求めるだけです。 計算手順としては、以下のようになります。
この計算によって、ある値段の買い物をしたときにどうやって払うのがベストかを求めることができます。 ひとつ注意が必要なところは、1.において持ち金額を入力すると、それに対応する持ち硬貨枚数が一意に決まるという点です。例えば持ち金額が5円のとき、1円玉5枚という可能性と、5円玉一枚という可能性が考えられますが、最適な支払い方している場合には常に5円玉一枚と考えてよいということです。 このことは、次のようにして簡単に理解できます。 今1円玉が五枚あるとします。すると、以前の支払いにおいて、財布の中の1円玉とお釣りとして受け取った1円玉の枚数の合計が五枚であったことになります。そうであれば、そのときに持っている1円玉を支払って、1円玉以外の硬貨でお釣りをもらうことが出来たはずです。よって、支払い後に財布に残る1円玉の枚数は常に4枚以下となります。 同様の議論によって、500円玉、50円玉、5円玉については1枚以下、100円玉、10円玉、1円玉については4枚以下ということが分かります。したがって、持ち金額が決まれば持ち硬貨枚数が一意に決まるわけです。 ここでは紙幣については考えず、硬貨だけを対象としていますので、金額の下三桁だけを考えれば十分です。よって、持ち金額が1円から1000円のそれぞれの場合について、1円から1000円の代金を支払うときの最適な方法を考えれば良いことになります。組み合わせの数としては1000×1000で100万通りです。 100万通りともなると、さすがに手作業で調べるという訳にはいきませんので、上記のアルゴリズムにそってプログラムを書き、この100万通りについて調べてみました。最適な支払い方の一覧のページにその結果を、最適な支払い方の一覧の見方のページにその説明を示します。 |
||
|
|
|||