Задание 5 ЕГЭ по информатике: алгоритмы с двоичной записью числа — разбор и примеры

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

На компьютерном ЕГЭ это задание надёжнее всего решать перебором: запрограммировать алгоритм буквально и перебрать N. Но понимать, как алгоритм меняет длину и значение числа, всё равно нужно — чтобы правильно выбрать границы перебора и проверить себя.

Что проверяет задание

• умение переводить числа между системами счисления и работать с записью числа как со строкой;
• умение точно исполнить алгоритм, заданный словесно;
• понимание, как дописывание цифр справа влияет на значение: дописать к двоичной записи k цифр — то же, что умножить число на 2 в степени k и прибавить значение дописанных цифр.

Типичные формулировки

1. «Укажите минимальное число N, после обработки которого получится R, большее 150».
2. «Укажите минимальное значение R, большее 200, которое может получиться в результате работы алгоритма».
3. «Сколько различных чисел R из отрезка [A; B] может быть получено?»
4. Вариант с троичной или четверичной записью: те же вопросы, но перевод в другую систему.

Обратите внимание на различие вопросов 1 и 2: в первом ищем наименьшее N, во втором — наименьшее R. Это разные числа, и наименьшее подходящее R может получиться вовсе не из наименьшего N.

Пошаговый метод

1. Перепишите алгоритм по пунктам, отметив все условия (чётность, делимость, сумма цифр) и что именно дописывается — цифры, их количество, слева или справа.
2. Проверьте на маленьком числе вручную, например N = 12 или 13: это защитит от неверного понимания условия.
3. Запрограммируйте функцию R(N), работая со строкой: bin(n)[2:] для двоичной записи, int(s, 2) для обратного перевода.
4. Переберите N с запасом (до нескольких тысяч) и ответьте на вопрос. Для вопроса о наименьшем R перебирайте все N и берите минимум среди подходящих R.
5. Оцените результат: длина записи R и порядок величины должны соответствовать ожиданиям.

Разбор примера

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

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

Проверка вручную. N = 13 = 1101₂, остаток от деления на 3 равен 1, утроенный остаток 3 = 11₂, получаем 110111₂ = 55. N = 12 = 1100₂ делится на 3, дописываем последние три цифры 100: 1100100₂ = 100.

Вопрос 1. Укажите минимальное N, при котором R > 150.

Дописывание двух или трёх цифр примерно умножает N на 4 или на 8, поэтому искать нужно среди N от 16 до 40. Перебор даёт: R(16) = 67, R(17) = 142, R(18) = 146, R(19) = 79, R(20) = 166. Число 20 = 10100₂ при делении на 3 даёт остаток 2, дописываем 110 и получаем 10100110₂ = 166.

Ответ: 20.

Вопрос 2. Укажите минимальное значение R, большее 200.

Здесь удобно рассуждать по длине записи. Число от 201 до 255 имеет 8 двоичных цифр. Восьмизначный R получается двумя способами: из пятизначного N, к которому дописаны три цифры (N делится на 3 или даёт остаток 2), или из шестизначного N с остатком 1, к которому дописано 11.

• Первый способ: R ≥ 8N, нужно 8N > 200, то есть N ≥ 26. N = 26 даёт остаток 2: 11010110₂ = 214.
• Второй способ: R = 4N + 3, нужно 4N + 3 > 200, то есть N ≥ 50. Остаток 1 впервые у N = 52: R = 211.

Меньшее из двух — 211, хотя оно получается из большего N. Ответ: 211.

Код на Python

def R(n):
    s = bin(n)[2:]                     # двоичная запись N
    if n % 3 == 0:
        s = s + s[-3:]                 # дописываем три последние цифры
    else:
        s = s + bin(3 * (n % 3))[2:]   # дописываем запись утроенного остатка
    return int(s, 2)

print(min(n for n in range(4, 1000) if R(n) > 150))        # 20
print(min(R(n) for n in range(4, 1000) if R(n) > 200))     # 211

Шаблон подходит почти для любого варианта: меняется только тело функции R. Для троичной записи понадобится своя функция перевода, например:

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

Обратный перевод — int(s, 3).

Полезные наблюдения

Дописывание к двоичной записи числа N справа k цифр, образующих число d, даёт N · 2^k + d. Поэтому R растёт примерно пропорционально N, но со «скачками»: при переходе к другому остатку меняется количество дописываемых цифр. Именно из-за таких скачков последовательность R не монотонна — в нашем примере R(19) = 79 меньше, чем R(18) = 146. Отсюда правило: никогда не останавливайте перебор на первом подходящем N, если спрашивают о наименьшем R, и всегда берите диапазон перебора с большим запасом.

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

• Путают «наименьшее N» и «наименьшее R». Во втором вопросе нужен минимум по значениям R, а не первое подходящее N.
• Слишком маленький диапазон перебора. Если перебрать N только до 50, во втором вопросе ответ 211 не найдётся, и вы ошибочно выберете 214.
• Ошибаются со срезами строк. s[-3:] — три последние цифры, s[:3] — три первые. Проверьте на ручном примере.
• Забывают, что дописывается запись числа, а не число. «Дописать 6» в двоичном алгоритме означает дописать 110.
• Пишут ответ в двоичной системе. Если не сказано иное, ответ записывается в десятичной системе.

Потренируйтесь

Проверьте себя на разных вариантах алгоритмов: задания № 5 в банке. Чтобы отработать сам код, решайте задачи с проверкой кода. Повторить переводы поможет статья «Системы счисления», а следующее задание — задание 6: исполнитель Черепаха.