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

Решение.

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

Для решения таких задач удобнее всего идти от конечного результата к начальному числу, выполняя обратные действия. Обратными действиями будут:
1. Извлечение квадратного корня: $\sqrt{x}$.
2. Вычитание двойки: $x - 2$.

Шаг 1. Начнём с числа $68$.
Из числа $68$ нельзя извлечь целый квадратный корень, поэтому единственный возможный путь назад — вычитание двойки (команда 2).
$68 - 2 = 66$. (Это была 5-я команда алгоритма).

Шаг 2. Рассмотрим число $66$.
Из числа $66$ также нельзя извлечь целый квадратный корень. Снова вычитаем двойку:
$66 - 2 = 64$. (Это была 4-я команда алгоритма).

Шаг 3. Рассмотрим число $64$.
Здесь у нас есть выбор: вычесть двойку или извлечь корень. Попробуем извлечь корень, так как нам нужно быстро прийти к числу $4$:
$\sqrt{64} = 8$. (Это была 3-я команда алгоритма — возведение в квадрат).

Шаг 4. Рассмотрим число $8$.
Из числа $8$ нельзя извлечь целый корень. Вычитаем двойку:
$8 - 2 = 6$. (Это была 2-я команда алгоритма).

Шаг 5. Рассмотрим число $6$.
Вычитаем двойку:
$6 - 2 = 4$. (Это была 1-я команда алгоритма).
Мы пришли к исходному числу $4$ ровно за $5$ шагов.

Теперь запишем команды в прямом порядке (от $4$ к $68$):
1. Прибавь 2: $4 + 2 = 6$ (команда 2)
2. Прибавь 2: $6 + 2 = 8$ (команда 2)
3. Возведи в квадрат: $8^2 = 64$ (команда 1)
4. Прибавь 2: $64 + 2 = 66$ (команда 2)
5. Прибавь 2: $66 + 2 = 68$ (команда 2)

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

Ответ: 22122

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