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

К списку заданий

#55908Задание №5ФИПИ

Анализ алгоритма

У исполнителя Квадратор две команды, которым присвоены номера:

1. вычти 1

2. возведи в квадрат

Первая из них уменьшает число на экране на 1, вторая возводит его во вторую степень.

Исполнитель работает только с натуральными числами.

Составьте алгоритм получения из числа 3 числа 62, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 12112 – это алгоритм:

вычти 1

возведи в квадрат

вычти 1

возведи в квадрат,

который преобразует число 4 в 49.)

Если таких алгоритмов более одного, то запишите любой из них.

Правильный ответ

21211

Пояснение

Решение.

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

Для решения таких задач удобнее идти от конечного результата к начальному числу, используя обратные операции. Обратной операцией для «вычти 1» будет «прибавь 1», а для «возведи в квадрат» — «извлеки квадратный корень».

Попробуем восстановить путь от $62$ к $3$ :

Шаг 1. Число $62$ не является квадратом натурального числа, поэтому мы не можем применить обратную команду «извлечь корень». Значит, на последнем этапе была выполнена команда 1 (вычти 1).
Выполняем обратное действие: $62 + 1 = 63$ . (Команда 1 в прямом порядке)

Шаг 2. Число $63$ также не является квадратом. Снова предполагаем, что была выполнена команда 1.
Выполняем обратное действие: $63 + 1 = 64$ . (Команда 1 в прямом порядке)

Шаг 3. Число $64$ является квадратом числа $8$ . Это позволяет нам применить обратную команду «извлечь корень».
Выполняем обратное действие: $\sqrt{64} = 8$ . (Команда 2 в прямом порядке)

Шаг 4. Число $8$ не является квадратом. Применяем обратное действие к команде 1.
Выполняем обратное действие: $8 + 1 = 9$ . (Команда 1 в прямом порядке)

Шаг 5. Число $9$ является квадратом числа $3$ . Это наше исходное число.
Выполняем обратное действие: $\sqrt{9} = 3$ . (Команда 2 в прямом порядке)

Теперь запишем полученные команды в прямом порядке (от $3$ к $62$ ):
1. $3^2 = 9$ (команда 2)
2. $9 - 1 = 8$ (команда 1)
3. $8^2 = 64$ (команда 2)
4. $64 - 1 = 63$ (команда 1)
5. $63 - 1 = 62$ (команда 1)

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

Ответ: 21211

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