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

Решение.

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

Самый эффективный способ решения таких задач — метод «обратного хода». Будем идти от конечного числа $25$ к начальному числу $2$. При этом команды заменяются на противоположные: вместо «умножить на $3$» будем «делить на $3$» (если число делится без остатка), а вместо «прибавить $1$» будем «вычитать $1$».

Шаг 1. Число $25$ не делится на $3$. Значит, на последнем этапе мы могли только прибавить единицу.
Выполняем обратное действие: $25 - 1 = 24$. (Команда 2)

Шаг 2. Число $24$ делится на $3$. Попробуем деление, так как оно быстрее уменьшает число:
$24 : 3 = 8$. (Команда 1)

Шаг 3. Число $8$ не делится на $3$. Вычитаем единицу:
$8 - 1 = 7$. (Команда 2)

Шаг 4. Число $7$ не делится на $3$. Вычитаем единицу:
$7 - 1 = 6$. (Команда 2)

Шаг 5. Число $6$ делится на $3$. Пробуем деление:
$6 : 3 = 2$. (Команда 1)

Мы пришли к исходному числу $2$. Теперь запишем команды в обратном порядке (от начала к концу):
1. Число $2$, применяем команду 1: $2 \cdot 3 = 6$
2. Число $6$, применяем команду 2: $6 + 1 = 7$
3. Число $7$, применяем команду 2: $7 + 1 = 8$
4. Число $8$, применяем команду 1: $8 \cdot 3 = 24$
5. Число $24$, применяем команду 2: $24 + 1 = 25$

Последовательность команд: 12212. Проверим количество команд: их ровно $5$, что соответствует условию задачи.

Ответ: 12212

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