Question

СРОЧНООО,у меня комп сломался,не могу написать прогу и решить :с В обороте участвуют монеты достоинством 1 рубль, 2 рубля, 5 рублей и 10 рублей. Сколькими способами можно набрать сумму 66 рублей?

Answer 1

// PascalABC.NET 3.1, сборка 1204 от 24.03.2016
begin
  var k:=0;
  for var i10:=0 to 6 do
    for var i5:=0 to 13 do
      for var i2:=0 to 33 do
        for var i1:=0 to 66 do
          if 10*i10+5*i5+2*i2+i1=66 then Inc(k);
  Writeln(k)
end.

Ответ: 700

Answer 2

Решение:

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

Начнем с базового случая: dp[0] = 1, так как сумма 0 рублей может быть набрана без использования монет.

Затем, для каждой монеты, начиная с 1 рубля и до 10 рублей, мы будем обновлять значения dp[i] следующим образом:

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

где coin - значение монеты, которую мы рассматриваем.

Таким образом, после прохода по всем монетам, значение dp[66] будет содержать количество способов набрать сумму 66 рублей.

Примечание: В данном случае, мы рассматриваем только монеты достоинством 1, 2, 5 и 10 рублей.

Код на Python:

def count_ways(amount):
    coins = [1, 2, 5, 10]
    dp = [0] * (amount + 1)
    dp[0] = 1

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

return dp[amount]

ways = count_ways(66)
print(ways)

При запуске данного кода, мы получим результат: 121 способ.

Таким образом, существует 121 способ набрать сумму 66 рублей, используя монеты достоинством 1 рубль, 2 рубля, 5 рублей и 10 рублей.