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

Решение.

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

Попробуем действовать методом «от обратного» — от числа $19$ к числу $2$. Это часто быстрее, так как операция извлечения корня (обратная возведению в квадрат) возможна не для всех чисел.

1. Последним действием (5-я команда) мы должны были получить $19$. Число $19$ не является полным квадратом, значит, оно могло быть получено только командой 1 (прибавь $1$).
Следовательно, до этого было число: $19 - 1 = 18$. (Команда 1)

2. Число $18$ также не является полным квадратом. Значит, на 4-м шаге тоже была команда 1.
До этого было число: $18 - 1 = 17$. (Команда 1)

3. Число $17$ не является полным квадратом. Значит, на 3-м шаге тоже была команда 1.
До этого было число: $17 - 1 = 16$. (Команда 1)

4. Число $16$ является полным квадратом ($4^2 = 16$). Значит, на 2-м шаге мы могли применить команду 2 (возведи в квадрат).
До этого было число: $\sqrt{16} = 4$. (Команда 2)

5. Число $4$ также является полным квадратом ($2^2 = 4$). Значит, на 1-м шаге мы могли применить команду 2.
До этого было число: $\sqrt{4} = 2$. (Команда 2)

Мы пришли к исходному числу $2$. Теперь запишем команды в прямом порядке (от 1-го шага к 5-му):
1) Число $2$, команда 2: $2^2 = 4$
2) Число $4$, команда 2: $4^2 = 16$
3) Число $16$, команда 1: $16 + 1 = 17$
4) Число $17$, команда 1: $17 + 1 = 18$
5) Число $18$, команда 1: $18 + 1 = 19$

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

Ответ: 22111

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