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

Решение.

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

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

Шаг 1. Рассмотрим число $64$. Мы можем либо извлечь корень, либо прибавить $4$.
Если мы извлечем корень ($\sqrt{64}$), получим $8$. Это кажется перспективным, так как число уменьшается.
Команда (обратная): 1.

Шаг 2. Теперь у нас число $8$.
Извлечь корень из $8$ нацело нельзя (исполнитель работает с натуральными числами). Значит, остается только прибавить $4$:
$8 + 4 = 12$.
Команда (обратная): 2.

Шаг 3. Теперь у нас число $12$.
Извлечь корень из $12$ нельзя. Прибавляем $4$:
$12 + 4 = 16$.
Команда (обратная): 2.

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

Шаг 5. Теперь у нас число $4$.
Извлекаем корень: $\sqrt{4} = 2$.
Команда (обратная): 1.

Мы пришли к исходному числу $2$ за $5$ шагов. Теперь запишем последовательность команд в прямом порядке (от шага 5 к шагу 1):
1. Число $2$, команда 1 (возведи в квадрат): $2^2 = 4$.
2. Число $4$, команда 1 (возведи в квадрат): $4^2 = 16$.
3. Число $16$, команда 2 (вычти 4): $16 - 4 = 12$.
4. Число $12$, команда 2 (вычти 4): $12 - 4 = 8$.
5. Число $8$, команда 1 (возведи в квадрат): $8^2 = 64$.

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

Ответ: 11221

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