Question

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

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

Программа — это последовательность команд. Траектория вычислений — это последовательность результатов выполнения всех команд программы.

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

Accepted Answer

324

Answer

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

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

Для каждого числа $n$ в диапазоне от $a$ до $b$ верно рекуррентное соотношение:
$$R(a, n) = R(a, n-1) + R(a, n-3) + R(a, n/3)$$
где третий член учитывается только если $n$ кратно 3.

**Этап 1: от 4 к 10**

| $n$ | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|
| $R(4, n)$ | 1 | 1 | 1 | 2 | 3 | 4 | 6 |

$R(4, 10) = 6$

**Этап 2: от 10 к 17**

| $n$ | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|
| $R(10, n)$ | 1 | 1 | 1 | 2 | 3 | 4 | 6 | 9 |

$R(10, 17) = 9$

**Этап 3: от 17 к 23**

| $n$ | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|
| $R(17, n)$ | 1 | 1 | 1 | 2 | 3 | 4 | 6 |

$R(17, 23) = 6$

Итоговое количество программ:
$$R(4, 10) 	imes R(10, 17) 	imes R(17, 23) = 6 	imes 9 	imes 6 = 324$$

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

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

print(f(4, 10) * f(10, 17) * f(17, 23))
```

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