Напишите программу на Python, которая определяет, сколькими различными способами можно выдать сдачу в заданную сумму. Входные данные — натуральное число n, не превышающее 106. Выходные данные — ответ на задачу. Примечание: для решения задачи используется один цикл while. Примеры: Вход: 2, Вывод: 2. Вход: 100000, Вывод: 1667116705001.
Ответ на вопрос:
Создадим массив 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))
Данное решение использует предопределенные наборы монет, которые можно легко изменить, для нахождения решения задачи.