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

Решение.

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

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

Шаг 1. Начнём с числа $26$. Оно не является полным квадратом, поэтому мы можем только вычесть $1$:
$26 - 1 = 25$. (Это была команда №2 в обратном порядке).

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

Шаг 3. Число $5$ не является полным квадратом. Вычитаем $1$:
$5 - 1 = 4$. (Это была команда №2 в обратном порядке).

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

Шаг 5. Из числа $2$ нам нужно получить исходную единицу. Вычитаем $1$:
$2 - 1 = 1$. (Это была команда №2 в обратном порядке).

Теперь запишем полученные команды в прямом порядке (от шага 5 к шагу 1):
1. Прибавь 1: $1 + 1 = 2$ (команда 2)
2. Возведи в квадрат: $2^2 = 4$ (команда 1)
3. Прибавь 1: $4 + 1 = 5$ (команда 2)
4. Возведи в квадрат: $5^2 = 25$ (команда 1)
5. Прибавь 1: $25 + 1 = 26$ (команда 2)

Последовательность команд: 21212. Проверим количество: ровно 5 команд, что соответствует условию задачи.

Ответ: 21212

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