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

Решение.

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

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

Шаг 1. Посмотрим на число $144$. Оно является полным квадратом ($12^2 = 144$). Значит, последней командой в прямом алгоритме (из $2$ в $144$) логично предположить возведение в квадрат.
Если последняя команда — №1, то на предыдущем шаге было число $\sqrt{144} = 12$.

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

Шаг 3. Работаем с числом $14$. Оно также не является полным квадратом. Значит, снова используем обратную команду для №2.
Прибавляем: $14 + 2 = 16$.

Шаг 4. Число $16$ является полным квадратом ($4^2 = 16$). Значит, в прямом алгоритме здесь могла быть команда №1.
В обратном ходе извлекаем корень: $\sqrt{16} = 4$.

Шаг 5. Число $4$ является полным квадратом ($2^2 = 4$).
В обратном ходе извлекаем корень: $\sqrt{4} = 2$. Мы пришли к исходному числу!

Теперь запишем наши действия в прямом порядке (от $2$ к $144$):
1. Число $2$. Команда 1 (возведи в квадрат): $2^2 = 4$.
2. Число $4$. Команда 1 (возведи в квадрат): $4^2 = 16$.
3. Число $16$. Команда 2 (вычти 2): $16 - 2 = 14$.
4. Число $14$. Команда 2 (вычти 2): $14 - 2 = 12$.
5. Число $12$. Команда 1 (возведи в квадрат): $12^2 = 144$.

Полученная последовательность команд: 11221. Она содержит ровно 5 команд, что соответствует условию задачи.

Ответ: 11221

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