7. Составьте алгоритм получения из числа 84 числа 3, содержащий не более 5 команд. В ответе запишите только номера команд. (Например, 11122 - это алгоритм: вычти 5, вычти 5, вычти 5, раздели на 2, раздели на 2, который преобразует число 51 в число 9.) Если таких алгоритмов более одного, то запишите любой из них.

Решение:

Для решения данной задачи будем двигаться от числа 84 к числу 3, используя обратные команды. Это означает, что вместо «вычти 5» будем использовать «прибавь 5», а вместо «раздели на 2» будем использовать «умножь на 2».

1. Начнем с числа 84.
2. Если мы прибавим 5, получим 89.
3. Если мы умножим на 2, получим 168.
4. Попробуем другой подход: начнем с числа 3 и будем двигаться к 84, используя команды 1 (прибавить 5) и 2 (умножить на 2).
5. Шаг 1: Умножим 3 на 2. Получим 6. (Команда 2)
6. Шаг 2: Прибавим 5 к 6. Получим 11. (Команда 1)
7. Шаг 3: Умножим 11 на 2. Получим 22. (Команда 2)
8. Шаг 4: Прибавим 5 к 22. Получим 27. (Команда 1)
9. Шаг 5: Умножим 27 на 2. Получим 54. (Команда 2)
10. Шаг 6: Прибавим 5 к 54. Получим 59. (Команда 1)
11. Шаг 7: Умножим 59 на 2. Получим 118. (Команда 2)
12. Это слишком много шагов. Вернемся к исходной задаче и попробуем найти более короткий путь от 84 к 3.
13. Ключевая идея: Делить на 2 нужно как можно чаще, чтобы уменьшить число.
14. Алгоритм 1:
• 84 / 2 = 42 (Команда 2)
• 42 / 2 = 21 (Команда 2)
• 21 - 5 = 16 (Команда 1)
• 16 / 2 = 8 (Команда 2)
• 8 - 5 = 3 (Команда 1)
15. Этот алгоритм состоит из 5 команд: 22121.
16. Алгоритм 2 (альтернативный, если возможно):
• 84 - 5 = 79 (Команда 1)
• 79 - 5 = 74 (Команда 1)
• 74 - 5 = 69 (Команда 1)
• 69 - 5 = 64 (Команда 1)
• 64 / 2 = 32 (Команда 2)
• 32 / 2 = 16 (Команда 2)
• 16 / 2 = 8 (Команда 2)
• 8 - 5 = 3 (Команда 1)
17. Этот алгоритм содержит 8 команд, что больше допустимого.
18. Проверим Алгоритм 1:
• 84 --(2)--> 42
• 42 --(2)--> 21
• 21 --(1)--> 16
• 16 --(2)--> 8
• 8 --(1)--> 3
19. Получили число 3 за 5 команд.

Ответ: 22121