スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

簡単に考えれば良かった

しつこくコインの問題です。

自分のこの問題への取り組みは、こういう順番を取ってました。

最初はまず、どんなにハチャメチャでも良いから、
払う枚数を最小に出来るパターンをしらみつぶしに探そう、と。

100セント以下のコイン3種類の場合、
{1、12、19}と言うのはこの方法で出た答えです。

この組み合わせの良くないのは、よーく考えないと、効率よく払えない金額が多い事。
この3種類のコインがあったとして、67セントをどうやって払いますか?
即答出来たら尊敬します(笑)


と言うわけで、払える中で出来るだけ大きいコインを順々に取っていく、
「貪欲法」で払える組み合わせに限って、これまたしらみつぶしに探しました。

それで出てきた答えは、{1、5、22}と{1、5、23}。
この組み合わせなら、引き算さえ出来れば効率よく払えます。


でも、一番シンプルなケースをちゃんと考えてませんでした。

実在する日本のコインの例に戻ってみます。
100円未満の金額だけを扱う事にすると、
日本で発行されてるコインは{1、5、10、50}の4種類。

この組み合わせの特徴は、
5円玉は1円玉が5個、
10円玉は5円玉が2個、
50円玉は10円玉が5個、
100円は50円玉が2個、と言う風に、
全部のコインが、次に安いコインの倍数の金額なんです。

どの2種類を選んでも、
大きいの1枚と、小さいの何枚かで両替できる、って言う事にもなります。
(アメリカだと、1、5、10の次が25なんで成り立ちません)


こういう組み合わせだと、0円から99円まで払う時に必要な平均枚数は、
大した計算も無く出てきます。
↓こういう計算です。

99円まで払う場合、
1円玉は0~4枚、5円玉は0~1枚、10円玉は0~4枚、50円玉は0~1枚使う可能性があって、
この範囲内の枚数の組み合わせ全部が、それぞれ違う金額に対応してます。

と言う事は、0円から99円まで、全部1回ずつ払ったとすると、
1円玉を払う平均枚数は0、1、2、3、4の平均だから2枚、
5円玉を払う平均枚数は0、1の平均で0.5枚。
同じように10円玉は平均2枚、50円玉は0.5枚使う事になります。
(ちょっといい加減な説明です。やりたければもっと厳密に言えます)

つまり、種類を問わず使った平均枚数は、2+0.5+2+0.5=5枚。
前の記事を見てもらえば分かりますが、これは正解です。


日本のと同じように、
全部のコインが、1つ下のコインの倍数になってる場合は、
これと同じような計算で、ちょうど払うのに必要な平均枚数が出てきます。
(これはただの経験則じゃなくて、証明できる事です)


そこで、100円未満のコインが2種類だけだった場合を考えてみましょう。
1円と100円の間に1つコインがあるって事ですが、
その金額は、100を割り切れる数にしたいんです。

可能性は、2、4、5、10、20、25、50の7つ。

2円の場合、1円玉を平均0.5枚、2円玉を平均24.5枚使って、平均25枚。
4円の場合、1円玉を平均1.5枚、4円玉を平均12枚使って、平均13.5枚。
5円の場合、1円玉を平均2枚、5円玉を平均9.5枚使って、平均11.5枚。
10円の場合、1円玉を平均4.5枚、10円玉を平均4.5枚使って、平均9枚。

これまた証明は書きませんが、掛け合わせて100になる数(2と50、4と25、5と20)は、
どっちを選んでも平均枚数は同じになります。

コイン2種類で最適なのは、10円玉がある場合、って事です。


「全部のコインが...」って言葉で書くと煩わしい条件は、
代数的に言うと、{1、a、a×b、a×b×c...}って言う組み合わせ、って事です。

そして、使う平均枚数=((a-1)+(b-1)+(c-1)...)/2、と言う公式で表せます。

これはまた厳密じゃない言い方ですが、
この枚数を最小化したい場合には、
出来るだけa、b、c...を、それぞれに近い数字にしたいんです。

2種類で10円がベストなのは、aとbが同じ数(10)だからです。
(前の記事のコメントで書いた「累乗法」の、この考え方はあってました)


3種類でベストなのは、4×5×5=100なのを考慮して、
a、b、cを4、5、5(とそれを並び替えた組み合わせ)にすれば良いんです。
(kashさんへ:素因数分解が役に立つのはここです)

そうやって出てくるコインの組み合わせは、
{1、4、4×5}={1、4、20}
{1、5、5×4}={1、5、20}
{1、5、5×5}={1、5、25}の3つ。

3つとも、平均枚数=((4-1)+(5-1)+(5-1))/2=5.5枚です。


この辺にしておきます。ワイルズじゃないですが。

テーマ : 数学
ジャンル : 学問・文化・芸術

コメントの投稿

非公開コメント

No title

魅力的な記事、ありがとうございます。

{1、12、19}で67セント払う場合ですが、
貪欲法に従わなくてもいいとして、
最初に思ったのが、
19×4-12×1-1×5。
ただ、これだと10枚必要なんで、よく考えてみました。
19×3+12×1-1×2=67
これだと6枚。
たぶん、これなんじゃないかなぁ、と。

kashさん

お釣りなしでお願いします。
{1、12、19}はお釣りなしで最適な組み合わせなんで。
(実はkashさんの答えより枚数が少ない答えがありますし)

当然、貪欲法は無視です。
貪欲法なら、即答できます。
(19、19、19、1、1、1、1、1、1、1、1、1、1)で13枚です。

No title

19×1+12×4=67
ですかね?

kashさん

5枚未満で67セントが払えない事が証明できれば、
5枚で払うkashさんの答えが正解、って事です。
FC2ブログランキング

FC2ブログランキング

プロフィール

アシュリー

Author:アシュリー
カリフォルニア州バークリー在住、元スポーツジャンキーのアシュリーです。

今観るスポーツは、アーセナル(サッカー)とグリズリーズ(バスケ)、あとテニス。

専門の物理ネタ以外にも、色々書いていくつもりです。

Twitterをハンドル名Inoueianでやっています。

ブログ内検索
カレンダー
09 | 2017/10 | 11
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 - - - -
最近の記事
最近のコメント
最近のトラックバック
カテゴリー
リンク
RSSリンク
月別アーカイブ
メールフォーム

名前:
メール:
件名:
本文:

カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。