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

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

Создадим массив dp длиной n+1, где каждый элемент dp[i] будет содержать количество способов выдать сдачу суммой i.

Инициализируем dp[0] = 1, так как существует только один способ — не выдавать никакую монету.

Затем будем проходить в цикле по всем монетам, начиная с монеты наименьшего достоинства и заканчивая монетой суммой n. Для каждой монеты будем обновлять значения dp[i], учитывая количество способов выдать сдачу с использованием предыдущих монет.

Конкретнее, для каждой монеты j будем обновлять dp[i] следующим образом:
dp[i] = dp[i] + dp[i — j]

То есть значение dp[i] увеличивается на количество способов выдать сдачу суммой (i — j), где j — текущая монета.

После завершения цикла значение dp[n] будет содержать искомое количество способов выдать сдачу суммой n. Выведем его на экран.

Вот решение на языке Python:

python
def count_change(n):
    dp = [0] * (n+1)
    dp[0] = 1

    coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000]

    for coin in coins:
        for i in range(coin, n+1):
            dp[i] += dp[i - coin]

    return dp[n]

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

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