Question

У исполнителя Удвоитель две команды, которым присвоены номера:

1. прибавь 1
2. прибавь 4

Первая команда увеличивает число на экране на 1, вторая — на 4. Программа для Удвоителя — это последовательность команд. Сколько существует программ, которые число 3 преобразуют в число 15?

Accepted Answer

26

Answer

Идея решения: найти количество способов представить разность 15 − 3 = 12 в виде суммы единиц и четвёрок, учитывая все возможные порядки команд.

Нужно увеличить число на 12. Обозначим количество команд первого типа (прибавь 1) как $a$, а количество команд второго типа (прибавь 4) как $b$. Тогда:

$$a + 4b = 12$$

Переберём все неотрицательные решения:
- $b = 0$: $a = 12$ (12 единиц)
- $b = 1$: $a = 8$ (8 единиц и 1 четвёрка)
- $b = 2$: $a = 4$ (4 единицы и 2 четвёрки)
- $b = 3$: $a = 0$ (3 четвёрки)

Для каждого решения количество различных программ равно числу перестановок с повторениями:

$$P(a, b) = \frac{(a + b)!}{a! \cdot b!}$$

Вычислим для каждого случая:
- $b = 0$: $\frac{12!}{12! \cdot 0!} = 1$
- $b = 1$: $\frac{9!}{8! \cdot 1!} = 9$
- $b = 2$: $\frac{6!}{4! \cdot 2!} = \frac{720}{24 \cdot 2} = 15$
- $b = 3$: $\frac{3!}{0! \cdot 3!} = 1$

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

Проверка рекурсивным методом:

```python
def f(x, y):
    if x == y:
        return 1
    if x > y:
        return 0
    return f(x + 1, y) + f(x + 4, y)

print(f(3, 15))
```

Функция $f(x, y)$ подсчитывает количество способов достичь числа $y$ из числа $x$. На каждом шаге либо прибавляем 1, либо прибавляем 4, пока не достигнем целевого значения.

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