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

Решение.

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

Для решения таких задач удобнее всего использовать метод «обратного хода» — пойдём от конечного числа $79$ к исходному числу $7$. При этом команды заменяются на противоположные:
1. Извлеки квадратный корень ($\sqrt{x}$);
2. Прибавь 2 ($x + 2$).

Шаг 1. Посмотрим на число $79$. Извлечь корень нацело нельзя. Значит, на последнем этапе мы могли получить его только вычитанием двойки. Применим обратную операцию: $79 + 2 = 81$. (Команда 2)

Шаг 2. Число $81$ является полным квадратом ($9^2$). Попробуем извлечь корень: $\sqrt{81} = 9$. (Команда 1)

Шаг 3. Теперь у нас число $9$. Оно также является полным квадратом ($3^2$). Попробуем извлечь корень: $\sqrt{9} = 3$. (Команда 1)

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

Проверим полученную последовательность обратных действий: $79 \xrightarrow{+2} 81 \xrightarrow{\sqrt{x}} 9 \xrightarrow{\sqrt{x}} 3 \xrightarrow{+2} 5 \xrightarrow{+2} 7$.
Всего получилось 5 действий. Теперь запишем их в прямом порядке (от $7$ к $79$) и заменим на номера исходных команд:

1. $7 - 2 = 5$ (Команда 2)
2. $5 - 2 = 3$ (Команда 2)
3. $3^2 = 9$ (Команда 1)
4. $9^2 = 81$ (Команда 1)
5. $81 - 2 = 79$ (Команда 2)

Последовательность команд: 22112.

Ответ: 22112

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