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

Решение.

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

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

Шаг 1. Начнём с числа $120$. Оно делится на 4. Проверим деление: $120 : 4 = 30$. Это значительно приближает нас к начальному числу $2$.
Команда (обратная): разделить на 4. (Соответствует прямой команде 1).

Шаг 2. Теперь у нас число $30$. Оно не делится на 4 без остатка ($30 : 4 = 7,5$). Значит, единственный путь — прибавить 4.
$30 + 4 = 34$.
Команда (обратная): прибавить 4. (Соответствует прямой команде 2).

Шаг 3. Число $34$ также не делится на 4. Прибавляем 4 еще раз:
$34 + 4 = 38$.
Команда (обратная): прибавить 4. (Соответствует прямой команде 2).

Видим, что мы отдаляемся от цели $2$. Попробуем изменить стратегию на первом шаге. Если мы не будем делить $120$ на 4 сразу, а сначала прибавим 4, число станет еще больше. Значит, первый шаг был верным. Попробуем рассмотреть прямую последовательность команд, зная, что в конце должно быть умножение на 4 или вычитание 4.

Проверим последовательность, указанную в условии как правильную: 11122.
1. Число $2$. Команда 1: $2 \cdot 4 = 8$.
2. Число $8$. Команда 1: $8 \cdot 4 = 32$.
3. Число $32$. Команда 1: $32 \cdot 4 = 128$.
4. Число $128$. Команда 2: $128 - 4 = 124$.
5. Число $124$. Команда 2: $124 - 4 = 120$.

Проверка расчётов:
$((2 \cdot 4) \cdot 4) \cdot 4 - 4 - 4 = 120$
$8 \cdot 4 \cdot 4 - 4 - 4 = 120$
$32 \cdot 4 - 4 - 4 = 120$
$128 - 4 - 4 = 120$
$124 - 4 = 120$.
Алгоритм состоит из 5 команд и приводит к верному результату.

Ответ: 11122

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