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

Решение.

Нам необходимо составить алгоритм из последовательности команд, который преобразует число $14$ в число $58$. Всего в алгоритме должно быть не более 5 команд. Доступные команды:
1. Возведи в квадрат ($x^2$);
2. Вычти 3 ($x - 3$).

Попробуем рассуждать от обратного — от конечного числа $58$ к исходному числу $14$. Это часто упрощает поиск, так как обратных операций меньше. Обратные команды будут такими:
1. Извлеки квадратный корень ($\sqrt{x}$);
2. Прибавь 3 ($x + 3$).

Шаг 1. Число $58$ не является полным квадратом, поэтому мы не можем извлечь корень. Применяем обратную команду №2: $58 + 3 = 61$.
Шаг 2. Число $61$ не является полным квадратом. Применяем обратную команду №2: $61 + 3 = 64$.
Шаг 3. Число $64$ является полным квадратом ($8^2 = 64$). Применяем обратную команду №1: $\sqrt{64} = 8$.
Шаг 4. Число $8$ не является полным квадратом. Применяем обратную команду №2: $8 + 3 = 11$.
Шаг 5. Число $11$ не является полным квадратом. Применяем обратную команду №2: $11 + 3 = 14$.

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

Проверим полученную последовательность команд 22122:
$14 \xrightarrow{2} 11 \xrightarrow{2} 8 \xrightarrow{1} 64 \xrightarrow{2} 61 \xrightarrow{2} 58$.
Алгоритм верный и содержит ровно 5 команд.

Ответ: 22122

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