Question

Исполнитель преобразует число на экране. Доступны три команды:

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

Программа — это последовательность команд. Найти количество программ, которые преобразуют исходное число 1 в число 35, при условии, что траектория вычислений обязательно проходит через число 7.

Accepted Answer

381662184

Answer

Идея решения: разбить задачу на два независимых этапа — путь от 1 к 7 и путь от 7 к 35, затем перемножить количества программ для каждого этапа.

Обозначим через $f(a, b)$ количество программ, преобразующих число $a$ в число $b$ с помощью трёх команд (прибавление 1, 2 или 3).

Рекуррентное соотношение:
- Если $a > b$: $f(a, b) = 0$ (невозможно достичь меньшего числа).
- Если $a = b$: $f(a, b) = 1$ (пустая программа).
- Если $a < b$: $f(a, b) = f(a+1, b) + f(a+2, b) + f(a+3, b)$ (применяем одну из трёх команд и рекурсивно считаем пути из нового состояния).

Поскольку траектория должна пройти через 7, общее количество программ равно произведению:
$$f(1, 7) 	imes f(7, 35)$$

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

result = f(1, 7) * f(7, 35)
print(result)
```

Вычисляем:
- $f(1, 7)$ — количество способов добавить в сумме 6 единиц, используя команды +1, +2, +3.
- $f(7, 35)$ — количество способов добавить в сумме 28 единиц.

Произведение даёт искомое количество программ.

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