ЯдроКодаподготовка к экзаменам
Учебная платформа

Загружаем материалы

Подготавливаем материалы и навигацию по разделу.

Python для задач ЕГЭ: перебор и проверка условий

Автор: · Обновлено

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

Первое число по двум условиям

Найдём первое целое x от 100 до 999 включительно, которое делится на 17 и имеет сумму цифр 9.

def digit_sum(number):
    return sum(map(int, str(number)))


answer = None

for x in range(100, 1000):
    if x % 17 == 0 and digit_sum(x) == 9:
        answer = x
        break

print(answer)

Ожидаемый результат:

153

Число 153 делится на 17, а 1 + 5 + 3 равно 9. break гарантирует первое подходящее значение при возрастающем диапазоне.

Доказательство минимальности

Проверить только свойства 153 недостаточно: нужно убедиться, что меньших ответов нет. Это следует из возрастающего перебора без пропусков и остановки на первом совпадении. Для максимального значения можно идти в обратном направлении или сохранить последнее найденное.

Типичные ошибки — range(100, 999), который не включает 999, неверное объединение and/or и начальный answer = 0, неотличимый от настоящего результата. None явно означает «не найдено».

Варианты одного перебора

Найдите все числа от 100 до 300, которые делятся на 7, но не делятся на 5; сохраните их в список. Затем выведите количество и первый элемент. Отдельно найдите последнее такое число без хранения всего списка. Проверьте границы диапазона и сформулируйте, почему версия с break решает другую задачу.

Перебор без скрытых предположений

Вынесите критерий кандидата в функцию is_candidate(x) и проверьте её отдельно на границах диапазона. Основной цикл должен отвечать только за порядок перебора и выбор первого, последнего или всех ответов. Добавьте счётчик проверенных кандидатов и подтвердите, что break уменьшает работу при ранней находке. Затем запустите диапазон в обратном направлении и объясните, почему тот же break теперь находит максимальный ответ. Удалите счётчик из финального вывода, но сохраните тесты критерия. Такой дизайн отделяет ошибку формулы от ошибки границ range.

Практикум: перебор ЕГЭ с проверяемым критерием

Для диапазона целых вынесите сложный критерий в is_candidate(x) и проверьте его на обеих границах и рядом с ними. Основной цикл должен отвечать только за порядок перебора и выбор первого, последнего или всех решений. Добавьте счётчик проверенных кандидатов и сравните полный проход с ранним break. Запустите диапазон в обратном направлении: тот же ранний выход теперь отвечает другому вопросу. Перед большим диапазоном оцените число итераций и возможность сузить его математически.

Контрольная точка

Как доказать, что найден именно минимальный подходящий кандидат? Нужны правильный порядок обхода, истинность критерия для ответа и отсутствие более раннего подходящего значения.

Частые вопросы

Полный перебор всегда считается плохим решением?

Нет. Если ограничения небольшие, перебор прозрачен и надёжен. Он становится проблемой, когда число вариантов превышает разумный бюджет; тогда используют свойства задачи для сокращения пространства.

Источники