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

Решение.

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

Для решения таких задач удобно использовать метод «обратного хода» — двигаться от конечного числа $13$ к начальному числу $2$. При этом команды заменяются на противоположные:
1. Вместо возведения в квадрат — извлечение квадратного корня (если число является полным квадратом);
2. Вместо вычитания единицы — прибавление единицы.

Попробуем восстановить путь от $13$ к $2$ за $5$ шагов:
Шаг 1: Число $13$ не является полным квадратом, поэтому мы можем только прибавить $1$.
$13 + 1 = 14$
Шаг 2: Число $14$ не является полным квадратом, прибавляем $1$.
$14 + 1 = 15$
Шаг 3: Число $15$ не является полным квадратом, прибавляем $1$.
$15 + 1 = 16$
Шаг 4: Число $16$ является полным квадратом ($4^2$). Извлекаем корень.
$\sqrt{16} = 4$
Шаг 5: Число $4$ является полным квадратом ($2^2$). Извлекаем корень.
$\sqrt{4} = 2$

Мы пришли к исходному числу $2$. Теперь запишем команды в прямом порядке (от $2$ к $13$), заменяя обратные действия на исходные:
1. (из шага 5) Возведи в квадрат: $2^2 = 4$ (Команда 1)
2. (из шага 4) Возведи в квадрат: $4^2 = 16$ (Команда 1)
3. (из шага 3) Вычти 1: $16 - 1 = 15$ (Команда 2)
4. (из шага 2) Вычти 1: $15 - 1 = 14$ (Команда 2)
5. (из шага 1) Вычти 1: $14 - 1 = 13$ (Команда 2)

Проверим полученную последовательность команд: $11222$.
$2 \xrightarrow{1} 4 \xrightarrow{1} 16 \xrightarrow{2} 15 \xrightarrow{2} 14 \xrightarrow{2} 13$.
Алгоритм состоит из $5$ команд и приводит к нужному результату.

Ответ: 11222

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