Английский
УкраинскийУсловие
После закупки в большом универмаге Мелу досталась сдача в размере 17 центов. Он получил одну десятицентовую монету, одну пятицентовую и 2 монеты по 1 центу. Позже, в этот же день, он делал покупки в мини-маркете, где тоже получил сдачу в размере 17 центов. На этот раз он получил две монеты по 5 центов и 7 монет по 1 центу. Тогда Мел задался вопросом: «Как много магазинов я могу посетить и получить сдачу в 17 центов различным набором монет?» После небольшого мозгового штурма, он определил, что ответ 6. Тогда он бросил вызов вам для решения более общего случая.
Напишите программу, которая определит количество различных комбинаций американских монет(1 цент, 5 центов, 10 центов, 25 и 50 центов), которые могут сложиться в определенную сумму.
Входные данные: ввод будет состоять из множества чисел между 0 и 30000 включительно, по одному в каждой строке.
Выходные данные: на каждое входное число, нужно определить число комбинаций и вывести, как показано в примере.
Пример:
Input:
17
11
4
Output:
There are 6 ways to produce 17 cents change.
There are 4 ways to produce 11 cents change.
There is only 1 way to produce 4 cents change.
На хабре в комментах предложили такой вариант
public class Coins {
private static int[] COINS_NOM = {1, 5, 10, 25, 50};
public static int getCountOfWays(int money) {
return getCountOfWays(money, 4);
}
/**
* КАК ДО ТАКОГО ДОДУМАТЬСЯ???
*/
private static int getCountOfWays(int money, int indexOfCoin) {
if (money < 0 || indexOfCoin < 0) return 0;
if (money == 0 || indexOfCoin == 0) return 1;
return getCountOfWays(money, indexOfCoin - 1) + getCountOfWays(money - COINS_NOM[indexOfCoin], indexOfCoin);
}
}
Вопрос: как такое вывести? Т.е. код работает, но самостоятельно до такого додуматься не смог.