Question

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

Answer 1

Ответ:

Объяснение:

n = int(input('n: \n'))  

counter = 0  

for coin1 in range(0, n+ 1):  

  for coin2 in range(0, (n // 2) + 1):  

      for coin5 in range(0, (n // 5) + 1):  

          for coin10 in range(0, (n // 10) + 1):  

              if coin1 * 1 + coin2 * 2 + coin5 * 5 + coin10 * 10 == n: counter += 1  

print(counter)

Answer 2

Эта задача может быть решена с использованием динамического программирования. Давайте создадим массив dp, где dp[i] будет хранить количество способов выдать сдачу в i рублей. Изначально, dp[0] равно 1, так как есть только один способ выдать сдачу в 0 рублей - не выдавать ничего.

Затем мы будем перебирать каждую монету (1, 2, 5 и 10 рублей) и обновлять массив dp следующим образом: dp[i] += dp[i - монета].

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

Пример кода на Python:

pythonCopy code
n = int(input())
coins = [1, 2, 5, 10]
dp = [0] * (n + 1)
dp[0] = 1

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

print(dp[n])

При вводе 2 программа вернет 2, а при вводе 5 вернет 4, как в вашем примере.