М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
1HM
1HM
27.05.2021 10:27 •  Информатика

Выдача сдачи
Имеется неограниченное количество монет в 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

👇
Ответ:
pva1992
pva1992
27.05.2021
Хорошо, давайте разберём эту задачу вместе.

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

Для начала, создадим список 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.

Надеюсь, что объяснение было понятным и полезным! Если у вас есть ещё вопросы по данной задаче, пожалуйста, напишите мне.
4,4(74 оценок)
Проверить ответ в нейросети
Это интересно:
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ