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

Решение.

Нам необходимо составить алгоритм для исполнителя Квадратор, который преобразует число $2$ в число $196$ за $5$ шагов или меньше. Доступны две команды: 1 (вычти $1$) и 2 (возведи в квадрат).

Для решения таких задач удобнее идти от конечного результата к начальному числу, выполняя обратные действия. Обратными действиями будут: для вычитания — сложение ($+1$), для возведения в квадрат — извлечение корня ($\sqrt{x}$).

Шаг 1. Конечный результат — число $196$. Попробуем применить обратную команду 2 (извлечение корня). Мы знаем, что $\sqrt{196} = 14$. Число $14$ — натуральное, значит, последней командой в прямом алгоритме была команда 2 (возведение в квадрат).
Текущее состояние: $196 \leftarrow 14$ (команда 2).

Шаг 2. Теперь работаем с числом $14$. Извлечь корень из $14$ нацело нельзя, поэтому применяем обратную команду 1 (прибавление единицы): $14 + 1 = 15$.
Текущее состояние: $14 \leftarrow 15$ (команда 1).

Шаг 3. Работаем с числом $15$. Снова извлечь корень нельзя, прибавляем единицу: $15 + 1 = 16$.
Текущее состояние: $15 \leftarrow 16$ (команда 1).

Шаг 4. Работаем с числом $16$. Из него можно извлечь корень: $\sqrt{16} = 4$. Это дает нам значительное продвижение к начальному числу $2$.
Текущее состояние: $16 \leftarrow 4$ (команда 2).

Шаг 5. Работаем с числом $4$. Из него также можно извлечь корень: $\sqrt{4} = 2$. Мы получили исходное число $2$.
Текущее состояние: $4 \leftarrow 2$ (команда 2).

Теперь запишем последовательность команд в прямом порядке (от $2$ к $196$):
1. Число $2$, команда 2: $2^2 = 4$
2. Число $4$, команда 2: $4^2 = 16$
3. Число $16$, команда 1: $16 - 1 = 15$
4. Число $15$, команда 1: $15 - 1 = 14$
5. Число $14$, команда 2: $14^2 = 196$

Последовательность номеров команд: 22112. Алгоритм содержит ровно 5 команд.

Ответ: 22112

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