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

Решение.

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

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

Шаг 1. Посмотрим на число $262$. Оно не является полным квадратом, поэтому мы не можем применить обратную команду №1. Применяем обратную команду №2:
$262 - 3 = 259$. (Команда 2)

Шаг 2. Число $259$ также не является полным квадратом. Снова вычитаем 3:
$259 - 3 = 256$. (Команда 2)

Шаг 3. Число $256$ является квадратом числа $16$ ($16^2 = 256$). Применяем обратную команду №1:
$\sqrt{256} = 16$. (Команда 1)

Шаг 4. Число $16$ является квадратом числа $4$ ($4^2 = 16$). Применяем обратную команду №1:
$\sqrt{16} = 4$. (Команда 1)

Шаг 5. Из числа $4$ нам нужно получить исходное число $1$. Вычитаем 3:
$4 - 3 = 1$. (Команда 2)

Мы получили последовательность обратных действий: 2, 2, 1, 1, 2. Чтобы записать алгоритм для исполнителя, нужно прочитать эти действия в обратном порядке (от числа $1$ к числу $262$):
1. $1 + 3 = 4$ (Команда 2)
2. $4^2 = 16$ (Команда 1)
3. $16^2 = 256$ (Команда 1)
4. $256 + 3 = 259$ (Команда 2)
5. $259 + 3 = 262$ (Команда 2)

Итоговая последовательность команд: 21122.

Ответ: 21122

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