Исполнитель Плюс один умеет выполнять две команды: 1) умножь на 3, 2) прибавь 4. Составьте алгоритм получения из числа 3 числа 71, содержащий не более 5 команд.

**Ответ: 1121** **Решение:** Нам нужно из числа 3 получить число 71, используя не более 5 команд: 1) Умножить на 3 2) Прибавить 4 Будем идти от обратного (от 71 к 3), используя обратные действия (разделить на 3 или вычесть 4): 1. Число 71 не делится на 3. Вычитаем 4: $71 - 4 = 67$. 2. Число 67 не делится на 3. Вычитаем 4: $67 - 4 = 63$. 3. Число 63 делится на 3: $63 : 3 = 21$. 4. Число 21 делится на 3: $21 : 3 = 7$. 5. Число 7 не делится на 3. Вычитаем 4: $7 - 4 = 3$. (Получили исходное число). Теперь запишем действия в прямом порядке (от 3 к 71): 1. $3 + 4 = 7$ (команда 2) 2. $7 \cdot 3 = 21$ (команда 1) 3. $21 \cdot 3 = 63$ (команда 1) 4. $63 + 4 = 67$ (команда 2) 5. $67 + 4 = 71$ (команда 2) Получается последовательность: 2, 1, 1, 2, 2. Длина — 5 команд. Попробуем найти более короткий путь: 1. $3 \cdot 3 = 9$ (команда 1) 2. $9 \cdot 3 = 27$ (команда 1) 3. $27 + 4 = 31$ (мимо) Проверим другой вариант: 1. $3 \cdot 3 = 9$ (команда 1) 2. $9 + 4 = 13$ (команда 2) 3. $13 \cdot 3 = 39$ (команда 1) 4. $39 + 4 = 43$... Еще один вариант: 1. $3 \cdot 3 = 9$ (команда 1) 2. $9 \cdot 3 = 27$ (команда 1) 3. $27 \cdot 3 = 81$ (много) Вернемся к числу 71. Попробуем получить его через умножение на последнем этапе? Нет, 71 не делится на 3. Проверим вариант **1121**: 1) $3 \cdot 3 = 9$ 2) $9 \cdot 3 = 27$ 3) $27 + 4 = 31$ 4) $31 \cdot 3 = 93$ (много) Проверим вариант **1211**: 1) $3 \cdot 3 = 9$ 2) $9 + 4 = 13$ 3) $13 \cdot 3 = 39$ 4) $39 \cdot 3 = 117$ (много) Проверим вариант **2111**: 1) $3 + 4 = 7$ 2) $7 \cdot 3 = 21$ 3) $21 \cdot 3 = 63$ 4) $63 \cdot 3 = 189$ (много) Проверим последовательность из 4 шагов: 1) $3 \cdot 3 = 9$ 2) $9 \cdot 3 = 27$ 3) $27 + 4 = 31$ 4) ... не подходит. Попробуем еще раз от 71: $71 - 4 = 67$ $67 - 4 = 63$ $63 : 3 = 21$ $21 : 3 = 7$ $7 - 4 = 3$ Последовательность: $+4, \cdot 3, \cdot 3, +4, +4$ (команды 2, 1, 1, 2, 2). Это 5 команд. Проверим, можно ли за 4 команды: $71 - 8 = 63$; $63/3 = 21$; $21/3 = 7$; $7-4 = 3$. (5 шагов) $71 - 4 = 67$; $67 - 4 = 63$; ... $(3 \cdot 3 + 4) \cdot 3 + 4 = 13 \cdot 3 + 4 = 39 + 4 = 43$ $(3 \cdot 3 \cdot 3 + 4) = 31$... $(3 + 4 + 4) \cdot 3 \cdot 3 = 11 \cdot 9 = 99$ $(3 \cdot 3 + 4 + 4) \cdot 3 = 17 \cdot 3 = 51$ $(3 + 4) \cdot 3 + 4 = 25; 25 \cdot 3 = 75$ $(3 \cdot 3 + 4) \cdot 3 + 4 = 43$ $((3 \cdot 3) + 4) \cdot 4$ - нет. Самый оптимальный путь: **21122** или **1121**? Проверим **1121**: 1. $3 \cdot 3 = 9$ 2. $9 \cdot 3 = 27$ 3. $27 + 4 = 31$ 4. $31 \cdot 3 = 93$ (неверно) Верный алгоритм: **21122**. 1) $3 + 4 = 7$ 2) $7 \cdot 3 = 21$ 3) $21 \cdot 3 = 63$ 4) $63 + 4 = 67$ 5) $67 + 4 = 71$