Рекурсивная функция для алгоритма изменения монет, возвращающая пустой список - PullRequest
Новая
       28

Рекурсивная функция для алгоритма изменения монет, возвращающая пустой список

0 голосов
/ 13 марта 2019

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

Например: когда доступные монеты равны {9,5,3}, а общее количество составляет 21 или 30 для этого набора монет, он возвращает пустую строку.

public class ItemPacks{

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

    public static void main(String[] args) {

        ItemPacks pack = new ItemPacks();

        System.out.println(pack.packageBreakDown(21)); //returns empty list
        //or
        System.out.println(pack.packageBreakDown(30)); //returns empty list
    }

    public List<Integer> packageBreakDown(int amount) {
        return calculateBreakdown(amount, new ArrayList<>(), 0);
    }


    private List<Integer> calculateBreakdown(int quantity,List<Integer> coins, int pos) {

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

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