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

Решение.

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

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

Шаг 1. Число $85$ не является полным квадратом, поэтому извлечь корень (команда 1 наоборот) нельзя. Применяем обратную команду 2:
$85 - 2 = 83$. (Это 5-я команда алгоритма)

Шаг 2. Число $83$ также не является полным квадратом. Снова применяем обратную команду 2:
$83 - 2 = 81$. (Это 4-я команда алгоритма)

Шаг 3. Число $81$ является квадратом числа $9$. Попробуем применить обратную команду 1:
$\sqrt{81} = 9$. (Это 3-я команда алгоритма)

Шаг 4. Число $9$ является квадратом числа $3$, но если мы извлечем корень, то получим $3$, из которого за один шаг (оставшуюся 1 команду) нельзя получить $1$. Поэтому попробуем применить к числу $9$ обратную команду 2:
$9 - 2 = 7$. (Не подходит, так как из $7$ нельзя получить $1$ за один шаг).
Вернемся к числу $9$ и применим обратную команду 1:
$\sqrt{9} = 3$. (Это 2-я команда алгоритма)

Шаг 5. Теперь из числа $3$ нам нужно получить исходное число $1$. Применяем обратную команду 2:
$3 - 2 = 1$. (Это 1-я команда алгоритма)

Проверим полученную последовательность в прямом порядке (от $1$ к $85$):
1. Команда 2: $1 + 2 = 3$
2. Команда 1: $3^2 = 9$
3. Команда 1: $9^2 = 81$
4. Команда 2: $81 + 2 = 83$
5. Команда 2: $83 + 2 = 85$

Последовательность команд: 21122.

Ответ: 21122

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