Question

Исполнитель Май4 преобразует число на экране с помощью трёх команд:

1. Прибавь 1
2. Прибавь 2
3. Прибавь 4

Программа — это последовательность команд. Сколько существует программ, которые число 21 преобразуют в число 30?

Accepted Answer

96

Answer

Идея решения: найти все способы представить разность 30 − 21 = 9 в виде суммы чисел 1, 2 и 4, а затем для каждого представления подсчитать количество различных порядков команд (перестановки с повторениями).

Нужно увеличить число на 9. Обозначим количество команд типа 1, 2, 4 как $a$, $b$, $c$ соответственно. Тогда:
$$a + 2b + 4c = 9$$

Переберём все неотрицательные целые решения этого уравнения:

- $c = 0$: $a + 2b = 9$
  - $b = 0$: $a = 9$ → набор из 9 единиц → 1 перестановка
  - $b = 1$: $a = 7$ → набор (1,1,1,1,1,1,1,2) → $\frac{8!}{7! \cdot 1!} = 8$ перестановок
  - $b = 2$: $a = 5$ → набор (1,1,1,1,1,2,2) → $\frac{7!}{5! \cdot 2!} = 21$ перестановка
  - $b = 3$: $a = 3$ → набор (1,1,1,2,2,2) → $\frac{6!}{3! \cdot 3!} = 20$ перестановок
  - $b = 4$: $a = 1$ → набор (1,2,2,2,2) → $\frac{5!}{1! \cdot 4!} = 5$ перестановок

- $c = 1$: $a + 2b = 5$
  - $b = 0$: $a = 5$ → набор (1,1,1,1,1,4) → $\frac{6!}{5! \cdot 1!} = 6$ перестановок
  - $b = 1$: $a = 3$ → набор (1,1,1,2,4) → $\frac{5!}{3! \cdot 1! \cdot 1!} = 20$ перестановок
  - $b = 2$: $a = 1$ → набор (1,2,2,4) → $\frac{4!}{1! \cdot 2! \cdot 1!} = 12$ перестановок

- $c = 2$: $a + 2b = 1$
  - $b = 0$: $a = 1$ → набор (1,4,4) → $\frac{3!}{1! \cdot 2!} = 3$ перестановки

Суммируем все перестановки:
$$1 + 8 + 21 + 20 + 5 + 6 + 20 + 12 + 3 = 96$$

Проверка через рекурсию:

```python
def count_programs(current, target):
    if current == target:
        return 1
    if current > target:
        return 0
    return (count_programs(current + 1, target) +
            count_programs(current + 2, target) +
            count_programs(current + 4, target))

print(count_programs(21, 30))
```

Задание №23Алгоритмы и исполнителиЕГЭ по информатике