- ベストアンサー
もし新しい硬貨を発行するなら、何円硬貨を発行すれば支払いで払う枚数が一番減りますか？
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枚なので) よかったりします.
関連するQ&A
- 硬貨の枚数の問題です。
１００円硬貨と５０円硬貨と１０円硬貨が全部で６枚あり、合計金額が２８０円であるという。それぞれの硬貨の枚数は何枚あるか？ 解き方が全く分からないので、どうぞ回答の程、宜しくお願いします。
- 締切済み
- 数学・算数
- 夏休みの自由研究で硬貨の発行枚数について調べているのですが・・・。
子どもが夏休みの自由研究で硬貨の発行枚数について調べています。 そこで質問なのですが、 （１）毎年の硬貨の発行枚数はどうやって決めているのでしょう？ （２） １円玉はＳ４３年、 ５円玉はｓ２９～３１年、 １０円玉はｓ３１年、 １００玉はｓ３７年、 にそれぞれ発行枚数０という年がありますが 何か特別な理由があるのでしょうか？ ３） ２０００年は発行枚数がどの貨幣も（新５００円以外）急に少なく なっているのはなぜ？ どなたか教えて下さい。宜しくお願いいたします。
- ベストアンサー
- 経済
- 500円、100円、10円硬貨の支払い方の総数について
500円、100円、10円、の3種類の硬貨がたくさんある。この3種類の硬貨を使って、1200円を支払う場合の数を求めよ。ただし使わない硬貨があってもよいとする。 という問題があり、こちらは自分で解いて理解することができました。 が、回答の検討欄に 『この問題でもしも全ての硬貨を使うとしたら、1200-610＝590（円）を支払う方法に帰着させる』 とありました。 どうしてこうなるのか、どのようにこう考えるのか、また、どの様にしてこれを導き出したか、が全く検討もつきません どなたか詳しく教えて下さればありがたいです。
- 締切済み
- 数学・算数
- １０円、５０円、１００円の３種類のどの硬貨も使って４２０円を支払うとき
１０円、５０円、１００円の３種類のどの硬貨も使って４２０円を支払うとき、何通りの方法があるか。 ただし、使用する硬貨は１５枚以下とする。 高１の数Ａ（場合の数と確率）です。解説を読んでも理解できないので困っています。
- ベストアンサー
- 数学・算数
- ５００円 １００円 ５０円 ５円 １円 の６種類
５００円 １００円 ５０円 ５円 １円 の６種類 硬貨がそれぞれ何枚かがあります。合計で５０枚あり１０００円になります。 １００円が１枚１０円玉が１６枚のとき他の硬貨はそれぞれ枚数ずつに なるのでしょうかどの硬貨も最低１枚ずつ使います。 どうも算数というか数学のことが苦手です。 どうしてもこの答えを解かなければなりません。 どうか誰か解答してください。お願いします。
- 締切済み
- 数学・算数
- １、一個１０円、３０円、５０円の３種類の品物がある。どの種類の品物も１
１、一個１０円、３０円、５０円の３種類の品物がある。どの種類の品物も１個は買うとき、合計２００円となる買い方は何通りあるか？（場合の数の問題） ２、次の硬貨の一部または全部を使って、支払うことのできる金額は何通りあるか？ (1)１０円硬貨４枚、１００円硬貨３枚、５００円硬貨２枚 (2)１０円硬貨３枚、１００円硬貨７枚、５００円硬貨３枚 （場合の数の問題） ３、男子４人、女子５人が１列に並ぶとき、次の並び方は何通りあるか？ (1)男子は男子、女子は女子で。それぞれ続いて並ぶ (2)どの男子も隣り合わない（順列の問題） ４、５個の数字０、１、２、３、４を使ってできる次のような自然数は何個あるか？ただし、同じ数字を重複して使っても良い。（重複順列の問題） この大問４問が分からないので、回答をどうかよろしくです。
- ベストアンサー
- 数学・算数
- 中学受験・割合と比です
50円硬貨と100円硬貨の2種類を使って、合計金額2625円にするのに、50円硬貨の枚数に2を加えた数を100円硬貨の枚数の5/3倍にしたいと思います。それぞれ何枚使えばよいでしょう。 100円硬貨の枚数の5/3倍から2枚をひいた数が50円硬貨の枚数 100円硬貨は3の倍数だから 100円硬貨の枚数 ３ ６ ９・・・ 50円硬貨の枚数 ３ ８ １３・・・ と解説にかいてありましたが、どうして100円硬貨は3の倍数と 考えるのでしょうか？ あと450円から550円ずつ増やしていき、数列で解いていくみたいなのですが・・・ この頭の悪い小学5年の私にすご～くわかりやすく教えてほしいのですが。 ちなみに答えは100円硬貨---15枚 50円硬貨---23枚です。 よろしくお願いします。
- ベストアンサー
- 数学・算数
お礼
回答ありがとうございます。 動的計画法は巡回セールスマン問題などで聞いたことがありましたが、すっかり忘れていました。 > えっと.... こんな硬貨, どうやって使えばいいんでしょうか? たしかに、117円硬貨なんて、使いこなせる人はいないかもしれませんね。 そこで、普通の人でも使いこなせて、比較的、合計枚数が少なくなる硬貨を考えてみました。 111円硬貨なんてどうでしょう？意外と扱いやすくないですか？ 答えを教えて頂き、ありがとうございました。お陰でスッキリしました。