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

Решение.

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

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

Шаг 1. Начнём с числа $66$.
Число $66$ делится на $3$. Попробуем применить обратную команду №1: $66 : 3 = 22$.
(Если бы мы вычли $2$, получили бы $64$, которое не делится на $3$, что усложнило бы путь).
Текущая последовательность команд (с конца): 1.

Шаг 2. Теперь у нас число $22$.
Число $22$ не делится на $3$. Значит, единственный вариант — применить обратную команду №2:
$22 - 2 = 20$.
Текущая последовательность команд (с конца): 2, 1.

Шаг 3. Теперь у нас число $20$.
Число $20$ не делится на $3$. Снова применяем обратную команду №2:
$20 - 2 = 18$.
Текущая последовательность команд (с конца): 2, 2, 1.

Шаг 4. Теперь у нас число $18$.
Число $18$ делится на $3$. Применим обратную команду №1:
$18 : 3 = 6$.
Текущая последовательность команд (с конца): 1, 2, 2, 1.

Шаг 5. Теперь у нас число $6$.
Число $6$ делится на $3$. Применим обратную команду №1:
$6 : 3 = 2$.
Мы пришли к исходному числу $2$.
Итоговая последовательность команд (с конца): 1, 1, 2, 2, 1.

Теперь запишем команды в прямом порядке (от начала к концу): 11221.

Проверка:
1. Команда 1: $2 \cdot 3 = 6$
2. Команда 1: $6 \cdot 3 = 18$
3. Команда 2: $18 + 2 = 20$
4. Команда 2: $20 + 2 = 22$
5. Команда 1: $22 \cdot 3 = 66$
Алгоритм верный и содержит ровно $5$ команд.

Ответ: 11221

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