Задание 5 ЕГЭ по информатике на Python: двоичная запись числа

В задании 5 ЕГЭ по информатике автомат превращает число N в число R: строит двоичную запись N, дописывает к ней цифры по правилу и читает результат как новое число. Спрашивают обычно наименьшее N, при котором R больше заданного. Руками это перевод туда и обратно для каждого N подряд. На Python правило записывается функцией в несколько строк, а цикл перебирает N сам. Код ниже запускается прямо на странице. Пример задачи составлен для этой статьи, на экзамене правило будет другим, а шаблон — тот же.

ЕГЭ / 01koddo

Как программа получает R для N = 18

Пример задачи

Автомат получает на вход натуральное число N и строит по нему число R так:

1. Строится двоичная запись числа N.
2. Если N делится на 4, к записи справа дописываются две её первые цифры. Иначе к записи слева дописывается 1, а справа — 01.
3. Получившаяся запись — двоичная запись числа R.

Например, для N = 12 запись 1100 превращается в 110011, и R = 51. Найди наименьшее N, при котором R больше 200. Ответ запиши в десятичной системе.

Решение

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

print(r_of(12), r_of(17), r_of(18))
for n in range(1, 1000):
    if r_of(n) > 200:
        print(n)
        break

51 197 201
18

• bin(n)[2:] — двоичная запись без приставки 0b.
• s[:2] — две первые цифры записи, а s + s[:2] дописывает их справа.
• '1' + s + '01' дописывает цифры с двух сторон: строки складываются по порядку.
• int(s, 2) читает запись обратно как двоичное число.
• Первая строка вывода — проверка функции: R(12) = 51, как в условии. Без такой проверки ошибка в правиле даст уверенный неверный ответ.
• Цикл идёт по N с единицы, поэтому первое N, при котором R больше 200, — наименьшее, и break останавливает перебор.

Ответ: 18.

Когда спрашивают R, а не N

Другой частый вопрос — наименьшее R, большее 180, которое может получиться. Взять R у первого подходящего N тут нельзя:

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

for n in range(1, 1000):
    if r_of(n) > 180:
        print('первое N:', n, 'R =', r_of(n))
        break
print('наименьшее R:', min(r_of(n) for n in range(1, 1000) if r_of(n) > 180))
print('его даёт N =', [n for n in range(1, 1000) if r_of(n) == 195])

первое N: 17 R = 197
наименьшее R: 195
его даёт N = [48]

N = 17 — первое число, у которого R больше 180, но наименьшее R даёт N = 48: оно делится на 4 и идёт по другой ветке правила. R растёт не вместе с N, поэтому для вопроса про R перебирают все N с запасом и берут min.

Запаса до 1000 хватает с избытком: в обеих ветках справа дописываются хотя бы две цифры, значит, R не меньше 4·N, и уже при N больше 50 R больше 200.

Троичная и другие системы

В части вариантов автомат строит не двоичную, а троичную запись. Готовой функции для неё в Python нет, но перевод пишется в несколько строк: остаток от деления на основание — очередная цифра справа.

def to_base(n, base):
    s = ''
    while n > 0:
        s = str(n % base) + s
        n //= base
    return s

print(to_base(14, 3))
print(int('112', 3), int('1120', 3))

112
14 42

Обратно запись переводит та же int, только с основанием 3. Дописать справа ноль в троичной записи — то же, что умножить число на 3: 112 превращается в 1120, а 14 — в 42. Функция to_base годится для оснований до 10, для шестнадцатеричной записи есть готовая hex.

Частые ошибки

Ответ — N или R. Перечитай вопрос перед тем, как печатать: для порога 180 первое N даёт 197, а наименьшее R — 195. Если спрашивают N, печатай n, если R — r_of(n).

Мало перебрал. С range(1, 40) вопрос про наименьшее R даст 197 вместо 195: N = 48 в перебор не попадёт. Запас бери с оценкой, как выше, а не наугад.

Приставка 0b. Без среза [2:] строка начинается с 0b, и правило ломается: для N = 12 s[:2] вернёт 0b, а int остановится с ошибкой ValueError: invalid literal for int() with base 2: '0b11000b'.

Короткая запись. Если правило меняет два левых разряда, а у N = 1 разряд один, срез s[2:] вернёт пустую строку, и Python не предупредит. Проверь по условию, с какого N начинать перебор.

Какие ещё задания решают программой — в статье «Python для ЕГЭ по информатике», задание 2 о таблице истинности — в статье «Задание 2 ЕГЭ на Python». Свой вариант задания удобно проверять в песочнице Python: пошаговое выполнение покажет, как строится запись для одного N.