Выдача сдачи
Имеется неограниченное количество монет в 1, 2, 5, 10 рублей. Определите, сколькими можно выдать сдачу в n рублей. Например, 5 рублей можно выдать четырьмя : 5=2+2+1=2+1+1+1=1+1+1+1+1.
Входные данные
Программа получает на вход натуральное число n, не превышающее 100.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод
Вывод
2
2
5
4
Для решения данной задачи можно использовать подход динамического программирования, который поможет нам сделать вычисления максимально эффективными.
Для начала, создадим список dp размером n+1, где каждый элемент будет хранить количество способов выдать сдачу в i рублей. Изначально все элементы списка равны 0.
Затем, инициализируем базовые значения:
dp[0] = 1 - вариант выдать сдачу в 0 рублей имеет только одно решение - не выдавать ничего.
Теперь мы готовы заполнить остальные элементы списка. Для этого мы будем проходить по каждой монете (1, 2, 5, 10 рублей) и для каждой монеты будем проходить по всем значениям i от 1 до n. Мы будем увеличивать значение dp[i] на значение dp[i - coin], где coin - это значение монеты.
Давайте рассмотрим пример для n = 5:
1 рубль:
dp[1] = dp[1] + dp[0] = 0 + 1 = 1
dp[2] = dp[2] + dp[1] = 0 + 1 = 1
dp[3] = dp[3] + dp[2] = 0 + 1 = 1
dp[4] = dp[4] + dp[3] = 0 + 1 = 1
dp[5] = dp[5] + dp[4] = 0 + 1 = 1
2 рубля:
dp[2] = dp[2] + dp[0] = 1 + 1 = 2
dp[3] = dp[3] + dp[1] = 1 + 1 = 2
dp[4] = dp[4] + dp[2] = 1 + 2 = 3
dp[5] = dp[5] + dp[3] = 1 + 2 = 3
5 рублей:
dp[5] = dp[5] + dp[0] = 3 + 1 = 4
В итоге получаем, что количество способов выдать сдачу в 5 рублей равно 4.
Вот и все! Давайте запишем код, который решит эту задачу:
```python
n = int(input())
dp = [0] * (n + 1)
dp[0] = 1
for coin in [1, 2, 5, 10]:
for i in range(coin, n + 1):
dp[i] += dp[i - coin]
print(dp[n])
```
Теперь наша программа способна выдать количество способов выдать сдачу в n рублей для любого значения n, не превышающего 100.
Надеюсь, что объяснение было понятным и полезным! Если у вас есть ещё вопросы по данной задаче, пожалуйста, напишите мне.