Question

На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число следующим образом:

1. Строится двоичная запись числа $N$.
2. К этой записи дописывается справа два нуля, если число чётное, или две единицы, если число нечётное.

Укажите максимальное число $N$, после обработки которого с помощью этого алгоритма получается число менее 94. В ответе это число запишите в десятичной системе.

Accepted Answer

22

Answer

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

Проверим числа, начиная с 93 и спускаясь вниз, какие из них могут быть результатом работы алгоритма (то есть заканчиваются на 00 или 11 в двоичной записи):

- $93_{10} = 1011101_2$ — заканчивается на 01, не подходит.
- $92_{10} = 1011100_2$ — заканчивается на 00, подходит.
- $91_{10} = 1011011_2$ — заканчивается на 11, подходит.
- $90_{10} = 1011010_2$ — заканчивается на 10, не подходит.
- $89_{10} = 1011001_2$ — заканчивается на 01, не подходит.
- $88_{10} = 1011000_2$ — заканчивается на 00, подходит.

Максимальное число, меньшее 94, которое может быть результатом алгоритма — это 92 или 91. Проверим 92:

Если результат $92_{10} = 1011100_2$, то исходное число получается удалением последних двух нулей: $10111_2 = 23_{10}$. Проверка: 23 — нечётное, должны добавиться 11, получим $1011111_2 = 95_{10}$ ≠ 92. Противоречие.

Проверим 91:

Если результат $91_{10} = 1011011_2$, то исходное число получается удалением последних двух единиц: $10110_2 = 22_{10}$. Проверка: 22 — чётное, должны добавиться 00, получим $1011000_2 = 88_{10}$ ≠ 91. Противоречие.

Проверим 88:

Если результат $88_{10} = 1011000_2$, то исходное число получается удалением последних двух нулей: $10110_2 = 22_{10}$. Проверка: 22 — чётное, добавляем 00, получим $1011000_2 = 88_{10}$. ✓

Альтернативное решение на Python:

```python
for i in range(100, 0, -1):
    s = bin(i)[2:]
    if i % 2 == 0:
        s += "00"
    else:
        s += "11"
    r = int(s, 2)
    if r < 94:
        print(i)
        break
```

Программа перебирает числа от 100 вниз, применяет алгоритм и выводит первое число, для которого результат меньше 94.

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