Решение задачи
Сколькими способами можно разменять 15 рублей на монеты номиналом (достоинством) в 10, 5, 2 и 1 рубль
Условие:
Сколькими способами можно разменять 15 рублей на монеты номиналом
(достоинством) в 10, 5, 2 и 1 рубль
Решение:
Для решения этой задачи можно использовать метод динамического программирования.
Создадим массив dp, где dp[i] будет представлять количество способов разменять i рублей. Изначально все элементы массива будут равны 0.
Затем заполним массив dp следующим образом:
- dp[0] = 1, так как есть только один способ разменять 0 рублей - не давать никаких монет.
- Для каждой монеты номиналом x (10, 5, 2, 1) будем обновлять значения dp[i] следующим образом: dp[i] += dp[i - x].
После завершения алгоритма значение dp[15] будет содержать количество способов разменять 15 рублей на монеты номиналом 10, 5, 2 и 1 рубль.
Применяя этот алгоритм, получим следующий код на языке Python:
def count_ways(n):
dp = [0] * (n + 1)
dp[0] = 1
for coin in [10, 5, 2, 1]:
for i in range(coin, n + 1):
dp[i] += dp[i - coin]
return dp[n]
ways = count_ways(15)
print(ways)
В результате выполнения этого кода получим, что количество способов разменять 15 рублей на монеты номиналом 10, 5, 2 и 1 рубль равно 6.
Похожие работы
Попробуй и другие функции
Решения по другим предметам
А
Б
В
М
П
С
Т
Э