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

Решение.

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

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

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

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

Шаг 3. Число $9$ также делится на $3$. Снова используем деление:
$9 / 3 = 3$. (Это соответствует команде 2 в прямом порядке).
Текущая последовательность команд (с конца): 2, 2, 1.

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

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

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

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

Ответ: 11221

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