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

Решение.

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

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

Шаг 1. Начнём с числа $37$.
Число $37$ не является полным квадратом, поэтому мы не можем применить обратную команду №1. Применяем обратную команду №2:
$37 - 1 = 36$. (Это была 5-я команда алгоритма — №2).

Шаг 2. Теперь у нас число $36$.
Число $36$ является полным квадратом ($6^2$). Выгодно применить обратную команду №1, так как она быстрее уменьшает число:
$\sqrt{36} = 6$. (Это была 4-я команда алгоритма — №1).

Шаг 3. Теперь у нас число $6$.
Число $6$ не является полным квадратом. Применяем обратную команду №2:
$6 - 1 = 5$. (Это была 3-я команда алгоритма — №2).

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

Шаг 5. Теперь у нас число $4$.
Число $4$ является полным квадратом ($2^2$). Применяем обратную команду №1:
$\sqrt{4} = 2$. (Это была 1-я команда алгоритма — №1).

Мы пришли к исходному числу $2$. Теперь запишем номера команд в прямом порядке (от 1-го шага к 5-му):
1. Команда №1: $2^2 = 4$
2. Команда №2: $4 + 1 = 5$
3. Команда №2: $5 + 1 = 6$
4. Команда №1: $6^2 = 36$
5. Команда №2: $36 + 1 = 37$

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

Ответ: 12212

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