Блог

Я работаю над функцией, которая разбивает заданные входные данные на наименования с помощью рекурсивного вызова.

На каждом шаге он преобразуется в два варианта:

1. Продолжайте с текущей монетой: добавьте ее в список и выполните рекурсию.
2. Переключитесь на следующую монету: увеличьте количество монет pos и повторите.

В дополнение к распечатке комбинации номиналов, записанных в списке, когда остается == 0, я намерен записать значение этого списка и вернуть его из функции.

Вот код:

     static final int[] DENOMINATIONS = {9,5,3};

    private static void change(int remaining, List<Integer> coins, int pos)

        if (remaining == 0) {

       // This correctly prints the desired output. 
       // I want to return that exact value from the function.
            System.out.println(coins); 

        } else {
            if (remaining >= DENOMINATIONS[pos]) {
                coins.add(DENOMINATIONS[pos]);
                another.addAll(coins);
                change(remaining - DENOMINATIONS[pos], coins, pos);
                coins.remove(coins.size() - 1);
            }
            if (pos   1 < DENOMINATIONS.length) {
                change(remaining, coins, pos   1);
            }
        }
    }


    public static List<Integer> denominations(int amount) {
        List<Integer> result = new ArrayList<Integer>();
        List<Integer> another = new ArrayList<Integer>();
        change(amount, result, another ,0);
        System.out.println(another.size());
        return another;
    }

    public static void main(String[] args) {
        List<Integer> list = denominations(13);
        System.out.println(list);
    }
  

Вывод: [5, 5, 3]

Вам пришлось бы добавить return coins; в метод and of change , но вы можете оставить его таким, какой он у вас есть. Возврат и изменение массива — это запах кода, поскольку метод одновременно работает с объектом (изменяет его) и возвращает результат.

Чтобы заставить это работать, вы можете определить свой denomination метод следующим образом:

 public static List<Integer> denominations(int amount) {
   List<Integer> result = new ArrayList<Integer>();
   change(amount, result, 0);
   return resu<
}
  

Редактировать:

Список пуст, потому что единственное место, где он был изменен, находится здесь:

 coins.add(DENOMINATIONS[pos]);
change(remaining - DENOMINATIONS[pos], coins, pos);
coins.remove(coins.size() - 1);
  

Где элемент добавляется и удаляется. Это то, что вы написали, что делает его пустым 🙂

Правка2:

Я бы предложил передать второй объект, который был бы копией списка, который вы хотели бы вернуть, и не был изменен.

Вы, кажется, предполагаете, что java передается по ссылке, что неверно. Методы Java передаются по значению.

Я обновил ваш код:

изменить метод:

 private static List<Integer> change(int remaining, List<Integer> coins, int pos) { // Updated method return type;

    if (pos < 0 || pos >= DENOMINATIONS.length) { // check if position is invalid
        return new ArrayList<>(); // return an empty list
    }

    if (remaining == DENOMINATIONS[pos]) { // check if remaining is equal to denominations[pos]
        coins.add(DENOMINATIONS[pos]); // add the denominations to the coins result
        return coins; // return the result
    } else if (remaining > DENOMINATIONS[pos]) { // check if remaining is greater than denominations[pos]
        coins.add(DENOMINATIONS[pos]);// add the possible denominations to the coins result
        remaining = remaining - DENOMINATIONS[pos]; // calculate the new remaining
        if (remaining >= DENOMINATIONS[pos]) { // check if remaining is greater than or equal to denominations[pos]
            return change(remaining, coins, pos); // stick to this position
        } else {
            return change(remaining, coins, pos   1); // increment pos to go to the lower denominations
        }
    } else if (remaining < DENOMINATIONS[pos]) { // check if remaining is lesser than denominations[pos]
        if (coins.isEmpty()) { // if coins is empty then go to the next denomination
            return change(remaining, coins, pos   1);
        } else {
            coins.remove(coins.size() - 1); // remove the previous denomination
            return change(remaining   DENOMINATIONS[pos - 1], coins, pos); // go back to the previous remaining and // try this DENOMINATIONS[pos]
        }
    }
    return coins;
}
  

метод деноминации:

 public static List<Integer> denominations(int amount) {
    return change(amount, new ArrayList<Integer>(), 0);
}
  

ВВОД : 13
ВЫВОД : [5, 5, 3]

change должно возвращать логическое значение, означающее, был ли найден ответ.

Итак, change тело выглядит следующим образом:

 if (remaining == 0) {
  return true;
}
...
if (change(...)) return true;
...
return false;  // It's last line of body