Сколько способов есть выдать сдачу в n рублей, если имеется неограниченное количество монет в 1, 2, 5, 10 рублей?

  • 14
Сколько способов есть выдать сдачу в 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

Для решения данной задачи мы использовали динамическое программирование, а именно метод заполнения массива пошагово, основываясь на предыдущих значениях массива.

Если будут возникать дополнительные вопросы или потребуется пояснение других задач, обращайтесь!