- 記入中
- 参照元
- 答え
コイン両替問題
何種類かのコインがあるとき、ちょうどの金額をできるだけ少ない枚数で払うにはどうすればよいでしょうか。また、払い方は全部で何通りあるでしょうか。大きいコインから取る貪欲法は実際のお金ではうまくいきますが、コインの組によっては失敗します。すべての金額をより小さい金額から作る表なら、いつでも正しい答えが得られます。 トレイのコインをタップするとカウンターに置かれ、カウンターのコインをタップすると戻ります。メーターは金額に向かって満ちていきます。できるだけ少ない枚数で、金額ちょうどを作ってください。「最少枚数」は最善の答えを、「貪欲法」は残りの金額以下で最大のコインを常に取ったときの結果を示しますが、それが最少とは限りません。パネルでコイン(セント単位)と金額を変えられます。「表」の表示では、動的計画法が最少枚数を見つける様子や、金額を作る方法の数を数える様子を見られます。「再生」を押すと表が埋まっていく様子を見られ、「ステップ」と「戻る」で1ステップずつ進められます。ステップのスライダーをドラッグすると好きな位置に移動できます。各コインは何回でも使えます。表を選択しているときは、矢印キーで1ステップずつ移動し、スペースキーで再生・一時停止し、Home と End で最初と最後に移動します。
使い方
- トレーのコインをタップして金額ちょうどを作り、メーターがセント単位で満ちていく様子を見ましょう。
- できるだけ少ない枚数を目指し、「最少枚数」か「貪欲法」を押して比べてみましょう。
- 「表」表示を開いて再生を押し、各マスがもとになる小さい金額を読む様子を見ましょう。
最少枚数
金額 0 にはコインは要りません。それより大きい各金額では、その金額以下のコインをすべて試します。そのコインを使った残りはより小さい金額で、すでに表にあるので、コインを1枚足すと候補になります。最も小さい候補がセルに入り、それを出したコインは下の行に記録されます。表が埋まったら、目標の金額からコインを読み取ります。その最後のコインを取り、残りの金額に移り、0 になるまで繰り返します。
組み合わせの数
順番ではなく組み合わせを数えるため、表は1行ごとにコインを1種類追加します。セルは、その行までのコインで自分の金額を作る方法の数を数えます。最新のコインを使わない作り方、つまり上のセルと、最新のコインを少なくとも1回使う作り方、つまり同じ行でコインの額と同じ列数だけ左のセルの和です。コインは決まった順番で追加されるので、1 + 2 と 2 + 1 は同じ作り方で、1回だけ数えます。
よくある質問
貪欲法はなぜ失敗するのですか?
貪欲法は残りの金額以下で最大のコインを常に取り、決して考え直しません。コインが 1、3、4 で金額が 6 のとき、4 を取り、次に 1 と 1 を取ります。3 を2枚使えば済むところを3枚使ってしまいます。ユーロや米ドルのようなコイン体系では、貪欲法がたまたま最適になります。このような体系を正準(カノニカル)なコイン体系と呼びます。
作り方の数と並べ方の数の違いは何ですか?
作り方では 1 + 2 と 2 + 1 を同じ組み合わせとみなし、並べ方では別々に数えます。このアプリは、コインを1行ずつ追加して作り方を数えます。並べ方を数える場合は、金額を順にたどり、それぞれですべてのコインを試します。
コイン両替のアルゴリズムはどのくらい速いですか?
どちらの表も、コインの種類数かける金額のステップ数がかかります。数千程度の金額なら高速ですが、金額は非常に大きな数になりうるので、桁数で測ると、この問題は一般に NP 困難です。
金額が作れない場合はどうなりますか?
そのセルは ∞ のままです。たとえば、コイン 2 と 5 での金額 1 と 3 です。「組み合わせの数」モードでは、その数は単に 0 になります。
データはどこかに送信されますか?
いいえ。すべての計算はブラウザー内で行われ、最後の設定はこのブラウザーのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ