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

Решение.

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

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

Шаг 1. Начнём с числа $55$.
Извлечь корень из $55$ нельзя (не получится целое число), поэтому применяем обратную команду №2:
$55 - 3 = 52$. (Команда №2 в прямом порядке)

Шаг 2. У нас число $52$.
Корень из $52$ не извлекается. Снова вычитаем 3:
$52 - 3 = 49$. (Команда №2 в прямом порядке)

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

Шаг 4. У нас число $7$.
Корень из $7$ не извлекается. Вычитаем 3:
$7 - 3 = 4$. (Команда №2 в прямом порядке)

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

Мы пришли к исходному числу $2$. Теперь запишем команды в прямом порядке (от числа 2 к числу 55):
1. Число $2$: возводим в квадрат (команда 1) $\rightarrow 4$;
2. Число $4$: прибавляем 3 (команда 2) $\rightarrow 7$;
3. Число $7$: возводим в квадрат (команда 1) $\rightarrow 49$;
4. Число $49$: прибавляем 3 (команда 2) $\rightarrow 52$;
5. Число $52$: прибавляем 3 (команда 2) $\rightarrow 55$.

Последовательность команд: 12122. Проверим количество: ровно 5 команд, что соответствует условию задачи.

Ответ: 12122

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