Сколько способов есть выдать сдачу в n рублей, если имеется неограниченное количество монет в 1, 2, 5, 10 рублей?
Сколько способов есть выдать сдачу в n рублей, если имеется неограниченное количество монет в 1, 2, 5, 10 рублей? Например, 5 рублей можно выдать четырьмя способами: 5=2+2+1=2+1+1+1=1+1+1+1+1. Входные данные: натуральное число n, не превышающее 100. Выходные данные: выведите ответ на задачу. Пример ввода: 2. Пример вывода: 2.
Лина 49
Для решения этой задачи можно использовать метод динамического программирования. Пусть d[i] - количество способов выдать сдачу в i рублей.Для начала, инициализируем массив d, в котором будем хранить количество способов выдать сдачу для каждого значения от 0 до n. Следующим шагом будет заполнение массива пошагово.
Обозначим индексы массива d как сумму выдаваемой сдачи. То есть, d[i] будет содержать количество способов выдать сдачу в i рублей.
Стартовое значение d[0] равно 1, так как сдачу в нулевую рубль можно выдать единственным образом - не выдавая ничего.
Для остальных значений i от 1 до n производим заполнение массива следующим образом:
1. Перебираем все возможные монеты для выдачи – 1, 2, 5 и 10 рублей.
2. Для каждой монеты c рассчитываем количество способов выдать сдачу в i рублей, используя монеты только с номиналами, которые меньше или равны c.
3. Добавляем количество способов выдать сдачу в i - c рублей к d[i].
4. После перебора всех монет значение d[i] будет представлять собой сумму всех возможных вариантов выдачи сдачи в i рублей.
5. В итоге, после прохода по всему циклу мы получим d[n] – количество способов выдать сдачу в n рублей.
Пример решения задачи для входных данных n = 2:
Инициализация массива d:
d = [1, 0, 0, 0]
Расчет значений массива d:
i = 1
- Рассчитываем количество способов выдать сдачу в 1 рубль, используя монеты 1, 2, 5 и 10 рублей:
Количество способов выдать сдачу в 0 рублей: d[0] = 1
- Обновляем значение d[1]: d[1] = d[1] + d[1 - 1] = 0 + 1 = 1
i = 2
- Рассчитываем количество способов выдать сдачу в 2 рубля, используя монеты 1, 2, 5 и 10 рублей:
Количество способов выдать сдачу в 1 рубль: d[1] = 1
Количество способов выдать сдачу в 0 рублей: d[0] = 1
- Обновляем значение d[2]: d[2] = d[2] + d[2 - 1] + d[2 - 2] = 0 + 1 + 1 = 2
Ответ: 2
Для решения данной задачи мы использовали динамическое программирование, а именно метод заполнения массива пошагово, основываясь на предыдущих значениях массива.
Если будут возникать дополнительные вопросы или потребуется пояснение других задач, обращайтесь!