Задание №5 — Алгоритмы и программирование

Решение.

Нам необходимо составить алгоритм для исполнителя «Калькулятор», который превратит число $1$ в число $7$ за ограниченное количество шагов (не более 5 команд). У нас есть две команды:
1. умножь на 3 (обозначим как $\times 3$);
2. вычти 5 (обозначим как $- 5$).

Будем строить цепочку вычислений пошагово, стараясь прийти к числу $7$:

Шаг 1. Начнём с числа $1$. Если мы применим команду 2 ($1 - 5 = -4$), мы получим отрицательное число, из которого сложно будет быстро прийти к $7$. Применим команду 1:
$1 \times 3 = 3$ (команда 1).

Шаг 2. Из числа $3$ снова применим команду 1, чтобы увеличить значение:
$3 \times 3 = 9$ (команда 1).

Шаг 3. Теперь мы получили число $9$. Нам нужно получить $7$. Если мы вычтем 5, то получим $4$. Попробуем этот путь:
$9 - 5 = 4$ (команда 2).

Шаг 4. Из числа $4$ попробуем снова увеличить значение, применив команду 1:
$4 \times 3 = 12$ (команда 1).

Шаг 5. Теперь у нас есть число $12$. Чтобы из него получить итоговое число $7$, нужно вычесть $5$:
$12 - 5 = 7$ (команда 2).

Проверим полученную последовательность команд: 1, 1, 2, 1, 2.
Вычисления: $1 \xrightarrow{1} 3 \xrightarrow{1} 9 \xrightarrow{2} 4 \xrightarrow{1} 12 \xrightarrow{2} 7$.
Алгоритм содержит ровно 5 команд, что соответствует условию задачи.

Ответ: 11212

Источник: ФИПИ