Question

Несколько десятилетей назад были в ходу монеты по 3 и 5 коп. Сколькими способами можно набрать ими сумму в 10 р.?

Answer 1

Так как 10 руб. =1000 коп на 3 не делится нацело ⇒ находим минимальное число монет по 3 копейки, сумма которых делится на 5:  это 3*5=15. Максимальное число, которое меньше 1000, делится на 3 и  оканчивается на 0 или 5: 990.   ⇒

990:15=66.

Ответ:

66 способами можно набрать монетами по 3 и 5 копеек 10 рублей.

Answer 2

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

Изначально все элементы массива dp устанавливаются равными нулю. Затем заполним его значениями, начиная с dp[3] и dp[5] (поскольку это минимальные значения сумм, которые можно набрать с использованием соответствующих монет). Для каждого i большего или равного 5, значение dp[i] будет равно сумме dp[i-3] и dp[i-5], поскольку мы можем получить сумму i путем добавления 3 или 5 копеек к сумме i-3 или i-5 соответственно.

В итоге, значение dp[10] будет содержать количество способов набрать сумму 10 рублей с использованием монет по 3 и 5 копеек.

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

pythonCopy code
def count_ways(n):
    dp = [0] * (n + 1)
    dp[3] = 1
    dp[5] = 1

    for i in range(6, n + 1):
        dp[i] = dp[i - 3] + dp[i - 5]

    return dp[n]

ways = count_ways(10)
print(ways)

Результат выполнения этого кода будет равен количеству способов набрать сумму 10 рублей с использованием монет по 3 и 5 копеек.