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

Решение.

Нам необходимо составить алгоритм для исполнителя «Квадратор», который превращает число $1$ в число $100$ ровно за $5$ шагов. У нас есть две команды:
1. прибавь $1$
2. возведи в квадрат

Для решения таких задач удобнее всего двигаться «с конца» — от итогового числа $100$ к исходному числу $1$. При этом команды будут заменяться на обратные:
1. вместо «прибавь $1$» будем выполнять «вычти $1$»;
2. вместо «возведи в квадрат» будем выполнять «извлеки квадратный корень».

Шаг 1. Посмотрим на число $100$. Из него можно извлечь квадратный корень: $\sqrt{100} = 10$. Это соответствует команде №2 (в прямом порядке).
Если бы мы вычитали $1$, мы бы получили $99$, из которого корень не извлекается, и нам пришлось бы долго вычитать единицы, что не уложится в лимит команд.

Шаг 2. Теперь у нас число $10$. Из него нельзя извлечь целый корень, поэтому единственный путь — вычесть $1$:
$10 - 1 = 9$. Это соответствует команде №1.

Шаг 3. Из числа $9$ можно извлечь квадратный корень: $\sqrt{9} = 3$. Это соответствует команде №2.

Шаг 4. Из числа $3$ нельзя извлечь целый корень, вычитаем $1$:
$3 - 1 = 2$. Это соответствует команде №1.

Шаг 5. Из числа $2$ вычитаем $1$:
$2 - 1 = 1$. Мы пришли к исходному числу. Это соответствует команде №1.

Теперь запишем полученные команды в обратном порядке (от числа $1$ к числу $100$):
1. Число $1$, команда 1: $1 + 1 = 2$
2. Число $2$, команда 1: $2 + 1 = 3$
3. Число $3$, команда 2: $3^{2} = 9$
4. Число $9$, команда 1: $9 + 1 = 10$
5. Число $10$, команда 2: $10^{2} = 100$

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

Ответ: 11212

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