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

Решение.

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

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

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

Шаг 2. Число $35$ не делится на $3$. Снова применяем обратную команду №2:
$35 - 2 = 33$. (Команда №2).

Шаг 3. Число $33$ делится на $3$. Попробуем применить обратную команду №1:
$33 : 3 = 11$. (Команда №1).

Шаг 4. Число $11$ не делится на $3$. Применяем обратную команду №2:
$11 - 2 = 9$. (Команда №2).

Шаг 5. Число $9$ делится на $3$. Применяем обратную команду №1:
$9 : 3 = 3$. (Команда №1).
Мы пришли к исходному числу $3$. Всего получилось 5 действий.

Теперь запишем команды в прямом порядке (от $3$ к $37$):
1. $3 \cdot 3 = 9$ (команда 1)
2. $9 + 2 = 11$ (команда 2)
3. $11 \cdot 3 = 33$ (команда 1)
4. $33 + 2 = 35$ (команда 2)
5. $35 + 2 = 37$ (команда 2)

Последовательность номеров команд: $12122$.

Ответ: 12122

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