Question

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

1. **Прибавь 2** — увеличивает число на 2.
2. **Умножь на 2** — увеличивает число в два раза.

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

Траектория вычислений — последовательность всех промежуточных результатов. Например, для программы с кодами команд 1, 2, 1 при исходном числе 3 траектория: 5, 10, 12.

Accepted Answer

96

Answer

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

Определим рекурсивную функцию $f(x, y)$, которая подсчитывает количество способов преобразовать число $x$ в число $y$ с помощью доступных команд.

Базовые случаи:
- Если $x > y$, то преобразование невозможно: $f(x, y) = 0$.
- Если $x = y$, то существует ровно один способ (не выполнять команды): $f(x, y) = 1$.

Рекурсивный случай: из числа $x$ можно перейти в $x + 2$ (команда 1) или в $2x$ (команда 2), поэтому:
$$f(x, y) = f(x + 2, y) + f(x \cdot 2, y)$$

Общее количество программ, проходящих через 18:
$$f(1, 18) \cdot f(18, 52)$$

Реализация на Python:

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

print(f(1, 18) * f(18, 52))
```

Реализация на PascalABC:

```pascal
var n: integer;

function F(n: integer; m: integer): integer;
begin
    if n > m then
        F := 0
    else if n = m then
        F := 1
    else
        F := F(n + 2, m) + F(n * 2, m)
end;

begin
    writeln(F(1, 18) * F(18, 52))
end.
```

Оба варианта выдают результат 96.

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