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

Решение.

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

Для решения таких задач удобнее идти от конечного результата к начальному числу, используя обратные операции. Обратной операцией для возведения в квадрат является извлечение квадратного корня ($\sqrt{x}$), а для вычитания $2$ — прибавление $2$ ($x + 2$).

Шаг 1. Посмотрим на конечное число $142$. Из него нельзя извлечь целый квадратный корень. Значит, последней командой (шаг 5) точно было вычитание $2$.
Выполним обратное действие: $142 + 2 = 144$.
Это была команда №2.

Шаг 2. Теперь у нас число $144$. Заметим, что $144 = 12^2$. Это отличный кандидат для команды возведения в квадрат. Проверим этот путь.
Выполним обратное действие: $\sqrt{144} = 12$.
Это была команда №1.

Шаг 3. Теперь у нас число $12$. Из него нельзя извлечь целый корень ($\sqrt{12}$ — не целое число). Значит, на этом этапе снова было вычитание $2$.
Выполним обратное действие: $12 + 2 = 14$.
Это была команда №2.

Шаг 4. Теперь у нас число $14$. Из него также нельзя извлечь целый корень. Снова применяем обратное действие к вычитанию $2$.
Выполним обратное действие: $14 + 2 = 16$.
Это была команда №2.

Шаг 5. Теперь у нас число $16$. Заметим, что $16 = 4^2$. А число $4$ — это как раз наше исходное число.
Выполним обратное действие: $\sqrt{16} = 4$.
Это была команда №1.

Проверка.
Запишем команды в прямом порядке (от $4$ к $142$):
1. Команда 1: $4^2 = 16$
2. Команда 2: $16 - 2 = 14$
3. Команда 2: $14 - 2 = 12$
4. Команда 1: $12^2 = 144$
5. Команда 2: $144 - 2 = 142$

Алгоритм состоит из 5 команд: 12212.

Ответ: 12212

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