Question

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

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

Программа для Вычислителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21, при этом траектория вычислений содержит число 10 и не содержит числа 16?

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

Accepted Answer

14

Answer

Идея решения: разбить путь от 1 к 21 на три этапа (1 → 10 → 15 → 21), избегая числа 16, и подсчитать количество программ для каждого этапа независимо.

Обозначим:
- $R(n)$ — количество программ, преобразующих 1 в $n$;
- $P(n)$ — количество программ, преобразующих 10 в $n$;
- $F(n)$ — количество программ, преобразующих 17 в $n$.

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

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

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

$$R(1) = 1$$
$$R(2) = R(1) + R(1) = 2$$
$$R(3) = R(2) = 2$$
$$R(4) = R(2) + R(3) = 4$$
$$R(5) = R(4) = 4$$
$$R(6) = R(3) + R(5) = 6$$
$$R(7) = R(6) = 6$$
$$R(8) = R(4) + R(7) = 10$$
$$R(9) = R(8) = 10$$
$$R(10) = R(5) + R(9) = 14$$

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

Поскольку все числа от 10 до 15 нечётны (кроме 10 и 12, 14), и мы не можем пройти через 16, остаётся только прибавлять 1:

$$P(10) = 1$$
$$P(11) = P(10) = 1$$
$$P(12) = P(6) + P(11) = 1 + 1 = 2$$

Однако, учитывая ограничение (не проходить через 16), от 10 до 15 можно идти только через прибавление 1:

$$P(10) = P(11) = P(12) = P(13) = P(14) = P(15) = 1$$

**Вычисляем $F(n)$ для $n$ от 17 до 21:**

От 17 к 21 можно идти только прибавлением 1 (умножение на 2 даст числа ≥ 34):

$$F(17) = F(18) = F(19) = F(20) = F(21) = 1$$

Общее количество программ:

$$R(10) 	imes P(15) 	imes F(21) = 14 	imes 1 	imes 1 = 14$$

**Альтернативное решение на Python:**

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

print(f(1, 10) * f(10, 21))
```

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