Question

Исполнитель Вычитатель преобразует число на экране с помощью двух команд:

1. Вычти 2
2. Вычти 5

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

Accepted Answer

23

Answer

Идея решения: поскольку вычитание коммутативно, порядок команд не влияет на результат, поэтому нужно найти все комбинации команд, дающие разность 20, и подсчитать количество способов их расставить.

Обозначим количество команд первого типа (вычти 2) как $a$, второго типа (вычти 5) как $b$. Требуется:
$$2a + 5b = 20$$

Так как $a, b \geq 0$, переберём возможные значения $b$:

- $b = 0$: $2a = 20 \Rightarrow a = 10$. Набор: десять команд типа 1. Количество расстановок: $\binom{10}{10} = 1$.
- $b = 1$: $2a = 15$ — не целое решение.
- $b = 2$: $2a = 10 \Rightarrow a = 5$. Набор: пять команд типа 1 и две команды типа 2. Количество расстановок: $\binom{7}{2} = 21$.
- $b = 3$: $2a = 5$ — не целое решение.
- $b = 4$: $2a = 0 \Rightarrow a = 0$. Набор: четыре команды типа 2. Количество расстановок: $\binom{4}{4} = 1$.

Общее количество программ: $1 + 21 + 1 = 23$.

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

```python
def f(x, y):
    if x < y:
        return 0
    if x == y:
        return 1
    return f(x - 2, y) + f(x - 5, y)

print(f(22, 2))
```

Функция $f(x, y)$ подсчитывает количество способов преобразовать $x$ в $y$. Если $x < y$, решений нет. Если $x = y$, найдено одно решение. Иначе рекурсивно суммируются результаты применения обеих команд.

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