Задание 5 ЕГЭ по информатике: алгоритм с двоичной записью
В пятом задании ЕГЭ по информатике описан алгоритм: число N переводится в двоичную систему, к записи по правилу дописываются цифры, результат переводится обратно в число R. Нужно найти наименьшее N, при котором R больше заданного, или наоборот. Перебор на Python решает такие задачи надёжнее всего.
Для 10–11 классов. Нумерация по проекту демоверсии ФИПИ на 2027 год.
Разбор примера
Алгоритм: строится двоичная запись N. Если сумма её цифр чётная, справа дописывается 0, иначе 1. Затем то же повторяется для новой записи. Получается число R.
Наименьшее N
Найдите наименьшее N, при котором R больше 40.
После первого шага сумма цифр всегда становится чётной: к нечётной сумме дописали 1. Значит, второй шаг всегда дописывает 0.
R = 4N + 2p, где p равно 1, если у N нечётная сумма цифр. При N = 10 (1010, сумма 2) R = 40, этого мало.
N = 11 (1011, сумма 3): R = 44 + 2 = 46 > 40.
Ответ: 11
Программа
for n in range(1, 1000): b = bin(n)[2:] b += str(b.count('1') % 2) b += str(b.count('1') % 2) r = int(b, 2) if r > 40: print(n) break
bin(n)[2:] даёт двоичную запись без префикса 0b, int(b, 2) переводит обратно. Если нужно наименьшее R, а не N, перебирайте N и храните минимум из подходящих R.
Частые варианты правил
- Дописать остаток от деления суммы цифр на 2 (как в примере).
- Если число чётное, дописать в конец 0, иначе в начало 1.
- Дописать в конец две последние цифры записи.
- Заменить первую единицу на 10 и так далее.
Каким бы ни было правило, программа строится одинаково: работаем со строкой двоичной записи, применяем правило буквально, как в условии, переводим обратно.
Проверь себя
- Какое R получится для N = 5 по алгоритму из примера? Ответ: 20 (101, сумма 2: дописываем 0 и ещё 0, 10100).
- Чему равно int('101110', 2)? Ответ: 46.
Где теряют балл
- Не та сумма цифр. На втором шаге сумма считается по новой записи, с дописанной цифрой.
- Строгое и нестрогое. «Больше 40» и «не меньше 40» дают разные ответы.
Как тренироваться
Системы счисления подробно в статье системы счисления. Все номера экзамена в статье ЕГЭ по информатике по номерам.
Разберём на занятии
Готовим к ОГЭ и ЕГЭ на живых занятиях в мини-группе до шести человек или один на один, с пробниками в формате экзамена и разбором каждой ошибки.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.
Частые вопросы
Можно ли решить без программы?
Да, как в примере, но для сложных правил ручной анализ дольше и рискованнее.
Сколько баллов?
Один первичный балл.