У исполнителя Квадратор две команды, которым присвоены номера: 1. возведи в квадрат 2. прибавь 1 Первая из них возводит число на экране во вторую степень, вторая увеличивает число на 1. Составьте алгоритм получения из числа 2 числа 101, содержащий не более 5 команд. В ответе запишите только номера команд. (Например, 22112 - это алгоритм: прибавь 1 прибавь 1 возведи в квадрат возведи в квадрат прибавь 1, который преобразует число 1 в 82.) Если таких алгоритмов более одного, то запишите любой из них.

Рассмотрим поставленную задачу: нужно получить число 101 из числа 2 за не более чем 5 команд, где команды обозначаются как: 1 — возвести число в квадрат 2 — прибавить 1 Изначально число равно 2. Постараемся найти такой алгоритм, который преобразует 2 в 101 за 5 или менее команд. Обратный подход — будем рассуждать, как получить 101, идя от него назад к 2: - Если число нечётное, то оно было получено прибавкой 1 после предыдущего (которое убедимся, что было чётным). - Если число чётное, его можно было получить возведением в квадрат предыдущего числа. Итак: 1. Начинаем с 101 (цель) 2. 101 — нечётное, значит, перед ним было 100 (после прибавки 1): 100 — чётное, следовательно, предыдущая операция — возведение в квадрат или прибавка? — Для 100: чётное. Можно было его получить, прибавив 1 к 99 — но это увеличивает число операции, так как при работающем порядке — идти назад. Лучше идти по обратному пути: от 101: - Уйти по обратной логике: 101 — нечетное, значит, могло быть получено добавлением 1 к 100: 100 — был результатом предыдущей операции. Двигаемся дальше: от 100 (чётное): - Могло быть получено возведением в квадрат числа 10, так как 10^2=100 Итак, предыдущим числом было 10. от 10 (чётное): - Можно было получить его возведением 3 (но 3^2=9), это не подходит. - Или из 9, но 9 — нечётное, значит, он был получен прибавкой 1 к 8 (8-это подошло?). Рассмотрим далее: от 10: - Возможно, 10 было получено прибавлением 1 к 9? — Тогда ранее было 9. - Можно было получить 10 путём прибавления 1 к 9 (нечётное — подходит). от 9: - Предыдущим было 8? - 8 — чётное, могло быть получено возведением в квадрат 2: 2^2=4, нет. - 8 — возможно, из 7 +1, значит, ранее было 7. от 7: - Можно было получить его прибавлением 1 к 6? — Тогда предыдущим числом было 6. от 6: - Можно было получить его возведением в квадрат 2? 2^2=4, нет. - Или из 5+1? 5 — нечётное? Да. - Тогда из 5. от 5: - Прибавление 1 к 4? 4 — чётное, было получено возведением 2 в квадрат? 2^2=4. Значит, от 2. Здесь получилась цепочка: 2 → (возвести в квадрат) 4 → (прибавить 1) 5 → (прибавить 1) 6 → (возвести в квадрат) 36 → (прибавить 1) 37 → (прибавить 1) 38 → (возвести в квадрат) 144 — слишком большое, а нам нужно было в 101. Нужно искать другой путь без такой длинной цепочки. --- Обратим внимание: Может быть проще составить алгоритм, исходя из прямых команд, проверяя, сможет ли он преобразовать 2 в 101 за 5 операций? Попробуем: - Если из 2 возвести в квадрат (команда 1): получим 4. - Затем прибавляем 1: 4 + 1 = 5. - Опять возводим в квадрат: 5^2=25. - Еще прибавляем 1: 25 + 1=26. - Еще раз возводим в квадрат: 26^2=676 (слишком много). Идея — попробовать последовательное применение операций: Посмотрим на возможную комбинацию: **Попытка 1:** 2 — возведи в квадрат (1): 4 4 — прибавь 1 (2): 5 5 — прибавь 1 (2): 6 6 — возвести в квадрат (1): 36 36 — прибавить 1 (2): 37 Еще один пример: 2 — складка (1): 4 4 — складка (1): 16 16 — прибавка (2): 17 17 — складка (1): 289 (слишком много) А давайте попробуем применить команду "возвести в квадрат" одному из чисел, чтобы приблизиться к 101? От 2: - 2 возвести в квадрат: 4 - 4 возвести в квадрат: 16 - 16 возвести в квадрат: 256 > 101, значит, не подходит, потому что мы превышаем 101, и нам нужно меньше команд. Поиграем в обратную сторону: Если мы получим 101, то попробуем разделить его на 2, если оно чётное, или прибавить 1, если нечетное, чтобы прийти к предыдущему числу. 101 — нечетное — значит, перед ним было 100, так как: 100 + 1 = 101. Если сделать так, чтобы получить 100: - 100 чётное, значит — оно могло быть получено возведением в квадрат: √100=10, то есть 10^2=100. От 10: - 10 — чётное, могло получить 10 — возведением в квадрат 3? 3^2=9, нет, не подходит. - Или из 9, нечётного, добавив 1? Итак, предыдущим было 9. Но из 9 можем попробовать дойти до 2: - 9 — нечётное, получено из 8+1 - 8 — чётное, из 2^2=4 или из 7+1? 8 — из 2^3, не подходит, потому что у нас только две команды, и возведения в квадрат — одна команда. Вернемся к простому варианту: Обратный алгоритм, основанный на командной последовательности: Используем последовательность: Команды: 1 (возвести в квадрат), 2 (прибавить 1) План действия: Начинаем с 2. - Возведи в квадрат (1): 2^2=4 - Прибавь 1 (2): 5 - Возведи в квадрат (1): 25 - Прибавь 1 (2): 26 - Возведи в квадрат (1): 676 (больше 101). Не подходит. Итак, попробуем: - из 2: прибавить 1: 3 (2) - из 3: прибавить 1: 4 (2) - из 4: возвести в квадрат: 16 (1) - из 16: прибавить 1: 17 (2) - из 17: прибавить 1: 18 (2) - из 18: возвести в квадрат: 324 (больше 101) — не подходит. Посмотрим на путевые сценарии снизу вверх. **Пробуем конкретный пример:** Возьмем такую последовательность команд: 1 2 2 2 2 (максимум 5 команд) — начиная с 2. - 2 (старт) - команда 1: возвести в квадрат: 4 - команда 2: прибавить 1: 5 - команда 2: прибавить 1: 6 - команда 2: прибавить 1: 7 - команда 2: прибавить 1: 8 Это дает 8, не 101. Попробуем: - 2 — команда 1: 4 - команда 1: 16 - команда 2: 17 - команда 2: 18 - команда 2: 19 — не подходит. Итак, попробуем другой путь: - 2 — команда 2: 3 - команда 1: 9 - команда 2: 10 - команда 1: 100 - команда 2: 101 Получилось! Пошагово: 2 — команда 2: прибавить 1 → 3 3 — команда 1: возвести в квадрат → 9 9 — команда 2: прибавить 1 → 10 10 — команда 1: возвести в квадрат → 100 100 — команда 2: прибавить 1 → 101 Всего 5 команд: 2 1 2 1 2 **Ответ:** 21212 Это соответствует требованиям и не превышает 5 команд. **Итог:** **Ответ: 21212**