Напишите программу на Python, которая определяет, сколько способов есть выдать сдачу в сумме n рублей, если имеется

Тема урока: Выдача сдачи в рублях

Разъяснение: Для решения данной задачи на Python мы можем использовать динамическое программирование и один цикл while. Создадим список dp, в котором будем хранить количество способов выдать сдачу для каждой суммы от 0 до n. Изначально все значения списка dp должны быть равны 0. Затем установим dp[0] равным 1, поскольку существует один способ выдать 0 рублей (не выдавать ничего). Внутри цикла while перебираем каждую возможную монету (1, 2, 5, 10 рублей) и обновляем значения списка dp для всех сумм больше или равных текущей монете. Для каждой суммы i, значение dp[i] будет равно сумме значений dp[i - 1], dp[i - 2], dp[i - 5] и dp[i - 10], поскольку мы можем получить текущую сумму, добавив одну из доступных монет к сумме (i - 1), (i - 2), (i - 5), (i - 10).

Доп. материал:

def count_change(n):

    dp = [0] * (n + 1)

    dp[0] = 1

    

    coins = [1, 2, 5, 10]

    

    for coin in coins:

        i = coin

        while i <= n:

            dp[i] += dp[i - coin]

            i += 1

    

    return dp[n]

    

n = int(input("Введите сумму: "))

print("Количество способов выдать сдачу:", count_change(n))

Совет: Чтобы лучше понять алгоритм решения и принцип работы динамического программирования, рекомендуется просмотреть видео-уроки или прочитать дополнительные материалы по этой теме.

Задача на проверку: Напишите программу на Python, которая определяет, сколько способов есть выдать сдачу в сумме 15 рублей, используя монеты с номинациями 1, 2 и 5 рублей.