Question

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

1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 2.

Сколько существует программ, для которых при исходном числе 4 результатом является число 13 и при этом траектория вычислений содержит число 11?

Accepted Answer

50

Answer

Идея решения: разбить задачу на два этапа — найти количество программ из 4 в 11, затем из 11 в 13, и перемножить результаты.

Обозначим $R(n)$ — количество программ, преобразующих 4 в число $n$, и $P(n)$ — количество программ, преобразующих 11 в число $n$.

Для вычисления $R(n)$ и $P(n)$ используем рекуррентные соотношения:
- Если $n$ нечётно: $R(n) = R(n-1) + R(n-2)$ (число можно получить прибавлением 1 или 2).
- Если $n$ чётно: $R(n) = R(n-1) + R(n-2) + R(n/2)$ (добавляется способ через умножение на 2).

Аналогично для $P(n)$.

**Вычисляем $R(n)$ от 4 до 11:**

- $R(4) = 1$ (начальное значение)
- $R(5) = R(4) = 1$
- $R(6) = R(4) + R(5) = 1 + 1 = 2$
- $R(7) = R(5) + R(6) = 1 + 2 = 3$
- $R(8) = R(6) + R(7) + R(4) = 2 + 3 + 1 = 6$
- $R(9) = R(7) + R(8) = 3 + 6 = 9$
- $R(10) = R(8) + R(9) + R(5) = 6 + 9 + 1 = 16$
- $R(11) = R(9) + R(10) = 9 + 16 = 25$

**Вычисляем $P(n)$ от 11 до 13:**

- $P(11) = 1$ (начальное значение)
- $P(12) = P(11) = 1$
- $P(13) = P(11) + P(12) = 1 + 1 = 2$

Количество программ, удовлетворяющих условию: $R(11) 	imes P(13) = 25 	imes 2 = 50$.

```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 * 2, y)

print(f(4, 11) * f(11, 13))
```

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