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

Решение.

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

Будем решать задачу методом обратного хода — от конечного числа $25$ к начальному числу $1$. Это удобнее, так как количество возможных действий на каждом шаге уменьшается. Обратные команды будут такими:
1. извлеки квадратный корень ($\sqrt{x}$);
2. вычти 3 ($x - 3$).

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

Шаг 2. У нас число $5$.
Корень из $5$ не извлекается нацело, поэтому используем только вычитание:
$5 - 3 = 2$ (команда 2).

Шаг 3. У нас число $2$.
Корень из $2$ не извлекается нацело. Вычитаем 3:
$2 - 3 = -1$. Это число меньше начального ($1$), значит, этот путь тупиковый. Вернемся назад.

Попробуем другой путь (начиная с конца):
1. $25 - 3 = 22$ (команда 2)
2. $22 - 3 = 19$ (команда 2)
3. $19 - 3 = 16$ (команда 2)
4. Из $16$ можно извлечь корень: $\sqrt{16} = 4$ (команда 1)
5. Из $4$ можно извлечь корень: $\sqrt{4} = 2$ (команда 1). Опять не приходим к $1$.
Или из $4$ вычесть 3: $4 - 3 = 1$ (команда 2). Это подходит!

Запишем полученную последовательность обратных действий: $25 \xrightarrow{-3} 22 \xrightarrow{-3} 19 \xrightarrow{-3} 16 \xrightarrow{\sqrt{}} 4 \xrightarrow{-3} 1$.
Теперь запишем эти команды в прямом порядке (от $1$ к $25$) и заменим их на номера из условия:
1. $1 + 3 = 4$ (команда 2)
2. $4^2 = 16$ (команда 1)
3. $16 + 3 = 19$ (команда 2)
4. $19 + 3 = 22$ (команда 2)
5. $22 + 3 = 25$ (команда 2)

Проверим количество команд: их ровно 5. Последовательность номеров команд: 2, 1, 2, 2, 2.

Ответ: 21222

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