7. Линейный алгоритм для исполнителя: Исполнитель Квадратор умеет выполнять две команды, у каждой…
Исполнитель Квадратор умеет выполнять две команды, у каждой есть свой номер:
1. возведи в квадрат
2. прибавь 1
Первая возводит число на экране в квадрат, вторая увеличивает число на экране на 1.
Запишите алгоритм, который из числа 2 получает число 37 и содержит не больше 5 команд. В ответе укажите только номера команд подряд, без пробелов и запятых.
Пример записи: 21 — это алгоритм
прибавь 1
возведи в квадрат,
который из числа 3 получает число 16.
Будем рассуждать с конца. Число 37 не является квадратом целого числа, значит, последней выполнена команда «прибавь 1», а до нее на экране было 36. Число $36 = 6^2$, поэтому перед этим можно получить 6 и возвести его в квадрат. Из 2 число 6 получается так: $2^2 = 4$, $4 + 1 = 5$, $5 + 1 = 6$. Вместе с возведением в квадрат и последним прибавлением единицы получается пять команд.
Проверим алгоритм 12212:
2 → возведи в квадрат → 4
4 → прибавь 1 → 5
5 → прибавь 1 → 6
6 → возведи в квадрат → 36
36 → прибавь 1 → 37
Получили 37 за 5 команд. Другого алгоритма не длиннее 5 команд нет.