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

Решение.

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

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

Попробуем восстановить путь от $120$ к $2$ за $5$ шагов:

Шаг 1. Число $120$ делится на $4$. Попробуем применить обратную команду №1:
$120 : 4 = 30$. (Это соответствует команде №1 в прямом порядке).

Шаг 2. Число $30$ не делится на $4$. Значит, мы можем применить только обратную команду №2:
$30 + 1 = 31$. (Это соответствует команде №2 в прямом порядке).

Шаг 3. Число $31$ не делится на $4$. Снова применяем обратную команду №2:
$31 + 1 = 32$. (Это соответствует команде №2 в прямом порядке).

Шаг 4. Число $32$ делится на $4$. Применяем обратную команду №1:
$32 : 4 = 8$. (Это соответствует команде №1 в прямом порядке).

Шаг 5. Число $8$ делится на $4$. Применяем обратную команду №1:
$8 : 4 = 2$. (Это соответствует команде №1 в прямом порядке).

Мы пришли к исходному числу $2$ за $5$ шагов. Теперь запишем команды в прямом порядке (от числа $2$ к числу $120$), учитывая, что мы шли с конца:

1. $2 \cdot 4 = 8$ (команда 1)
2. $8 \cdot 4 = 32$ (команда 1)
3. $32 - 1 = 31$ (команда 2)
4. $31 - 1 = 30$ (команда 2)
5. $30 \cdot 4 = 120$ (команда 1)

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

Ответ: 11221

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