スポンサーサイト

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

一昨日から

うちのオフィスのコンピュータは、
コインの問題の計算でかかりっきりです(笑)

計算させてる問題を全部含めるように言うと、
0セントから99セントまで払う時に、
コインの移動(お釣りありの場合となしの場合別々に)を出来るだけ減らすために、
コインの金額をどう設定すればいいのか、って問題です。


コイン3種類でベストな組合せは、{1、12、19}。

でもこれだと、ある金額を払うときに出来るだけ大きいのを順々に出していく、
貪欲法」って言う出し方が使えないんですね。

例えば、24セント払うときに貪欲法を使うと、
大きいのコインから出そうとするとまず19で、残りは1セントずつ。
{19、1、1、1、1、1}って言う出し方になります。

でも、最善の出し方はそれじゃなくて、{12、12}。
こういうコインの組合せだと、出し方を考えるのにいちいち時間がかかるんです。


そこで、貪欲法が使える組合せだけに限定する方法を今日はプログラムしてました。
で、コインが3種類の場合、貪欲法が使えるベストチョイスは、{1、5、23}と{1、5、23}。(お釣りなしの場合)

どちらも、0セントから99セントまでをちょうど払うのに、
平均5.26枚コインを使う組合せです。

日本で実際に使われてる{1、5、10、50}の組合せだと、
4種類コインがあるのに平均5枚使うのを考えると、
かなり効率が良いのは分かります。
(当然、コインの種類が多い方が、1回の取引に必要なコインの数は減ります。
極端な話、ありとあらゆる金額に対応するコインがあれば、毎回1枚で済みますし)


夜の間、3種類で、お釣りありの場合と、
4種類で、お釣りあり、なし、両方計算してもらってます。


一応言って置くと、
「最善のを見つけて、世界中でその通貨を使うようになるよう運動しよう!」
なんて事はこれっぽちも思ってませんから(笑)

ただ知りたいだけ。
数学の問題として気になるだけです。

まぁ、数学の問題としては、100を区切りにする理由は無いんですけどね。

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

コメントの投稿

非公開コメント

No title

僕はプログラミングの知識全くないですけど、
最善策を導き出す前に、素因数分解するプログラムを組めばいいんではないでしょうか。

kashさん

Mathematicaって言う、パッケージされた数学ソフトで、
関数なんかをプログラムしてやっているんですが、
素因数分解は既製の関数が付いてます。

ただ、素因数分解とこの問題との繋がりが自分には見えません。
ちょっと説明してもらえますか?

No title

支払う手段は、丁度払う(お釣りを出さない)場合に限って、話を進めます。

通貨が3種類の場合の最善策が{1、12、19}だとして、

24セント払う場合を考える時、
貪欲法だと19セント+1×5(6枚)。
しかし、支払うコインの枚数を出来るだけ少なくするということなので、最善は12×2枚。
24を素因数分解すると、
24=2の3乗+3
つまり、2で割り切れる数だということです。
これから、2の2乗×3=12(セント)が導けます。」
ただ、この考え方だと25の場合にややこしくなります。

25=5の2乗

ここで、僕の頭では2通りの考え方があります。
①25の±1を探る
②5の近似値を探る

①は、24が12×2だとわかっている事を前提にした上で最善策を探るてっとり早い方法(総当たり的なやり方ですが)。
②は、コインが3種類、1、12、19の場合で近似値を考えたら、5の近似は1です。
なので、25セント丁度支払う場合、1セント硬貨が必要になります。
なので、25=12×2+1。

一応、6の2乗や7の2乗なども考えてみましたが、
0~99までなら、①か②のやり方でプログラミングではじき出せるんじゃないかと思います。

kashさん

xを払うときに、xの約数がコインの中にあれば、
その種類のコインだけで払う方法が最善策かどうかチェックする、
って言う事ですね?

それの問題は、書かれてるように、
1種類で済む場合にしか単純には使えない事ですよね。
{1、12、19}の場合、24を払うときだけじゃなくて、
25から30を払うときも、19じゃなくて12から出した方がいいですから。

今は、「ちょうど払う」時の最善策を、
払い方を全部リストアップして、枚数が少ないのを見つける、
っていうやり方で探してるんですが、
それでもかなり短時間(多分.1秒くらい)でコンピュータは見つけてくれてます。

だから実は、その部分の改善は考えてなかったんですが、
kashさんの案がヒントでもっといいやり方のアイディアが出るかもしれません。

例えば、{1、12、19}で30を払うとき、
貪欲法だと最初のステップが19だから失敗しますが、
「最初のステップでは、使える2番目に大きいコインを使って、
そのあとは貪欲法」
って言うアルゴリズムだと、
最善策({12、12、1、1、1、1、1、1})を導き出してくれます。
(このアルゴリズムは準貪欲法って呼ぶ事にします)

ちょっとスタート地点に戻ると、
自分がやりたいのは、
貪欲法が最善策にならない事があるコインの組み合わせを除外する事です。

って事は、
必ずしも全部の値段の最善策を見つけなければならないわけじゃないんです。
1つでも最善策と貪欲法が違ってしまうケースが見つけられれば除外できますから。

「貪欲法が最善策と完璧に一致ない組合せの場合には、
(例外無く)上に出した準貪欲法が、貪欲法より良い金額がある」
って言うのが証明できれば、
この2つのアルゴリズムをチェックするだけで、貪欲法が使えるかどうかが判断できます。

まぁ、もうちょっと考えてみます。

No title

アシュリーさんのおっしゃる準貪欲法について。

30セントを考える場合、
30÷2=15
15の近似は{1、12、19}の場合は12になります。
僕が着目してほしかったのは、30の場合でいうと、2の方じゃなくて15の方です。

ちなみに、30=2×3×5です。
2+3+5=11
11の近似は12です。

もちろんこれは、コンピュータが{1、12、19}をあらかじめ導き出してくれているので、後付け発想です。何にせよ、素因数分解は手間を省くことになると思います。

それから、貪欲法のみの抽出を考える場合、少なくとも1つは別のアルゴリズム(?)は必要なんじゃないかと思います(コンピュータに計算してもらう場合、効率が良いように思います)。
物理でいうと(、、、といっても僕は物理には明るくないですけど)、相対性の考え方じゃないかなと思います。

No title

あ、計算ミスの訂正。
2+3+5=10でした。

kashさん

最初の説明でkashさんの言いたい事が分かった気がしてましたが、
2度目の説明で考えると分かりません。

最初の説明から自分が読み取ったのは、
24が2と12で割り切れるから、12を2枚で払える、と言う話です。
これは、2が素数と言う事とは関係ない話だと思います。
例えば、48を払う時には、最善策は12セント×4枚です。

そして25セントを払うときに1セントが必要なのは、
25が12と19の組合せで作れないから、です。
1が5の近似だから、と言う事ではないと思います。

例えば29を払う場合は、29自体が素数なわけで、
その近似を取ると19になってしまいます。
最善策は12×2+1×5です。

素数は自分も何より好きですが、
この問題とは関係が無いと思うんです。

アルゴリズムについて少し

貪欲法と、自分の勝手に名づけた準貪欲法のアドバンテージは、
コンピュータが(人間でも)試行錯誤しなくていい事なんです。

貪欲法のプログラムに、日本の硬貨で61円払わせる問題を出したら、
ステップ1 61円より小さい中で最大の硬貨を探す(50円)
ステップ2 50円を払って、61から50を引く(11円)
ステップ3 11円を払う問題にして、ステップ1に戻る

このループを機械的に繰り返して、払う金額が0円になるまでやれば払い方が出るんです。
(この場合ループ3回)

kashさんの提案してる方法は、
自分が理解できてないのもありますが、
ステップにして書くのがとても難しいように思います。

No title

数学の話なので、なるべく論理的にと思って考えてますが、基本的に僕は勘を働かせて考える人なので、ご了承ください。
そして、3種類の場合の{1、12、19}が最善かどうかを疑って考えてます。
2つ目のコメントで言いたかったのは、素因数分解することによって、コインの行き来の最少化とコインの種類の最適な組み合わせを同時に考えちゃおう、という欲張った考え方の提案です。

で、ちょっとお願いがあるんですが、
{1、7、13}
{1、8、13}
でのコインの行き来(丁度払う場合でも構わないです)の平均を出して頂けませんか?
({1、12、19}の場合と比較してみてほしいです)

No title

あ、貪欲法を有効な手段にすることとかけ離れちゃってすいません。

kashさん

{1、7、13}と{1、8、13}のチェックですね。了解です。
(自分の組んだプログラムが間違ってなければ、
確実に{1、12、19}の方が良いと言っておきますが、笑)

意図は分かりましたが、
素数とこの問題の関係が何度読んでも分かりません。

No title

お願いした件は、よろしくお願いします。
これは、アシュリーさんに対抗するとかの意味ではなく、自分の頭はどこまでのものなのか試しているだけなので、その辺り、誤解しないでくださいませ。

で、素数との因果関係ですが、僕も見いだせてないです。
ただの勘としか。
前のコメントで言ったように、コインの最少化と、使う硬貨の種類を割り出す計算を同時に行うのに効率がよいと思っただけです。
近似を用いたのは、後付けです。

で、今回の問題に対してですが、
僕はまず、コインが2種類の場合を考えてみました。
その場合、大ざっぱに計算してみて{1、72or73}。
(お釣りなしで)
使う枚数は、99の場合(以下、case99)で26枚か27枚。
この(大ざっぱな)計算が正しいと仮定して(この仮定が間違ってる可能性は大いにあります)、n=2の場合で26か27→3の3乗。
n=3の場合はアシュリーさんがはじき出してくれましたが、case99で9= 3の2乗 枚。
であれば、
n=4の場合は3の1乗で、case99で3枚になるように計算すればいいんではないか、と思ったわけです。
で、方程式組んだりしてやってたんですが、僕の頭ではなかなか上手くいきませんでして。
(この辺、僕の頭は日本式に毒されているのでアメリカほど合理的ではないんじゃないか、と)
なので、アメリカで4種類のコインで平均4.7枚ならば、平均4枚以下を目指そう、と。
で、
その場合の効率的なやり方を考えてみた場合、素因数分解を思いつきました。

といった具合です。

kashさん

kashさんに頼まれた計算も含めて、
ここまでの結果を記事にしますね。

「アシュリーさんに対抗するとかの意味」
と言う風には取ってませんから、心配しないで下さい。
数学の話をしてる以上、正しい事は正しくて、間違っている事は間違ってます。
僕が言ったから反対されたくない、なんて事は思ってません。

ただ、僕が{1、12、19}と言う結果をどうやって得たのか、
kashさんが誤解されてるように思うんです。

この結果は、
「xを払うのに12セントがあるといいから、12セントを含めよう」
と言う風にやって出したわけではありません。

全ての3種類のコインの組合せをコンピュータに試させて、
平均で必要なコインの数が最小だった、
と言う組み合わせが{1、12、19}なんです。

全ての可能性はすでに試されてるわけで、
僕がなんと言っても、kashさんがなんと言っても、これが最善だと言うのは覆りません。
(プログラムが間違っていなければ)

つまり、kashさんの言う、
「3種類の場合の{1、12、19}が最善かどうかを疑って考えてます」
って言うのは、
ピタゴラスの定理を疑って考えてます、と言うようなものなんです。
FC2ブログランキング

FC2ブログランキング

プロフィール

アシュリー

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

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

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

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

ブログ内検索
カレンダー
07 | 2017/08 | 09
- - 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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。