Question

Сколькими способами можно уплатить без сдачи 28 руб. имея монеты по 1 и 5 руб.

Answer 1

Заплотить можно6 способами

Answer 2

5 монет по 5 и 3 по1 = 25+3=28

4 по 5 и 8 по 1 = 20+8=28

3 по 5 и 13 по 1 = 15+13=28

2 по 5 и 18 по 1 = 10+18=28

1 по 5 и 23 по1 = 5+23=28

Answer 3

Для определения количества способов уплатить без сдачи 28 рублей, имея монеты по 1 и 5 рублей, мы можем использовать метод динамического программирования.

Представим, что у нас есть массив dp длиной 29 (так как нам нужно учесть все суммы от 0 до 28). Изначально все элементы в массиве равны 0.

Затем мы начинаем обрабатывать каждую сумму от 1 до 28. Для каждой суммы мы рассматриваем два случая:

1) Если мы не используем монету по 5 рублей, то сумма будет состоять только из монет по 1 рублю. В этом случае мы можем просто взять значение dp[сумма-1] и присвоить его dp[сумма].

2) Если мы используем монету по 5 рублей, то сумма будет состоять из монет по 1 рублю и одной монеты по 5 рублей. В этом случае мы можем взять значение dp[сумма-5] и присвоить его dp[сумма].

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

Программный код на языке Python, реализующий описанный алгоритм, выглядит следующим образом:

dp = [0] * 29
dp[0] = 1

for i in range(1, 29):
    dp[i] += dp[i-1]
    if i >= 5:
        dp[i] += dp[i-5]

print(dp[28])

Запустив этот код, мы получим ответ: 13 способов уплатить без сдачи 28 рублей, имея монеты по 1 и 5 рублей.