再帰バックトラッキングを使用して、ペニー (1 セント)、ニッケル (5 セント)、ダイム (10 セント)、およびクォーター (25 セント) を使用して、特定の金額を変更するすべての方法を見つけるメソッド makeChange を記述します。
たとえば、37 セントを両替する場合は、次のように使用できます。
- 1四半期
- 1 ダイムと 2 ペニー
- 3 ダイムと 7 ペニー
- または他の組み合わせ。
メソッドは 1 つのパラメーターを受け入れる必要があります。変更するセントの金額です。
メソッドの出力は、1 行に 1 つずつ、合計するとその金額になる各タイプのコインのすべての組み合わせのシーケンスである必要があります。
たとえば、クライアント コードに次の呼び出しが含まれていたとします。
System.out.println(" P N D Q");
System.out.println("------------");
makeChange(28);
生成される全体的な出力は次のようになります。
P N D Q
------------ [3, 0, 0, 1] [3, 1, 2, 0] [3, 3, 1, 0] [3, 5, 0, 0] [8, 0, 2, 0] [8, 2, 1, 0] [8, 4, 0, 0] [13, 1, 1, 0] [13, 3, 0, 0] [18, 0, 1, 0] [18, 2, 0, 0] [23, 1, 0, 0] [28, 0, 0, 0]
この問題を解決するための重要な洞察は、硬貨の各額面 (ペニー、ニッケルなど) を見て、その硬貨のすべての可能な数 (1 ペニー、2 ペニー、...、28 ペニー) を試して何がわかるかという概念です。その選択から始まる組み合わせを作ることができます。たとえば、上記の出力では、最初に 3 ペニーで始まるすべての組み合わせが表示され、次に 8 ペニーで始まるすべての組み合わせが表示されます。
バックトラックには一連の選択肢の調査が含まれるため、コード内で何らかの方法でコインの種類を表す必要があります。処理のために、すべてのコインの額面値のリストを保持することをお勧めします。さまざまなコインの値を処理するときに、このリストの内容を変更できます。以下のテンプレートは出発点です (コピーしてコード テキスト ボックスに貼り付けて開始できます)。
public static void makeChange(int amount) {
List coinValues = new LinkedList();
coinValues.add(1); // penny
coinValues.add(5); // nickel
coinValues.add(10); // dime
coinValues.add(25); // quarter
// ... your code goes here ...
メソッドに渡された変更の量は負ではないと考えるかもしれませんが、100 を超える可能性があります。
だからここに私のコードがあります：
public static void makeChange(int amount){
int[] acc = new int[4];
makeChange(amount, acc);
}
private static void makeChange(int amount, int[] acc){
if(amount == 0){
System.out.print("[" + acc[0]);
for(int i = 1; i < 4; i++){
System.out.print(", " + acc[i]);
}
System.out.print("]");
System.out.println();
}
if(amount > 0){
acc[0]++;
makeChange(amount - 1, acc);
acc[0]--;
acc[1]++;
makeChange(amount - 5, acc);
acc[1]--;
acc[2]++;
makeChange(amount - 10, acc);
acc[2]--;
acc[3]++;
makeChange(amount - 25, acc);
acc[3]--;
}
}
そして、makeChange(28) の呼び出しに対するその出力:
[28, 0, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 0, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[13, 1, 1, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[18, 2, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
...(何百行もの出力があります)
重複した出力が生成される理由を教えてもらえますか? どうもありがとう！