Блог

Проблема в том:

Напишите статический метод 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. это НЕ домашнее задание, это добровольная практика

Ваш 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]