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

Решение.

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

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

Шаг 1. Посмотрим на число $46$. Из него нельзя извлечь целый квадратный корень, поэтому применяем обратную команду №2 (прибавь 3):
$46 + 3 = 49$. (Это была бы команда 2, если смотреть от начала).

Шаг 2. Из числа $49$ можно извлечь квадратный корень:
$\sqrt{49} = 7$. (Это команда 1, если смотреть от начала).

Шаг 3. Из числа $7$ нельзя извлечь целый корень. Применяем обратную команду №2 (прибавь 3):
$7 + 3 = 10$. (Команда 2).

Шаг 4. Из числа $10$ нельзя извлечь целый корень. Применяем обратную команду №2 (прибавь 3):
$10 + 3 = 13$. (Команда 2).
Заметим: если мы продолжим прибавлять 3, мы будем отдаляться от начальной двойки. Попробуем пересмотреть шаги.

Попробуем другой путь (прямой перебор):
Нам нужно получить $46$. Заметим, что $46 + 3 = 49$, а $49$ — это $7^2$. Значит, последними командами могут быть 1 и 2.
Как получить $7$ из $2$?
1. Если мы возведем $2$ в квадрат (команда 1), получим $4$. Из $4$ прибавлением/вычитанием 3 получить $7$ сложно за 1 шаг.
2. Попробуем использовать только вычитание (команду 2) в обратном порядке. Чтобы получить $7$, нужно к какому-то числу прибавить 3.
Проверим последовательность команд 22212:
1) Команда 2: $2 - 3 = -1$
2) Команда 2: $-1 - 3 = -4$
3) Команда 2: $-4 - 3 = -7$
4) Команда 1: $(-7)^2 = 49$
5) Команда 2: $49 - 3 = 46$

Проверим количество команд: их ровно 5. Все действия выполнены верно, итоговое число $46$ получено из числа $2$.

Ответ: 22212

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