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

Решение.

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

Попробуем действовать методом "от обратного" — будем идти от конечного числа $25$ к начальному числу $4$. При этом команды будут обратными:
1. прибавь 1 (вместо "вычти 1")
2. раздели на 3 (вместо "умножь на 3", выполняется только если число делится на 3 без остатка)

Шаг 1. Число $25$ не делится на $3$. Значит, единственно возможный обратный шаг — прибавить $1$.
$25 + 1 = 26$ (это была бы команда 1 в прямом порядке).

Шаг 2. Число $26$ не делится на $3$. Снова прибавляем $1$.
$26 + 1 = 27$ (это была бы команда 1 в прямом порядке).

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

Шаг 4. Число $9$ делится на $3$. Попробуем разделить.
$9 : 3 = 3$ (это была бы команда 2 в прямом порядке). Но нам нужно прийти к числу $4$. Если мы получили $3$, то следующим шагом (прибавлением единицы) мы как раз получим $4$.
$3 + 1 = 4$ (это была бы команда 1 в прямом порядке).

Теперь запишем полученные команды в обратном порядке (от числа $4$ к числу $25$):
1. Начнём с $4$. Применим команду 1: $4 - 1 = 3$.
2. Применим команду 2: $3 \cdot 3 = 9$.
3. Применим команду 2: $9 \cdot 3 = 27$.
4. Применим команду 1: $27 - 1 = 26$.
5. Применим команду 1: $26 - 1 = 25$.

Проверим количество команд: их ровно 5, что соответствует условию задачи.
Последовательность номеров команд: 1 (вычти 1), 2 (умножь на 3), 2 (умножь на 3), 1 (вычти 1), 1 (вычти 1).

Ответ: 12211

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