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

Решение:

Цель: получить из числа 3 число 87, используя не более 5 команд.

Команды:

1. Возвести в квадрат
2. Прибавить 2

Рассмотрим возможные последовательности команд, двигаясь от исходного числа 3 к целевому числу 87:

1. Алгоритм 1:
• 3 --(2)--> 5 --(1)--> 25 --(2)--> 27 --(2)--> 29 --(2)--> 31 (5 команд, не 87)
• 3 --(1)--> 9 --(2)--> 11 --(2)--> 13 --(2)--> 15 (4 команды, не 87)
• 3 --(1)--> 9 --(2)--> 11 --(1)--> 121 (3 команды, не 87)
• 3 --(2)--> 5 --(2)--> 7 --(2)--> 9 --(1)--> 81 (4 команды, не 87)
• 3 --(2)--> 5 --(2)--> 7 --(1)--> 49 --(2)--> 51 (4 команды, не 87)
• 3 --(2)--> 5 --(1)--> 25 --(2)--> 27 (3 команды, не 87)
• 3 --(1)--> 9 --(1)--> 81 --(2)--> 83 (3 команды, не 87)
2. Попробуем работать от числа 87 назад:
• 87 - 2 = 85
• 85 - 2 = 83
• 83 - 2 = 81
• 81 - 2 = 79

Теперь применим операцию возведения в квадрат к числам, которые могли бы дать 81, 83, 85, 87:

• Если предыдущая команда была «возведи в квадрат», то извлекая корень, мы получим:
• √87 (не целое)
• √85 (не целое)
• √83 (не целое)
• √81 = 9

Итак, мы можем получить 81, применив команду 1 к числу 9.

Теперь наша задача — получить число 9 из числа 3.

• 3 --(1)--> 9 (1 команда)

Теперь объединим шаги:

• Исходное число: 3
• Команда 1: возведи в квадрат (3² = 9)
• Команда 1: возведи в квадрат (9² = 81)
• Команда 2: прибавь 2 (81 + 2 = 83)
• Команда 2: прибавь 2 (83 + 2 = 85)

Таким образом, алгоритм: 1122. Получаем 85. Не 87.

Давайте рассмотрим другой путь:

Чтобы получить 87, мы можем попробовать дойти до числа, квадрат которого близок к 87, или число, к которому прибавив 2, получим 87.

87 - 2 = 85 (не является полным квадратом)

87 - 2 - 2 = 83 (не является полным квадратом)

87 - 2 - 2 - 2 = 81. 81 = 9². Значит, мы можем получить 81, затем прибавить 2, затем еще 2. Итого: 81 + 2 + 2 = 85. Это 3 команды.

Теперь нам нужно получить 81 из 3. Мы знаем, что 3² = 9. И 9² = 81. То есть, 3 -> 9 -> 81. Это 2 команды.

Общий алгоритм: 1122. Получаем 85.

Попробуем получить 87 другим способом:

Нам нужно получить 87. Используем команды 1 (квадрат) и 2 (прибавить 2).

Если последнее действие — прибавление 2, то перед этим число должно быть 85. 85 из 3 за 4 команды: 3 -> 5 -> 7 -> 9 -> 81 (не 85)

Давайте попробуем с конца:

87. Если последнее действие было +2, то предыдущее число было 85. Если было возведение в квадрат, то √87 (не целое).

Теперь нам нужно получить 85 из 3.

3 --(2)--> 5 --(2)--> 7 --(2)--> 9 --(2)--> 11 (4 команды, не 85)

3 --(1)--> 9 --(2)--> 11 --(2)--> 13 --(2)--> 15 (4 команды, не 85)

Попробуем такой алгоритм:

3 --(1)--> 9 (команда 1)

9 --(2)--> 11 (команда 2)

11 --(1)--> 121 (команда 1)

121 --(2)--> 123 (команда 2)

Это 4 команды, результат 123.

Рассмотрим задачу получения 87 из 3:

3 --(1)--> 9

9 --(1)--> 81

81 --(2)--> 83

83 --(2)--> 85

85 --(2)--> 87

Этот алгоритм состоит из 5 команд: 11222.

Проверяем:

1. 3 (исходное число)
2. 3² = 9 (команда 1)
3. 9² = 81 (команда 1)
4. 81 + 2 = 83 (команда 2)
5. 83 + 2 = 85 (команда 2)
6. 85 + 2 = 87 (команда 2)

Алгоритм 11222 содержит 5 команд и приводит к числу 87.

Ответ: 11222