#java #recursion
#java #рекурсия
Вопрос:
Проблема в том:
Напишите статический метод makeChange, который использует рекурсивное отслеживание возврата, чтобы найти все способы внести изменения на заданную сумму денег, используя пенни (1 цент), никели (5 центов), десятицентовики (10 центов) и четвертаки (25 центов). Например, при внесении изменений на 37 центов вы могли бы использовать: 1 четверть, 1 десятицентовик и 2 пенни; 3 десятицентовика и 7 пенни; или другие комбинации.
Ваш метод должен принимать единственный параметр: количество центов, на которое нужно внести изменения. Выводом вашего метода должна быть последовательность всех комбинаций каждого типа монет, которые в сумме составляют эту сумму, по одной на строку. Например, если клиентский код содержал следующий вызов:
System.out.println(«P N D Q»);
System.out.println(«————«);
Внесите изменения(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]
Мое решение состоит в том, чтобы сохранить список целых чисел, соответствующих четырем номиналам. Отдельный метод обрабатывает общую стоимость «монет» в списке. Рекурсивный метод увеличивает количество «монет» каждого номинала до тех пор, пока сумма не будет равна заданному значению, после чего он печатает. К сожалению, мое решение печатает много дубликатов каждой возможной комбинации монет. Почему?
public static void makeChange(int n) {
ArrayList<Integer> combos = new ArrayList<Integer>();
combos.add(0);
combos.add(0);
combos.add(0);
combos.add(0);
System.out.println(" P N D Q");
System.out.println("------------");
makeChange(n, combos);
}
public static void makeChange(int n, ArrayList<Integer> combos) {
int sum = getSum(combos);
if (sum == n) {
System.out.println(combos.toString());
} else {
for (int i = 0; i < combos.size(); i ) {
combos.set(i, combos.get(i) 1);
if (getSum(combos) <= n) {
makeChange(n, combos);
}
combos.set(i, combos.get(i) - 1);
}
}
}
public static int getSum(ArrayList<Integer> combos) {
int sum = combos.get(0);
sum = 5 * combos.get(1);
sum = 10 * combos.get(2);
sum = 25 * combos.get(3);
return sum;
}
Пример вывода:
вызов makeChange(6) выдает следующий результат:
P N D Q
————
[6, 0, 0, 0]
[1, 1, 0, 0]
[1, 1, 0, 0] <——- дублировать
P.S. это НЕ домашнее задание, это добровольная практика
Комментарии:
1. Было бы полезно, если бы вы также показали свой вывод.
2. в какой момент вашего кода вы проверяете, была ли комбинация уже записана? Я этого не вижу, но это могут быть просто мои глаза.
3. Имеет смысл, что вы получаете дублирующиеся выходные данные из этого кода. Я не уверен, что вы можете этого избежать. Вы могли бы отслеживать предыдущие решения и не распечатывать их, но это было бы довольно беспорядочно в этом рекурсивном коде.
4. не 1 голосование, не одно принятие, не 1 ответ?
5. Однако может существовать совершенно другой способ использования рекурсии, который не создавал бы дубликатов.
Ответ №1:
Ваш for
цикл сбрасывает i
переменную на ноль каждый раз, когда вы вызываете свою рекурсивную функцию, и это приводит к дублированию выходных данных.
Вам нужно передать эту переменную в качестве входного параметра:
public static void makeChange(int n) {
List<Integer> combos = new ArrayList<Integer>(); // you should declare as List, not ArrayList
combos.add(0);
combos.add(0);
combos.add(0);
combos.add(0);
System.out.println(" P N D Q");
System.out.println("------------");
makeChange(n, 0, combos);
}
public static void makeChange(int n, int i, List<Integer> combos) {
int sum = getSum(combos);
if (sum == n) {
System.out.println(combos.toString());
} else {
while (i < combos.size()) {
combos.set(i, combos.get(i) 1);
if (getSum(combos) <= n) {
makeChange(n, i, combos);
}
combos.set(i, combos.get(i) - 1);
i;
}
}
}
Для makeChange(28)
это выводит:
P N D Q
------------
[28, 0, 0, 0]
[23, 1, 0, 0]
[18, 2, 0, 0]
[18, 0, 1, 0]
[13, 3, 0, 0]
[13, 1, 1, 0]
[8, 4, 0, 0]
[8, 2, 1, 0]
[8, 0, 2, 0]
[3, 5, 0, 0]
[3, 3, 1, 0]
[3, 1, 2, 0]
[3, 0, 0, 1]
для makeChange(6)
он выводит:
P N D Q
------------
[6, 0, 0, 0]
[1, 1, 0, 0]
Имейте в виду, что P < N < D < Q. Ваше предыдущее решение снова увеличивало P после нахождения хорошего P, и в этом нет необходимости
Редактировать Чтобы отменить вывод, вы можете сначала записать вывод в список, а затем, когда процесс завершен, вывести список:
public static void makeChange(int n) {
List<Integer> combos = new ArrayList<Integer>();
List<String> output = new ArrayList<String>();
combos.add(0);
combos.add(0);
combos.add(0);
combos.add(0);
System.out.println(" P N D Q");
System.out.println("------------");
makeChange(n, 0, combos, output);
for(String s: output) {
System.out.println(s);
}
}
public static void makeChange(int n, int i, List<Integer> combos, List<String> output) {
int sum = getSum(combos);
if (sum == n) {
output.add(0, combos.toString());
} else {
while (i < combos.size()) {
combos.set(i, combos.get(i) 1);
if (getSum(combos) <= n) {
makeChange(n, i, combos, output);
}
combos.set(i, combos.get(i) - 1);
i;
}
}
}
Теперь, для 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. Обновлены функции для обратного вывода