7. Линейный алгоритм для исполнителя: Исполнитель Вычислитель умеет выполнять две команды, у каждой…
Исполнитель Вычислитель умеет выполнять две команды, у каждой есть свой номер:
1. прибавь 3
2. умножь на 2
Первая увеличивает число на экране на 3, вторая умножает число на экране на 2.
Запишите алгоритм, который из числа 2 получает число 31 и содержит не больше 5 команд. В ответе укажите только номера команд подряд, без пробелов и запятых.
Пример записи: 112 — это алгоритм
прибавь 3
прибавь 3
умножь на 2,
который из числа 1 получает число 14.
Будем рассуждать с конца. Число 31 нечетное, поэтому его нельзя получить умножением на 2: последней была команда «прибавь 3», до нее было $31 - 3 = 28$. Число 28 получается удвоением 14, 14 — удвоением 7. Число 7 нечетное, его дает команда «прибавь 3» из 4, а 4 — это удвоенное 2. Получаем команды 2, 1, 2, 2, 1.
Проверим алгоритм 21221:
2 → умножь на 2 → 4
4 → прибавь 3 → 7
7 → умножь на 2 → 14
14 → умножь на 2 → 28
28 → прибавь 3 → 31
Получили 31 за 5 команд. Другого алгоритма не длиннее 5 команд нет.