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

Решение.

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

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

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

Шаг 2. Из числа $83$ также нельзя извлечь корень. Снова вычитаем единицу:
$83 - 1 = 82$ (Команда №2 в прямом порядке).

Шаг 3. Из числа $82$ корень не извлекается. Вычитаем единицу:
$82 - 1 = 81$ (Команда №2 в прямом порядке).

Шаг 4. Число $81$ является полным квадратом ($9^2 = 81$). Значит, мы можем применить обратную команду извлечения корня:
$\sqrt{81} = 9$ (Команда №1 в прямом порядке).

Шаг 5. Теперь из числа $9$ мы можем либо вычесть 1, либо извлечь корень. Проверим извлечение корня:
$\sqrt{9} = 3$ (Команда №1 в прямом порядке).
Мы получили исходное число $3$. Весь путь занял ровно 5 команд.

Проверка в прямом порядке:
1. Команда 1: $3^2 = 9$
2. Команда 1: $9^2 = 81$
3. Команда 2: $81 + 1 = 82$
4. Команда 2: $82 + 1 = 83$
5. Команда 2: $83 + 1 = 84$

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

Ответ: 11222

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