Question

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

1. возведи в квадрат
2. прибавь 1

Первая команда возводит число на экране в квадрат, вторая увеличивает его на 1. Найдите порядок команд в программе, которая преобразует число 1 в число 17 и содержит не более 4 команд. Укажите только номера команд.

(Пример: программа `2122` означает последовательность команд «прибавь 1, возведи в квадрат, прибавь 1, прибавь 1» и преобразует 1 в 6.)

Accepted Answer

2112

Answer

Идея решения: поскольку возведение в квадрат необратимо для большинства чисел, проще работать в обратном направлении — от 17 к 1, восстанавливая команды справа налево.

**Обратный ход:**

1) Число 17 не является полным квадратом, значит оно получено командой 2 (прибавь 1) из числа 16:
   $$17 = 16 + 1$$
   Команда: **2**

2) Число 16 — полный квадрат: $16 = 4^2$. Используем команду 1 (возведи в квадрат):
   $$16 = 4^2$$
   Команда: **1**

3) Число 4 — полный квадрат: $4 = 2^2$. Используем команду 1:
   $$4 = 2^2$$
   Команда: **1**

4) Число 2 не является полным квадратом, получено командой 2 из числа 1:
   $$2 = 1 + 1$$
   Команда: **2**

Восстановленные команды в обратном порядке: 2, 1, 1, 2.

Читаем справа налево (в прямом порядке выполнения): **2112**

- Начало: 1
- Команда 2 (прибавь 1): $1 + 1 = 2$
- Команда 1 (возведи в квадрат): $2^2 = 4$
- Команда 1 (возведи в квадрат): $4^2 = 16$
- Команда 2 (прибавь 1): $16 + 1 = 17$ ✓

Задание №5Системы счисления и арифметикаЕГЭ по информатике