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

Решение.

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

Для решения таких задач удобно рассуждать «с конца» — от итогового числа $26$ к исходному числу $5$. При движении в обратную сторону команды меняются на противоположные:
1. прибавь 1
2. раздели на 3 (применимо только к числам, кратным 3)

Шаг 1. Начнём с числа $26$. Оно не делится на $3$, поэтому единственный возможный обратный ход — прибавить $1$.
$26 + 1 = 27$ (Команда 1 в обратном порядке).
Теперь у нас есть число $27$.

Шаг 2. Число $27$ делится на $3$. Попробуем применить деление, так как это быстрее приведёт нас к маленькому числу $5$.
$27 : 3 = 9$ (Команда 2 в обратном порядке).
Теперь у нас есть число $9$.

Шаг 3. Число $9$ также делится на $3$. Применим деление ещё раз.
$9 : 3 = 3$ (Команда 2 в обратном порядке).
Теперь у нас есть число $3$.

Шаг 4. Нам нужно получить число $5$. Из числа $3$ мы можем только прибавлять единицы.
$3 + 1 = 4$ (Команда 1 в обратном порядке).
Теперь у нас есть число $4$.

Шаг 5. Последний шаг:
$4 + 1 = 5$ (Команда 1 в обратном порядке).
Мы пришли к исходному числу $5$.

Проверка. Запишем полученные команды в прямом порядке (от $5$ к $26$):
1. (Команда 1): $5 - 1 = 4$
2. (Команда 1): $4 - 1 = 3$
3. (Команда 2): $3 \cdot 3 = 9$
4. (Команда 2): $9 \cdot 3 = 27$
5. (Команда 1): $27 - 1 = 26$
Алгоритм: 11221. Количество команд — 5, что соответствует условию задачи.

Ответ: 11221

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