Задание 5 ЕГЭ: от условия к решению на Python

Как решать задание 5 ЕГЭ на Python

Есть исходное число N. Алгоритм меняет его двоичную или троичную запись и получает новое число R. Программа повторяет эти действия для каждого N, оставляет подходящие результаты и выбирает ответ.

В шпаргалке разобраны три варианта. Начнём с вопроса задачи: он определяет последние строки программы.

Команды, которые нужны в этих трёх типах

s[2:] и s[-2:] берут разные части строки. Первое отбрасывает два символа слева; второе оставляет два символа справа. Если в строке 11 взять s[-3:], Python вернёт всю строку 11, без добавления ведущих нулей.

Общий каркас перебора

mas = []
for n in range(1, 1000):
    s = bin(n)[2:]
    # Здесь меняем s строго по условию
    r = int(s, 2)
    # Здесь проверяем R и сохраняем нужное число
# Здесь выбираем ответ после всего перебора

s создаём заново для каждого n. Преобразование записи и проверка R находятся внутри цикла. Итоговый print располагается после цикла, без отступа. range(1, 1000) проверяет N от 1 до 999; почему этого хватает именно в этих примерах, разберём после трёх решений.

Сумма цифр и замена двух первых разрядов

1. Проверяем чётность исходной записи

В двоичной системе сумма цифр равна числу единиц. Поэтому проверка из условия записывается s.count('1') % 2 == 0. Проверяем её до изменения s.

2. Выполняем изменения в нужном порядке

if s.count('1') % 2 == 0:
    s = s + '0'
    s = '10' + s[2:]
else:
    s = s + '1'
    s = '11' + s[2:]

После дописывания s[2:] берёт всё, что осталось правее первых двух символов. Приписываем слева 10 или 11 — так меняем два первых разряда, сохраняя остальную запись.

3. Прослеживаем одно N

4. Собираем полный перебор

mas = []
for n in range(1, 1000):
    s = bin(n)[2:]
    if s.count('1') % 2 == 0:
        s = s + '0'
        s = '10' + s[2:]
    else:
        s = s + '1'
        s = '11' + s[2:]
    r = int(s, 2)
    if r <= 19:
        mas.append(n)
print(max(mas))

Строка r = int(s, 2) превращает изменённую запись в число. Ограничение r <= 19 проверяет результат, а mas.append(n) сохраняет исходное N. Затем max(mas) выбирает наибольшее из всех подходящих N.

Дописываем последние цифры или запись остатка

1. Разделяем два правила

Проверяем делимость самого N, поэтому здесь n % 3. Количество единиц в записи больше не требуется.

2. Разбираем длинную строку по действиям

Если остаток равен 1, хвостом станет двоичная запись числа 3 — 11. Если остаток 2 — запись числа 6, то есть 110. Запись str((n % 3) * 3) не подходит: она даст десятичную цифру 3 или 6 вместо двоичной строки.

Для делящейся ветви возьми N = 12: 1100 + 100 = 1100100, поэтому R = 100. Хвост берётся из записи до изменения s.

3. Переводим вопрос задачи в последние строки

«Не меньше 200» означает R ≥ 200. В коде используем r >= 200. Минимальное N означает сохранение n и выбор min(mas).

mas = []
for n in range(1, 1000):
    s = bin(n)[2:]
    if n % 3 == 0:
        s = s + s[-3:]
    else:
        s = s + bin((n % 3) * 3)[2:]
    r = int(s, 2)
    if r >= 200:
        mas.append(n)
print(min(mas))

Тот же перебор в системе с основанием 3

1. Получаем троичную запись

Используем функцию из шпаргалки. Она возвращает строку, которую можно дополнять теми же приёмами:

def to_3(n):
    s = ''
    while n != 0:
        s = str(n % 3) + s
        n //= 3
    return s

Проследим to_3(15). Остаток от деления на 3 — очередная цифра. Добавляем её слева к уже собранной строке, затем делим число нацело на 3.

Функция вернула 120. Исходный n во внешнем цикле остался 15: деление меняло локальное число внутри функции. В этих примерах все вызовы to_3 получают положительные числа.

2. Меняем только нужные части второго шаблона

3. Проверяем две ветви вручную

4. Перебираем все N и сохраняем R

def to_3(n):
    s = ''
    while n != 0:
        s = str(n % 3) + s
        n //= 3
    return s

mas = []
for n in range(1, 1000):
    s = to_3(n)
    if n % 3 == 0:
        s = s + s[-2:]
    else:
        s = s + to_3((n % 3) * 5)
    r = int(s, 3)
    if r > 133:
        mas.append(r)
print(min(mas))

Почему здесь хватает range(1, 1000)

Число 1000 в шпаргалке — граница этих примеров. Для нового алгоритма её нужно проверять, особенно если ищешь максимальное N или минимальное R.

В первом типе при исходной длине k ≥ 2 получается k + 1 бит с единицей слева, поэтому R ≥ 2^k > N. Для N = 1 отдельно получается R = 3. В третьем типе дописывание непустого хвоста увеличивает положительное число.

Когда можно использовать break

Если N идут по возрастанию и требуется минимальное N, первое подходящее N уже является ответом. Это работает во втором типе. Если требуется минимальное R, значение R может уменьшиться при увеличении N, как в третьем типе. Останавливаться на первом подходящем N нельзя.

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

Пошагово выполни алгоритм для одного N

Выбери тип и N, затем переходи по шагам. На каждом шаге видно действие из Python, новую запись и проверку условия. Попробуй тип 1 с N = 12 и 4, тип 2 с N = 26 и 12, тип 3 с N = 15 и 5.

Собери три программы и проверь их вывод

В этих задачах изменены числовые границы. Заполни пропуски выражениями из разобранных шаблонов. Затем скопируй собранную программу в свой редактор Python, запусти и введи полученный ответ. Отдельные задания для написания с чистого листа есть в учебном архиве.

Кнопка «Проверить строки» сверяет фрагменты с разобранными шаблонами. Другой способ решения можно проверить запуском в Python и по итоговому ответу. Пробелы и вид обычных кавычек в полях не мешают проверке.

Решено: 0 из 12

mas = []
for n in range(1, 1000):
    s = ⟦1⟧
    if ⟦2⟧:
        s = s + '0'
        s = '10' + s[2:]
    else:
        s = s + '1'
        s = '11' + s[2:]
    r = ⟦3⟧
    if ⟦4⟧:
        mas.append(⟦5⟧)
print(⟦6⟧)

mas = []
for n in range(1, 1000):
    s = bin(n)[2:]
    if n % 3 == 0:
        s = s + ⟦1⟧
    else:
        s = s + ⟦2⟧
    r = ⟦3⟧
    if ⟦4⟧:
        mas.append(⟦5⟧)
print(⟦6⟧)

def to_3(n):
    s = ''
    while n != 0:
        s = str(n % 3) + s
        n //= 3
    return s

mas = []
for n in range(1, 1000):
    s = ⟦1⟧
    if n % 3 == 0:
        s = s + ⟦2⟧
    else:
        s = s + ⟦3⟧
    r = ⟦4⟧
    if r > 300:
        mas.append(⟦5⟧)
print(⟦6⟧)

Короткие задания на понимание кода

Попробуй ответить без запуска. Если ошибся, можно изменить ответ и проверить снова.

Скачать программы и задания для самостоятельной работы

В первом разборе операции выполнены в порядке исходного условия; во втором использовано точное сравнение «не меньше». Контрольные ответы трёх разборов: 12, 26, 141.

Как найти ошибку в решении

Для отладки временно добавь внутри цикла после вычисления r строку print(n, s, r). Сравни вывод для одного известного N с таблицей разбора. Когда преобразование совпало, убери диагностический вывод и оставь итоговый ответ.

Вопросы о решении задания 5 кодом