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

Решение:

Нам нужно получить число 25 из числа 4, используя не более 5 команд (1 - вычти 1, 2 - умножь на 3).

Попробуем строить алгоритм в обратном порядке или прямом.

Прямой путь:

• Начнем с 4.
• 4 * 3 = 12 (команда 2)
• 12 + 1 = 13 (команда 1, но нам нужно 25)
• 4 + 1 = 5 (команда 1)
• 5 * 3 = 15 (команда 2)
• 15 + 1 = 16 (команда 1)
• 16 + 1 = 17 (команда 1)
• 17 + 1 = 18 (команда 1)
• ...

Попробуем другой подход. Так как нам нужно получить число 25, а команды 2 (умножить на 3) увеличивают число быстро, скорее всего, она будет использоваться.

Если последнее действие - вычесть 1 (команда 1), то предыдущее число было 26. Из 4 получить 26 за 4 команды.

Если последнее действие - умножить на 3 (команда 2), то предыдущее число было 25/3, что не целое. Значит, последняя команда не может быть умножение на 3.

Итак, последняя команда - вычти 1. Предыдущее число 26.

Как получить 26 из 4 за 4 команды:

• 4 * 3 = 12 (2)
• 12 + 1 = 13 (1)
• 13 + 1 = 14 (1)
• 14 + 1 = 15 (1)
• 15 + 1 = 16 (1) - не 26

Рассмотрим обратный порядок: 25. Последняя команда - вычти 1, предыдущее число 26. Последняя команда - вычти 1, предыдущее число 27. Последняя команда - вычти 1, предыдущее число 28. Последняя команда - вычти 1, предыдущее число 29.

Рассмотрим, если последнее действие — вычти 1. Значит, получили 25 из 26. Как получить 26 из 4?

4 * 3 = 12 (2)

12 + 1 = 13 (1)

13 + 1 = 14 (1)

14 + 1 = 15 (1)

15 + 1 = 16 (1)

Попробуем иначе:

4 -> (2) 12 -> (2) 36 (слишком много)

4 -> (2) 12 -> (1) 11 -> (2) 33 (слишком много)

4 -> (1) 3 -> (2) 9 -> (2) 27 (близко)

4 -> (1) 3 -> (2) 9 -> (2) 27 -> (1) 26 -> (1) 25 (5 команд: 12211)

Проверим:

• 4
• 4 - 1 = 3 (1)
• 3 * 3 = 9 (2)
• 9 * 3 = 27 (2)
• 27 - 1 = 26 (1)
• 26 - 1 = 25 (1)

Этот алгоритм содержит 5 команд.

Ответ: 12211