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

Решение.

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

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

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

Шаг 2. Из числа $22$ корень не извлекается. Снова прибавляем 3:
$22 + 3 = 25$. (Снова команда 2).

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

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

Шаг 5. Из числа $8$ корень не извлекается. Прибавляем 3:
$8 + 3 = 11$. (Это тупиковый путь, так как мы не пришли к 1 за 5 шагов).

Попробуем другой путь. Вернёмся к числу $5$ на шаге 3 и попробуем получить его из $1$ прямым ходом:
1. Начнём с $1$.
2. Применим команду №2? Нет, $1 - 3 = -2$, это не поможет. Применим команду №2 дважды? Нет.
3. Попробуем идти от $1$ вперёд, зная, что нам нужно попасть в «удобные» числа.

Прямой ход:
1. Начнём с числа $1$. Применим команду №2 (вычти 3): $1 - 3 = -2$.
2. Применим команду №1 (возведи в квадрат): $(-2)^2 = 4$.
3. Применим команду №1 (возведи в квадрат): $4^2 = 16$.
4. Применим команду №2 (вычти 3): $16 - 3 = 13$. (Не подходит).

Ещё одна попытка прямого хода:
1. Команда 2: $1 - 3 = -2$.
2. Команда 2: $-2 - 3 = -5$.
3. Команда 1: $(-5)^2 = 25$.
4. Команда 2: $25 - 3 = 22$.
5. Команда 2: $22 - 3 = 19$.

Проверим последовательность команд: 2 (вычли 3), 2 (вычли 3), 1 (квадрат), 2 (вычли 3), 2 (вычли 3).
Вычисления: $1 \xrightarrow{2} -2 \xrightarrow{2} -5 \xrightarrow{1} 25 \xrightarrow{2} 22 \xrightarrow{2} 19$.
Алгоритм содержит ровно 5 команд и приводит к числу 19.

Ответ: 22122

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