Двоичные алгоритмы в ЕГЭ: дописывание битов и решение на Python

Число N и его двоичная запись — разные вещи

Число 6 записывается как 110 в двоичной системе. Когда справа дописывают 01, получается строка 11001. Её десятичное значение — 25. Это не сложение 6 и 1.

Если перевод пока вызывает трудности, начните с разрядов двоичной системы.

Условие учебного алгоритма

Авторский пример: натуральное число N находится в диапазоне от 1 до 100 включительно. Алгоритм строит R:

1. Записывает N в двоичной системе без ведущих нулей.
2. Если исходное N чётное, дописывает справа 01.
3. Если исходное N нечётное, дописывает слева 1, а справа 0.
4. Переводит новую запись в десятичную систему.

Чётность проверяем у исходного числа N. В других задачах могут спрашивать чётность числа единиц или сумму цифр: это другое условие.

Два примера по шагам

Знак «+» во второй строке означает соединение строк. Заметьте: большее N здесь даёт меньшее R. Значения R не обязаны возрастать вместе с N.

Как записать преобразование на Python

def transform(n):
    s = bin(n)[2:]
    if n % 2 == 0:
        s = s + "01"
    else:
        s = "1" + s + "0"
    return int(s, 2)

print(transform(6))  # 25
print(transform(5))  # 26

• bin(n) возвращает строку с префиксом 0b; для положительного N срез [2:] оставляет цифры.
• n % 2 == 0 проверяет чётность числа.
• int(s, 2) читает строку как двоичную запись.

Код можно проверить в Python онлайн. Сначала посчитайте два примера вручную.

Минимальное N и минимальное R: не перепутайте

Для нашего диапазона 1 ≤ N ≤ 100 найдём наименьшее R, которое больше 55. На N = 13 получаем R = 58, а на N = 14 — R = 57. Поэтому остановиться на первом подходящем N нельзя.

results = []
for n in range(1, 101):
    r = transform(n)
    if r > 55:
        results.append((r, n))

if results:
    r, n = min(results)
    print(r)  # 57
    print(n)  # 14

Кортежи начинаются с R, поэтому min сначала сравнивает результаты. Если спросили наименьшее N, ответ для этого условия — 13. Если нужно R, ответ — 57.

Диапазон 1–100 здесь дан в условии. В другой задаче нельзя выбирать границу перебора наугад: её нужно взять из условия или обосновать.

Быстрая проверка без программы

Дописывание двух бит справа сдвигает исходное число на два разряда: умножает его на 4. Биты 01 добавляют 1. Для чётного N в нашем примере R = 4N + 1.

Для нечётного N пусть k — длина двоичной записи. Добавленная единица слева даёт 2^k+1, а ноль справа умножает исходное N на 2. Получаем R = 2^k+1 + 2N. При N = 5: k = 3, R = 16 + 10 = 26.

Это формулы именно для нашего правила. Если суффикс или префикс изменились, расчёт тоже меняется.

Ошибки, которые стоит проверить перед ответом

• Не оставлен ли префикс 0b внутри изменённой записи?
• Проверяется чётность N или количество единиц — как написано в условии?
• Биты дописываются с правильной стороны?
• В условии «больше» или «не меньше»?
• Спрашивают N или R? Есть ли обоснование диапазона перебора?

Правила bin и int: официальная документация Python. Формат экзамена сверяйте с материалами ФИПИ для нужного года. Примеры на этой странице авторские, не официальный вариант экзамена.

Проверьте себя

Сначала решите самостоятельно. Затем проверьте ответ или откройте объяснение.