Проект Javatalks.ru закрывается в конце Апреля 2021 года

Мы рекомендуем следующие сайты для вопросов по языку Java:


Алгоритм подсчёта количества способов размена монет

0
23 июл 2015 06:05
Здравствуйте. Есть такая задачка.

Условие

После закупки в большом универмаге Мелу досталась сдача в размере 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);
    }
}


Вопрос: как такое вывести? Т.е. код работает, но самостоятельно до такого додуматься не смог.

Ответов: 3

3
23 июл 2015 19:02
Ну это просто задача которая сводится к рекуррентному соотношению и которую поэтому можно решать либо тупо рекурсией, либо "динамическим программированием" (по сути построение рекуррентного соотношения снизу, с запоминанием результатов для переиспользования).

Смотрите, ваша функция по сути что делает - она возвращает количество способов разбиения суммы money монетами не больше той индекс которой задан как indexOfCoin.

Можно написать рекуррентное соотношение - рассмотрим его на примере. Пусть у нас есть 23 центов и мы спрашиваем, сколько способов выплатить её монетами не больше 10 центов (индекс = 2). Это количество способов складывается из двух:

- либо мы выплатим одну десятицентовую монетку, и будем считать количество способов выплатить оставшиеся 13 центов, также монетами не больше 10 центов;
- либо мы не трогаем десятицентовые, и считаем количество способов выплатить всю сумму в 23 цента меньшими монетами - т.е. не старше пятака (индекс = 1);

общее количество для 23 центов и монет не старше 10 как я уже сказал складывается из этих двух. вот у вас последняя строчка и есть сумма двух рекурсивных вызовов к той же функции либо с уменьшенным индексом максимальной монеты, либо с уменьшенной суммой.

а первые две строки определяют когда цепочка рекуррентных вызовов должна остановиться (на очевидных крайних случаях) и что она должна вернуть.

Можете для упражнения порешать задачки на ДП:

http://www.codeabbey.com/index/task_list/dynamic-programming

Из них на мой вкус Sweet Harvest самая простая и показательная. Наверное после неё понятнее станет сама концепция...
0
03 мар 2021 18:15
Понимаю, что тред еще 15 года).
Я сейчас изучаю скалу, и пришлось решать такую же задачу.
Решил посмотреть как другие делают подобное задание.
И в ваш код при некоторых входных донных дает неверный ответ.
Например:
у нас 301 монета и возможен размен такими номиналами: (5, 10, 20, 50, 100, 200, 500)
В этом случае нет решения. Ответ должен быть 0.
Но здесь
if (money == 0 || indexOfCoin == 0) return 1;

Часть условия indexOfCoin == 0 приводит к результату 1022 (вместо 0).
Поэтому надо просто удалить вторую часть условия и оставить
if (money == 0) return 1;
.
Прошу прощения за грамматические и лексические ошибки т.к. родной - Украинский.
0
27 июл 2015 06:11
Quote:
Ну это просто задача которая сводится к рекуррентному соотношению и которую поэтому можно решать либо тупо рекурсией, либо "динамическим программированием"


Из этих трёх терминов только рекурсией владею. Надо бы покурить. Спасибо.
Модераторы: Нет
Сейчас эту тему просматривают: Нет