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

Решение.

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

Для решения таких задач удобно рассуждать «с конца», то есть идти от итогового числа $27$ к исходному числу $2$, используя обратные операции (извлечение корня и вычитание единицы).

Шаг 1. Рассмотрим число $27$. Из него нельзя извлечь целый квадратный корень, поэтому единственная возможная обратная операция — это вычитание единицы (команда 2).
$27 - 1 = 26$. (Последняя команда — 2).

Шаг 2. Рассмотрим число $26$. Из него также нельзя извлечь целый квадратный корень. Снова вычитаем единицу:
$26 - 1 = 25$. (Предпоследняя команда — 2).

Шаг 3. Рассмотрим число $25$. Это число является полным квадратом ($5^2 = 25$). Значит, мы могли получить его возведением в квадрат числа $5$.
$\sqrt{25} = 5$. (Третья команда с конца — 1).

Шаг 4. Рассмотрим число $5$. Из него нельзя извлечь целый корень. Вычитаем единицу:
$5 - 1 = 4$. (Вторая команда с конца — 2).

Шаг 5. Рассмотрим число $4$. Мы можем получить его из числа $2$ (нашего начального числа) путём возведения в квадрат.
$\sqrt{4} = 2$. (Первая команда — 1).

Проверим полученную последовательность команд в прямом порядке (12122):
1) Число $2$, команда 1: $2^2 = 4$;
2) Число $4$, команда 2: $4 + 1 = 5$;
3) Число $5$, команда 1: $5^2 = 25$;
4) Число $25$, команда 2: $25 + 1 = 26$;
5) Число $26$, команда 2: $26 + 1 = 27$.

Алгоритм состоит из 5 команд и приводит к нужному результату.

Ответ: 12122

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