昨年末、アシュリーさんのブログでコインの組み合わせ問題の出題がありました。
詳細はコチラ↓
http://grizz.blog60.fc2.com/blog-entry-370.html
http://grizz.blog60.fc2.com/blog-entry-371.html
http://grizz.blog60.fc2.com/blog-entry-375.html
http://grizz.blog60.fc2.com/blog-entry-378.html
問題の中身は、
０～９９セントまでの金額を払う時、
（１）ちょうと払う場合の枚数
（２）お釣りも含めた場合の枚数
をできるだけ少なくする、というもの。
そして、これは、貪欲法に限ったベストな組み合わせを考えるとします。
（貪欲法については、リンク先を参照してください）
その結果が以下の通り↓
（１）ちょうど払う場合
２種類だと、｛１、１０｝
（平均９枚）
３種類だと、｛１、５、２２｝、｛１、５、２３｝
（平均５.２６枚）
４種類だと、｛１、３、１１、３７｝、｛１、３、１１、３８｝
（平均４.１枚）
（２）お釣りも含めた場合
２種類だと、｛１、１３｝
（平均４.８枚）
３種類だと、｛１、８、２９｝
（平均３.０９枚）
４種類だと、｛１、４、１０、３７｝
（平均２.５２枚）
僕が出した案は、
３種類で①｛１、７、１３｝と②｛１、８、１３｝、
４種類で③｛１、３、７、２４｝。
それぞれの平均は、
（１）の場合で、①６.５４枚②５.４８枚③４.２８枚、
（２）の場合で、①３.７２枚②３.２５枚③２.８６枚
でした。
この結果を見た時の僕の率直な感想は、
（思ったほど悪くないな）
でした。
が、この問題は数学の問題として出されたものです。
なので、僕の提案した組み合わせというのは間違いです。
リンク先のコメント欄にも書いてありますが、
この問題を機に、高校数学に再度取り組むことにしました。
アシュリーさん、この件について色々とありがとうございました。
で、一応、この問題に取り組んだ時の自分の思考回路というのを数学的に表現することを試みると、
仮に３種類のコイン｛ａ、ｂ、ｃ｝でＮセントを払う場合に必要なコインの枚数をそれぞれＡ枚（ａが必要な枚数）、Ｂ枚、Ｃ枚とすると、
Ｎ＝ａＡ＋ｂＢ＋ｃＣ
ｂ＝ａ＋ａ’、ｃ＝ａ＋ａ’’、とすると、
Ｎ＝ａ（Ａ＋Ｂ＋Ｃ）＋ａ’ Ｂ＋ａ’’ Ｃ
僕は素因数分解にこだわってたんですが、
どうして、そこまでこだわってたかというと、
頭の中にこの数式があったからではないかと思います。
この数式のみでは足りなくて、他に条件式が必要ですが。
今の僕には、このような説明しか出来なくて、これでも意味不明かもしれませんが、記事にさせてもらいました。
詳細はコチラ↓
http://grizz.blog60.fc2.com/blog-entry-370.html
http://grizz.blog60.fc2.com/blog-entry-371.html
http://grizz.blog60.fc2.com/blog-entry-375.html
http://grizz.blog60.fc2.com/blog-entry-378.html
問題の中身は、
０～９９セントまでの金額を払う時、
（１）ちょうと払う場合の枚数
（２）お釣りも含めた場合の枚数
をできるだけ少なくする、というもの。
そして、これは、貪欲法に限ったベストな組み合わせを考えるとします。
（貪欲法については、リンク先を参照してください）
その結果が以下の通り↓
（１）ちょうど払う場合
２種類だと、｛１、１０｝
（平均９枚）
３種類だと、｛１、５、２２｝、｛１、５、２３｝
（平均５.２６枚）
４種類だと、｛１、３、１１、３７｝、｛１、３、１１、３８｝
（平均４.１枚）
（２）お釣りも含めた場合
２種類だと、｛１、１３｝
（平均４.８枚）
３種類だと、｛１、８、２９｝
（平均３.０９枚）
４種類だと、｛１、４、１０、３７｝
（平均２.５２枚）
僕が出した案は、
３種類で①｛１、７、１３｝と②｛１、８、１３｝、
４種類で③｛１、３、７、２４｝。
それぞれの平均は、
（１）の場合で、①６.５４枚②５.４８枚③４.２８枚、
（２）の場合で、①３.７２枚②３.２５枚③２.８６枚
でした。
この結果を見た時の僕の率直な感想は、
（思ったほど悪くないな）
でした。
が、この問題は数学の問題として出されたものです。
なので、僕の提案した組み合わせというのは間違いです。
リンク先のコメント欄にも書いてありますが、
この問題を機に、高校数学に再度取り組むことにしました。
アシュリーさん、この件について色々とありがとうございました。
で、一応、この問題に取り組んだ時の自分の思考回路というのを数学的に表現することを試みると、
仮に３種類のコイン｛ａ、ｂ、ｃ｝でＮセントを払う場合に必要なコインの枚数をそれぞれＡ枚（ａが必要な枚数）、Ｂ枚、Ｃ枚とすると、
Ｎ＝ａＡ＋ｂＢ＋ｃＣ
ｂ＝ａ＋ａ’、ｃ＝ａ＋ａ’’、とすると、
Ｎ＝ａ（Ａ＋Ｂ＋Ｃ）＋ａ’ Ｂ＋ａ’’ Ｃ
僕は素因数分解にこだわってたんですが、
どうして、そこまでこだわってたかというと、
頭の中にこの数式があったからではないかと思います。
この数式のみでは足りなくて、他に条件式が必要ですが。
今の僕には、このような説明しか出来なくて、これでも意味不明かもしれませんが、記事にさせてもらいました。