Есть число S. Сколькими способами можно набрать эт...

Ниже разберём классическую задачу о количестве способов набрать сумму $S$ с помощью монет номиналов 1, 2 и 5 рублей (при этом порядок монет не имеет значения).

---

1. Математическая формулировка

Ищем количество неотрицательных целочисленных решений уравнения

$$x \;+\; 2y \;+\; 5z \;=\; S,$$

где

• $x$ — количество монет по 1 рублю,
• $y$ — количество монет по 2 рубля,
• $z$ — количество монет по 5 рублей.

Так как $x, y, z \ge 0$, нужно перебрать все возможные значения $z$ (от 0 до $\lfloor S/5 \rfloor$), а для каждого зафиксированного $z$ посмотреть, сколькими способами можно добрать остаток $S - 5z$ монетами в 1 и 2 рубля.

Подсчёт числа решений для $x + 2y = N$

Если мы обозначим $N = S - 5z$, то количество решений для

$$x + 2y = N, \quad x, y \ge 0,$$

равно $1 + \lfloor N/2 \rfloor$.
Почему так? Потому что:

• $y$ может принимать все значения от 0 до $\lfloor N/2 \rfloor$.
• Для каждого $y$ значение $x = N - 2y$ однозначно определяется и неотрицательно.

Итоговая формула

Итого, полное число способов набрать сумму $S$ монетами 1, 2 и 5 рублей (без учёта порядка) даёт сумма:

$$\sum_{z=0}^{\lfloor S/5 \rfloor} \Bigl(1 + \bigl\lfloor \tfrac{S - 5z}{2} \bigr\rfloor \Bigr).$$

Другими словами, мы перебираем $z = 0, 1, 2, \dots, \lfloor S/5 \rfloor$. Для каждого $z$ считаем, сколько есть способов составить $S - 5z$ монетами 1 и 2 рубля, и складываем результаты.

---

2. Динамический (программный) подход

Ещё один популярный способ — метод динамического программирования. Пусть $dp[n]$ обозначает количество способов набрать сумму $n$ монетами $\{1,2,5\}$ (при этом порядок не важен). Тогда:

1. Инициализируем массив $dp$ длиной $S+1$ нулями.
2. Задаём базовое условие: $dp[0] = 1$. (Один способ набрать 0 — не взять ни одной монеты.)
3. По очереди «проходим» по каждому номиналу монеты и обновляем $dp$.
   • Сначала для монеты 1 рубль: $$\text{для } n \text{ от } 1 \text{ до } S:\quad dp[n] \;{+}{=}\; dp[n - 1].$$ Здесь $dp[n - 1]$ уже содержит число способов набрать сумму $n-1$ (поскольку раньше мы рассмотрели все более «мелкие» суммы).
   • Затем для монеты 2 рубля: $$\text{для } n \text{ от } 2 \text{ до } S:\quad dp[n] \;{+}{=}\; dp[n - 2].$$
   • И наконец для монеты 5 рублей: $$\text{для } n \text{ от } 5 \text{ до } S:\quad dp[n] \;{+}{=}\; dp[n - 5].$$

После обработки всех трёх номиналов в $dp[S]$ окажется количество искомых способов.

Ниже приведён условный псевдокод:

text
function countWays(S):
    dp = массив из (S+1) элементов, заполненный нулями
    dp[0] = 1  # База: 1 способ набрать 0

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

    return dp[S]

После выполнения этого алгоритма dp[S] вернёт то же самое число, что и формула выше, но часто такой код проще прямо реализовать в программе.

---

3. Пример вычисления вручную

Для иллюстрации возьмём небольшую сумму, скажем, $S = 6$:

1. Через формулу
   Нужно перебрать $z = 0$ и $z = 1$, потому что $\lfloor 6 / 5 \rfloor = 1$.

   • При $z = 0$, сумма $S - 5z = 6$. Способов набрать 6 монетами 1 и 2 рублей: $$1 + \lfloor 6 / 2 \rfloor = 1 + 3 = 4.$$ (Это варианты: $6 = 6\cdot1$; $6 = 4\cdot1 + 1\cdot2$; $6 = 2\cdot1 + 2\cdot2$; $6 = 3\cdot2$.)
   • При $z = 1$, сумма $S - 5z = 1$. Способов набрать 1 монетами 1 и 2 рублей: $$1 + \lfloor 1 / 2 \rfloor = 1 + 0 = 1.$$ (Это вариант: $1 = 1\cdot1$.)

   Итого: $4 + 1 = 5$ способов.

2. Через динамику

   • Изначально dp[0] = 1, остальные dp[1..6] = 0.
   • Сначала учтём монету в 1 рубль:
     • dp[1] += dp[0] → dp[1] = 1
     • dp[2] += dp[1] → dp[2] = 1
     • dp[3] += dp[2] → dp[3] = 1
     • dp[4] += dp[3] → dp[4] = 1
     • dp[5] += dp[4] → dp[5] = 1
     • dp[6] += dp[5] → dp[6] = 1
       Теперь dp = [1,1,1,1,1,1,1].
   • Учитываем монету в 2 рубля:
     • для n от 2 до 6:
       • dp[2] += dp[0] → dp[2] = 2 (т.е. 2 способа набрать 2: (1+1) или (2))
       • dp[3] += dp[1] → dp[3] = 2
       • dp[4] += dp[2] → dp[4] = 1 + 2 = 3
       • dp[5] += dp[3] → dp[5] = 1 + 2 = 3
       • dp[6] += dp[4] → dp[6] = 1 + 3 = 4
   • Учитываем монету в 5 рублей:
     • для n от 5 до 6:
       • dp[5] += dp[0] → dp[5] = 3 + 1 = 4
       • dp[6] += dp[1] → dp[6] = 4 + 1 = 5

   В итоге dp[6] = 5.

Таким образом, оба подхода дают ответ $5$.

---

4. Резюме

Чтобы найти, сколькими способами можно набрать сумму $S$ монетами в 1, 2 и 5 рублей (без учёта порядка), можно использовать:

1. Явную суммирующую формулу:

   $$\text{Количество способов} \;=\; \sum_{z=0}^{\lfloor S/5 \rfloor} \Bigl(1 + \bigl\lfloor \tfrac{S - 5z}{2} \bigr\rfloor \Bigr).$$

2. Динамическое программирование, перебирая номиналы $\{1,2,5\}$ и заполняя массив $dp$, где $dp[n]$ — количество способов получить $n$.
   В конце в dp[S] будет искомое число.

Оба способа эквивалентны по результату; выбор метода зависит от того, удобнее ли вам «быстрая» формула суммирования или универсальный программный подход.

Ниже приведён пример кода на Python, который вычисляет количество способов (без учёта порядка) набрать сумму S монетами номиналов 1, 2 и 5 рублей с помощью динамического программирования:

python
def count_ways(S):
    # dp[n] будет хранить количество способов набрать сумму n
    dp = [0] * (S + 1)
    
    # Для суммы 0 есть ровно 1 способ (не использовать монеты)
    dp[0] = 1

    # Последовательно "добавляем" каждый из доступных номиналов
    for coin in [1, 2, 5]:
        for n in range(coin, S + 1):
            dp[n] += dp[n - coin]

    return dp[S]

# Пример использования
if __name__ == "__main__":
    S = 10
    print(f"Количество способов набрать {S} рублей: {count_ways(S)}")

Как это работает:

1. Мы создаём список dp длиной S + 1, где каждый элемент изначально равен 0.
2. Устанавливаем dp[0] = 1, поскольку единственный способ набрать сумму 0 — не брать ни одной монеты.
3. Внешний цикл итерируется по номиналам монет (1, 2, 5).
4. Внутренний цикл идёт по всем суммам от текущего номинала до S. Для каждой суммы n, мы обновляем dp[n], прибавляя к нему число способов набрать n - coin.

В итоге, когда перебраны все монеты, в dp[S] будет записано количество уникальных комбинаций (без учёта порядка монет), дающих итоговую сумму S.