もし新しい硬貨を発行するなら、何円硬貨を発行すれば支払いで払う枚数が一番減りますか？

質問

現在、日本で一般的に使用されている硬貨は
1円、5円、10円、50円、100円、500円の6種類だと思いますが、
もし、新しい硬貨を発行するとして、何円硬貨を発行すれば
1～999円のそれぞれの支払いに必要な硬貨の合計枚数が最も減るでしょうか？

ただし、新しい硬貨は999円以下の自然数とし、
支払いは、必ず合計枚数が最も少なくなるような組み合わせで払うとします。

私が計算したところ、意外な結果が出たので、
もしよろしければ、皆さんの結果を教えて下さい。

回答No.10

Tacosan · ベストアンサー

この手の問題はだいたい NP-困難なので多項式時間でまともに解くのは難しいんですが, 常套手段として動的計画法 (Dynamic Programming, DP) というのがあります.
で, DP で解いてみました. 以下, 手元のプログラムが間違っていないという前提でいきます.
少ない方のトップ5 は
117円: 5630枚
133円: 5637枚
112円: 5642枚
121円, 88円: 5642枚
でした. 166円硬貨だと 5657枚で, 183円硬貨と並んで 11位タイ.
えっと.... こんな硬貨, どうやって使えばいいんでしょうか?
ちなみに 1000円硬貨まで許して 10000円までで数えると 917円硬貨を追加したときの 106,604枚がベストの模様. 499円硬貨までだと 479円硬貨の 131,309枚がベストっぽい感じですが, 実は 1000円硬貨を追加する方が (120,000枚なので) よかったりします.

お礼

回答ありがとうございます。
動的計画法は巡回セールスマン問題などで聞いたことがありましたが、すっかり忘れていました。

> えっと.... こんな硬貨, どうやって使えばいいんでしょうか?
たしかに、117円硬貨なんて、使いこなせる人はいないかもしれませんね。
そこで、普通の人でも使いこなせて、比較的、合計枚数が少なくなる硬貨を考えてみました。
111円硬貨なんてどうでしょう？意外と扱いやすくないですか？

答えを教えて頂き、ありがとうございました。お陰でスッキリしました。

回答No.15

Tacosan

現状だと 1-5-10-50-100-500 というステップなんだけど, ここから (1以外の) どれを抜いても「その前の金額の比」が 10 で変わらないので, どこを抜いても同じですね. 1-2-5-10-25-50-100-200 というステップ (ex. アメリカ) だと, どこを抜くかで比が変わるため必要枚数も変わってくるんじゃないでしょうか.
ちなみにオーストラリアでは 5セント単位のはず.

お礼

アメリカの25って、なんか使いにくいイメージがあるんですよね。私が25を使いたくなる金額は、「23、24、25、26、27」ぐらいしかないんですが…。

国によって硬貨の種類が異なるのは、何か理由がありそうですね。とても勉強になりました。ありがとうございました。

回答No.14

silverbear

No7,9,11です。
硬貨を減らす問題ですか。
個人的に直感では５００円でした。１円がなくなると使い物にならないのと、１０，１００円がないと４００円等を数えるのが５の倍数となり１の倍数より面倒だから　と言う理由です。

ふと思ったんですが、硬貨をなくす場合当然「国」がなくしますよね？と言う事は１円をなくすのがもっとも効率がいいのかもしれません。
１円硬貨がなくなるということは当然４円以下切り捨てと言う事になると思います。（今の「銭」のようなイメージですね。無いお金は使えない。消費税も小数点以下切り捨てですから。）
他の硬貨ですと支払い枚数が増えるのに、1円硬貨だけは支払い枚数が減る可能性があります。
また、お金の切り捨てがあると経済効果があるかもしれません。

消費税が出る前は子供だったこともあり、1円玉・5円玉は殆ど見たことがありませんでした。しかし、消費税が出来た次の月あたりから見る機会がものすごく増えました。それが昔に戻るだけだと思います。

これは邪道な考え方かもしれませんが、受験者の中には居るかもしれませんよ。

お礼

なるほど、そのような理由で「1円硬貨」と答える受験者もいるかもしれませんね。
それはそれですばらしい回答がと思います。採用してしまうかも。

私の直感だと、50円硬貨ですかね。
1円は、消費税が払えなくなるし、
5円は、お賽銭が使えなくなるし、
10円は、ないと不便だし、
100円は、自動販売機で困るし、
500円は、500円貯金が出来なくなるし。
こんな理由では不採用になりそうですね^^;

回答No.13

adinat

ANo.12です。88円硬貨投入したときの答えをミスってました。5642枚ですね。平均5.642枚必要、最大で9枚ってとこですか。117円の平均5.63枚、最大10枚と比べてると、こちらの方が使い勝手は多少よいのかも知れませんね。111円なら平均5.74枚、最大で10枚です。

硬貨を抜く問題、どれでも一緒なんですね。さすがに1円を抜くわけにはいかないから、5円～500円、どの硬貨がなくても、平均で9.5枚（9500枚）、最大で19枚の硬貨が必要なようです。

お礼

早速の回答、ありがとうございます。

>硬貨を抜く問題、どれでも一緒なんですね。
>さすがに1円を抜くわけにはいかないから、5円～500円、
>どの硬貨がなくても、平均で9.5枚（9500枚）、
>最大で19枚の硬貨が必要なようです。

正解です。この問題なら、唯一の答えはないので、
面接で聞くと面白いかも知れません。
（どの硬貨を廃止しても同じ、と答えたら即採用、
　"１円硬貨"と答えたら、即お帰り願います^^）

回答No.12

adinat

答えは既に117が最小であると出てますので、最小枚数ですむ場合を計算させてみました。
79 9 5685
83 9 5686
84 9 5682
88 9 5672
89 9 5709
92 9 5675
となるようです。これらの硬貨を発行すれば、必ず9枚で支払えます。期待値を最小にするには117ですね。この場合は99円など10枚必要な場合があります。

エクセルで組む方法の一例です。
セルc1～k1に0～8を入力して、
セルc2に「=$A2-$B$1*C1」として、k2までオートフィルします。
さらにセルc4に「=IF(C$2-$B4<1;"";INT(C2/500)+INT(MOD(C2;500)/100)+INT(MOD(C2;100)/50)+INT(MOD(C2;50)/10)+INT(MOD(C2;10)/5)+MOD(C2;5)+C1)」として、k4までオートフィルします。
さらにセルc5に「=IF(C$2-$B4<1;"";IF(MOD(C$2-$B4;500)=0;C4+13;IF(MOD(C$2-$B4;100)=0;C4+9;IF(MOD(C$2-$B4;50)=0;C4+8;IF(MOD(C$2-$B4;10)=0;C4+4;IF(MOD(C$2-$B4;5)=0;C4+3;C4-1))))))」として、セルk1002までオートフィルします。
セルa4～a1002までは順に999～1と入力しましょう。
セルl4には「=MIN(C4:K4)」として、l1002までオートフィルします。
さらにセルl1に「=SUM(L4:L1002)」として、l2には、「=MAX(L4:L1002)」とでもしましょう。
セルa2には「999」と入力しておきます。
あとはお好みで、l1とl2とb1あたりの色を変えておいて、b1にたとえば「117」と入力するとうまくいくと思います。

open officeでやっているので、もしかしたら、セミコロン（；）をコロン（：）にかえるとかが必要かも知れません。

さすがに10000円までやりたかったり、全部の答えを一気に出したかったら、マクロを組んだり、プログラム組んだりは必要ですね。n円硬貨入れた場合ぐらいでしたら、エクセルでもよさそうです。

回答No.11

silverbear

No７．９です。
なんか、１円～５００円までを全部９枚までで計算してたのを、5,50,500円を１枚、1,10,100円を４枚までしか使用しないように制限しただけですんごく早く動くようになりました。（１０個の硬貨の計算が３秒ぐらい）
なので、１～１０００まで数えさせてみました。（プログラミングの腕が悪いってことですね。すいませんたぶんもう少し早くはなりそうな気がしますが。）

１６６円硬貨なら５６５７枚でした。-1843
一番少ないのは１１７円硬貨で５６３０枚でした。-1870

お礼

回答、ありがとうございました。
10番さんと同じ答えなので、117円が本当の答えみたいですね。これはExcelでは解けませんね^^;

最初は、2円とか3円じゃないかな、と気軽に考えていたのですが、いざ冷静に考えてみると奥が深く、とても面白かったです。

そもそも、この問題を思いついたのは、新卒採用の一次面接の質問を考えていたときでした。

「あなたが新しい硬貨を発行するとしたら、何円硬貨を発行しますか？」という質問をすれば、ものを考えるプロセスが観察できてよいのでは、と思ったのですが、一応、学生に質問する前に、自分なりの答えを見つけておこうと思い、この問題を考え始めました。

今思うと、この問題を一次面接でするのは難しすぎますね。

そこで、面接向けにちょっと内容を変えてみました。
次の問題、わかりますか？^^

「現在、発行されている6種類の硬貨(1円,5円,10円,50円,100円,500円)のうち、1つだけ廃止するとしたら、どの硬貨を廃止しますか？」

回答No.9

silverbear

No8さん指摘ありがとうございます。大きいものから順に入れるんじゃだめなんですね。全然気づきませんでした。
ソフト作って数えさせてみました。（１円から５００円までを0～9枚ずつ全部足して、目的の金額になるかを比較し、合ってたらOKで、最小値を求めました。なので９円玉の998円=11枚の計算です。）

今ある硬貨の最小の組み合わせで０円～９９９円までの組み合わせを全部出す場合、７５００枚必要でした。（合ってますか？？）
＋２円硬貨なら６７００枚でした。-800
＋３円硬貨なら６７００枚でした。-800
＋４円硬貨なら６６２０枚でした。-880
＋６円硬貨なら６６４０枚でした。-860
＋７円硬貨なら６４２０枚でした。-1080
＋８円硬貨なら６３２０枚でした。-1180
＋９円硬貨なら６３００枚でした。-1200
＋１１円硬貨なら６３００枚でした。-1200
＋１２円硬貨なら６１６０枚でした。-1340
＋１３円硬貨なら６１１０枚でした。-1390
＋１４円硬貨なら６３８０枚でした。-1120
＋１５円硬貨なら６８００枚でした。-700
＋２５円硬貨なら６７００枚でした。-800
（書き間違い、プログラムミスあったらごめんなさい）

一つの硬貨を数えさせるのに２～３分かかるソフトなので、これ以上はちょっとやりたくないです。（２分としても全部やると３３時間はかかるのか・・・）
プログラムをもうちょっと変更して、暇な日に自動的に９９９円までを数えさせるようにして実験してみようかとは思いますが・・・。
補足を見る限りですと、質問者さまのエクセルの計算方法が998円で９円硬貨の時１４枚ですから、ちょっと違う結果になってると思います。

今のところ１３円が怪しいです。ただ、実際１３円硬貨が出来ても効率よく使うことはできないんだろうなぁ・・・・

お礼

プログラムまで作成して頂き、ありがとうございます。

> 今ある硬貨の最小の組み合わせで０円～９９９円までの組み合わせを全部出す場合、
> ７５００枚必要でした。（合ってますか？？）

私も、現在の硬貨で必要な合計枚数は「7500枚」となりました。まずは一安心です^^;

補足

私もNo8さんの指摘で、自分の考え方が違うことに今気が付きました。盲点でした。。。

私が使っていたアルゴリズム(No.9さんと同じ、大きいものから入れる方法)では、166円硬貨で
「-1464枚」まで減らすことが出来ています。

ということで、大きいものから入れるのではなく、本当の意味で最適の組み合わせを探せば、もっと枚数が減らせそうですね！

うーん、これは奥が深すぎる…。

回答No.8

adinat

♯7サマへ。

たとえば、998円は9円硬貨を2枚使えば、900=5枚、80=4枚、18=2枚で、12枚で支払えると思われます。

結構面倒な問題ですよね。いろいろと参考になりました。>皆様

補足

確かに、結構面倒な問題かもしれません。
私はExcelでごりごりと全ケースを計算しましたが、
数学的な計算で求める方法はあるんですかね？

回答No.7

silverbear

>1～999円のそれぞれの支払いに必要な硬貨の合計枚数が最も減るでしょうか？

999：１５枚、998：１４枚、989：１４枚、899：１４枚
これが多い組み合わせであるため、これらを減らすことが出来れば最も減らせたと言える。

９円硬貨の場合
999：１１枚、998：１４枚、989：１０枚、899：１０枚　997：１３枚
この９円硬貨のおかげで下一桁が９の金額（９９の組み合わせに影響）において大幅に支払い枚数が減る

８円硬貨の場合
999：１２枚、998：１１枚、989：１１枚、899：１１枚　997：１３枚
この８円硬貨のおかげで下一桁が８以上の金額（198の組み合わせに影響）において支払い枚数が減る

７円硬貨の場合　
999：１３枚、998：１２枚、989：１２枚、899：１２枚、997：１１枚
この７円硬貨のおかげで下一桁が７以上の金額（297の組み合わせに影響）において支払い枚数が減る

２円硬貨の場合　
999：１３枚、998：１３枚、989：１２枚、899：１２枚、997：１２枚
この２円硬貨のおかげで下一桁が2,3,4,7,8,9の金額（594の組み合わせに影響）において支払い枚数が減る

結果、
影響が大きいのは９円硬貨（９０円、９００円でも同じ）
たくさん使われる可能性が高いのは２円硬貨（２０円、２００円でも同じ）
平均的に減らせるのは７円硬貨、８円硬貨（７０円、７００円でも同じ）
かな？と思います。

補足

> 999：１５枚、998：１４枚、989：１４枚、899：１４枚
> これが多い組み合わせであるため、これらを減らすことが出来れば最も減らせたと言える。

15枚と14枚になる値段は、
　15枚：999円
　14枚：499円、899円、949円、989円、994円、998円
となりました。

また、例えば9円硬貨を発行した場合、15枚と14枚必要だった値段は、以下のように減りました。

999円：15枚→11枚（-4）
998円：14枚→14枚（減らすことが出来ず）
994円：14枚→14枚（減らすことが出来ず）
989円：14枚→10枚（-4）
949円：14枚→10枚（-4）
899円：14枚→10枚（-4）
499円：14枚→10枚（-4）

回答No.6

cocomonchi

#4です
度々すいません
５円玉の存在を忘れていました…

結果３円玉ではないでしょうか？

回答No.5

Trick--o--

通常時の最大枚数１５枚（９９９円）
２円硬貨などを追加、最大枚数１３枚

12枚以下に出来るのかな……
流石に全部試すのは疲れるぞ。

補足

私も、最初は色々と考えながら決めうちで考えていましたが、
だんだん面倒になり、Excelで計算してしまいました。(^^)

私は1～999円の全ての値段で、11枚以下にすることができました。
しかし、10枚以下は出来ませんでした。