Question

У исполнителя Удвоитель две команды, которым присвоены номера:

1. прибавь 1
2. умножь на 2

Первая команда увеличивает число на экране на 1, вторая удваивает его. Например, программа 2121 преобразует число 1 в число 7.

Запишите порядок команд в программе преобразования числа 4 в число 94, содержащей не более 8 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.

Accepted Answer

12121212

Answer

Идея решения: пойти от конечного числа 94 к начальному числу 4 в обратном направлении, восстанавливая команды.

Обратный ход работает так: если число нечётное, то перед ним была команда 1 (прибавь 1), поэтому отнимаем 1. Если число чётное, то могла быть команда 2 (умножь на 2), поэтому делим на 2. Восстановленные команды записываются в обратном порядке.

Проследим преобразование от 94 к 4:

| Текущее число | Операция | Команда |
|---|---|---|
| 94 | делим на 2 | 2 |
| 47 | отнимаем 1 | 1 |
| 46 | делим на 2 | 2 |
| 23 | отнимаем 1 | 1 |
| 22 | делим на 2 | 2 |
| 11 | отнимаем 1 | 1 |
| 10 | делим на 2 | 2 |
| 5 | отнимаем 1 | 1 |
| 4 | — | — |

Последовательность команд в обратном порядке: 12121212.

Проверка: $4 	o 5 	o 10 	o 11 	o 22 	o 23 	o 46 	o 47 	o 94$ ✓

Задание №5Системы счисления и арифметикаЕГЭ по информатике