Question

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

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

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Accepted Answer

112

Answer

Идея решения: найти количество программ, ведущих из 3 в 14 через обязательное промежуточное число 9, как произведение количества путей 3 → 9 и 9 → 14.

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

Рекуррентное соотношение:
$$R(n) = R(n - 1) + R(n - 2) + \begin{cases} R(n / 3) & 	ext{если } 3 \mid n \ 0 & 	ext{иначе} \end{cases}$$

Это следует из того, что в число $n$ можно попасть тремя способами:
- из $n - 1$ командой «Прибавить 1»;
- из $n - 2$ командой «Прибавить 2»;
- из $n / 3$ командой «Умножить на 3» (если $n$ делится на 3).

Вычислим значения:

| $n$ | $R(n)$ |
|---|---|
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 3 |
| 7 | 5 |
| 8 | 8 |
| 9 | 14 |
| 10 | 14 |
| 11 | 28 |
| 12 | 42 |
| 13 | 70 |
| 14 | 112 |

Количество программ, проходящих через 9:
$$R(3 	o 9) 	imes R(9 	o 14) = 14 	imes 8 = 112$$

Проверка через рекурсивный перебор:

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

print(f(3, 9) * f(9, 14))
```

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