Question

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

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

Первая команда увеличивает число на экране на 2, вторая утраивает его. Например, программа **21211** преобразует число 1 в число 19:

$$1 \xrightarrow{	ext{команда 2}} 3 \xrightarrow{	ext{команда 1}} 5 \xrightarrow{	ext{команда 2}} 15 \xrightarrow{	ext{команда 1}} 17 \xrightarrow{	ext{команда 1}} 19$$

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

Accepted Answer

11212

Answer

Идея решения: проследим преобразование в обратном направлении — от 69 к 3, определяя на каждом шаге, какая команда была применена.

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

Проследим от 69 к 3:

| Текущее число | Операция | Предыдущее число | Команда |
|---|---|---|---|
| 69 | $69 = 23 	imes 3$ | 23 | 2 |
| 23 | $23 = 21 + 2$ | 21 | 1 |
| 21 | $21 = 7 	imes 3$ | 7 | 2 |
| 7 | $7 = 5 + 2$ | 5 | 1 |
| 5 | $5 = 3 + 2$ | 3 | 1 |

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

Записав их в прямом порядке (от начала к концу): **11212**.

Проверка: $3 \xrightarrow{1} 5 \xrightarrow{1} 7 \xrightarrow{2} 21 \xrightarrow{1} 23 \xrightarrow{2} 69$ ✓

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