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

Решение.

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

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

Шаг 1. Начнём с числа $21$. Извлечь корень из $21$ нельзя (не получится целое число), поэтому применяем обратную команду №2:
$21 + 4 = 25$. (Это была команда 2 в прямом порядке).

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

Шаг 3. Из числа $5$ корень не извлекается. Применяем обратную команду №2:
$5 + 4 = 9$. (Это была команда 2 в прямом порядке).

Шаг 4. Из числа $9$ можно извлечь корень:
$\sqrt{9} = 3$. (Это была команда 1 в прямом порядке).

Шаг 5. Из числа $3$ корень не извлекается. Применяем обратную команду №2:
$3 + 4 = 7$. (Это не ведёт нас к единице).
Попробуем другой путь на 4-м шаге. Если из $9$ не извлекать корень, а прибавить 4, мы получим $13$, что ещё дальше от единицы. Значит, вернёмся к числу $5$ и попробуем прибавлять 4, пока не получим число, из которого извлекается корень и которое ближе к $1$. Но у нас ограничение в 5 команд.

Давайте проверим полученную последовательность в прямом порядке (от $1$ к $21$):
1. Команда 2: $1 - 4 = -3$
2. Команда 1: $(-3)^2 = 9$
3. Команда 2: $9 - 4 = 5$
4. Команда 1: $5^2 = 25$
5. Команда 2: $25 - 4 = 21$

Проверим вычисления еще раз:
1) $1 - 4 = -3$
2) $(-3) \cdot (-3) = 9$
3) $9 - 4 = 5$
4) $5 \cdot 5 = 25$
5) $25 - 4 = 21$

Алгоритм состоит из 5 команд: 2, 1, 2, 1, 2. Это соответствует условию задачи.

Ответ: 21212

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