Задание 8: учимся решать перебором на Python

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

В задачах из этой шпаргалки нужно составлять слова или записи чисел, отбирать подходящие варианты и находить ответ. product берёт перебор на себя. Твоя работа — выбрать алфавит, длину и точно записать ограничения.

Номер в списке или количество подходящих?

Переводим условие в код

Почему product, а не permutations

product('АБ', repeat=3) выдаёт ААА, ААБ, АБА, АББ, БАА, БАБ, ББА, БББ. Повторы букв разрешены. permutations('АБВ', 3) переставляет три имеющихся элемента без повторного использования: АБВ, АВБ, БАВ и так далее. Выбирай по условию, можно ли брать букву заново. Если исходный набор сам содержит одинаковые буквы, permutations может выдавать одинаковые строки.

Для трёх разборов ниже достаточно from itertools import product. Это тот же product, что и при импорте * в шпаргалке. Все варианты перебирать вручную и писать шесть вложенных циклов не нужно.

АПРЕЛЬ: собираем условия в один if

1. Задаём полный список

sorted('АПРЕЛЬ') даёт А, Е, Л, П, Р, Ь. В product первой меняется последняя позиция. Поэтому начало списка: АААААА, АААААЕ, АААААЛ, АААААП, АААААР, АААААЬ, ААААЕА.

2. Нумеруем каждое слово

number = 0
for word in product(sorted('АПРЕЛЬ'), repeat=6):
    s = ''.join(word)
    number += 1
    # Только теперь проверяем s и number

До цикла number = 0. Для первого слова сначала выполняется number += 1, поэтому его номер равен 1. Прибавление стоит на одном уровне с if: неподходящие слова тоже занимают места в исходном списке.

3. Соединяем четыре ограничения

Нужны все четыре свойства одновременно, значит соединяем их через and. Запись s[0] != 'А' or s[0] != 'Л' ошибочна: она пропустит любую первую букву, ведь одна буква не может одновременно быть и А, и Л.

4. Печатаем первое совпадение

from itertools import product

number = 0
for word in product(sorted('АПРЕЛЬ'), repeat=6):
    s = ''.join(word)
    number += 1
    if (s[0] != 'А' and s[0] != 'Л'
            and s.count('П') >= 2 and number % 2 == 1):
        print(number)
        break

break останавливает перебор сразу после ответа. Это допустимо: список уже идёт в нужном порядке, все предыдущие слова проверены. В шпаргалке программа печатает все подходящие номера; здесь добавлена остановка после первого, который и требуется.

Что происходит перед ответом

Номер слова растёт всегда, count — только после отбора

Небольшой список: трёхбуквенные слова из А и Б. Требование — ровно две Б. Нажимай «Следующее слово» и следи за двумя разными числами.

Первое подходящее слово АББ имеет номер 4. Всего подходящих слов 3. Если перенести number += 1 внутрь if, номер АББ превратится в 1 — это уже нумерация отобранных слов, которой в условии нет.

Пять цифр, ровно один ноль и ограничения соседей

1. Перечисляем допустимые цифры и длину

Девятеричная запись использует цифры 012345678. Пять разрядов задаёт repeat=5. Но product создаст и строки вида 02468: это ещё не пятизначное число. Поэтому добавляем s[0] != '0'.

2. Проверяем число нулей до проверки соседей

if s.count('0') == 1 and s[0] != '0':
    # Здесь ровно один 0, а первая цифра не 0

== 1 означает ровно один ноль. Условие >= 1 разрешило бы два и больше. Нули не нужны в отдельной переменной: s.count('0') считает их в текущей строке.

3. Заменяем нечётные цифры одним символом

Нечётные цифры в этом алфавите — 1, 3, 5, 7. Заменим их на * и сохраним в отдельной строке masked. Исходное s останется доступным для проверки и отладки.

'0*' not in masked запрещает нечётного соседа справа; '*0' not in masked — слева. Объединяем через and, чтобы запрет действовал в обе стороны. Проверка '**' not in masked здесь не нужна: нечётные цифры могут стоять рядом друг с другом.

4. Считаем только прошедшие все проверки числа

from itertools import product

count = 0
for word in product('012345678', repeat=5):
    s = ''.join(word)
    if s.count('0') == 1 and s[0] != '0':
        masked = s.replace('1', '*').replace('3', '*').replace('5', '*').replace('7', '*')
        if '0*' not in masked and '*0' not in masked:
            count += 1
print(count)

count += 1 находится внутри двух if. print(count) стоит после цикла без отступа: нужен итог для всех чисел. break здесь не ставим, иначе посчитаем только часть вариантов. Переводить s в десятичное число не требуется: все ограничения относятся к цифрам записи.

Проверяем соседние цифры через индексы

Можно обойтись без замены. Последовательно проверяем пары s[i] и s[i + 1]. Плохая пара — ноль и нечётная цифра в любом порядке.

В пятизначной строке четыре соседние пары, поэтому цикл range(len(s) - 1) даёт i от 0 до 3. Если взять range(len(s)), последний i = 4 приведёт к обращению к несуществующему s[5].

from itertools import product

count = 0
for word in product('012345678', repeat=5):
    s = ''.join(word)
    if s.count('0') == 1 and s[0] != '0':
        bad_pairs = 0
        for i in range(len(s) - 1):
            if ((s[i] in '1357' and s[i + 1] == '0') or
                    (s[i + 1] in '1357' and s[i] == '0')):
                bad_pairs += 1
        if bad_pairs == 0:
            count += 1
print(count)

Два направления плохой пары соединены через or: достаточно встретить «нечётная → 0» либо «0 → нечётная». Внутри каждого направления стоит and, потому что оба свойства пары должны выполняться.

bad_pairs = 0 создаём заново для каждого s. Если после просмотра всех соседей он остался равен 0, увеличиваем общий count. В шпаргалке этот внутренний счётчик назван number; здесь он переименован, чтобы не путать его с номером слова.

Почему запись проходит или не проходит отбор

Тренажёр проверяет условие пятизначного девятеричного примера. Введи запись цифрами 0–8: увидишь замену нечётных цифр, все четыре соседние пары и причины отказа.

Как найти ВОРОТА в алфавитном списке

Алфавит здесь АВОРТ, длина 6. Снова нужен номер каждой строки, поэтому number растёт перед if. Вместо набора ограничений достаточно сравнения s == 'ВОРОТА'.

from itertools import product

number = 0
for word in product(sorted('АВОРТ'), repeat=6):
    s = ''.join(word)
    number += 1
    if s == 'ВОРОТА':
        print(number)
        break

Если в новой задаче нужно найти слово по его номеру, меняется только проверка: if number == нужный_номер:, затем print(s) и break. Если нужен последний подходящий номер, ранняя остановка уже не годится: придётся просмотреть весь список и запомнить последнее совпадение.

Собери три программы и проверь результат

В этих примерах изменены алфавиты и длины. Сначала впиши выражения в пропуски, потом запусти собранный код в своём редакторе Python и введи полученный ответ. Для работы с чистого листа скачай условия из учебного архива ниже.

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

Решено: 0 из 12

from itertools import product

number = 0
for word in product(⟦1⟧, repeat=⟦2⟧):
    s = ⟦3⟧
    number += 1
    if ⟦4⟧ and ⟦5⟧ and ⟦6⟧:
        print(number)
        break

from itertools import product

count = 0
for word in product('0123456', repeat=⟦1⟧):
    s = ''.join(word)
    if ⟦2⟧ and ⟦3⟧:
        masked = ⟦4⟧
        if ⟦5⟧ and ⟦6⟧:
            count += 1
print(count)

from itertools import product

number = ⟦1⟧
for word in product(⟦2⟧, repeat=⟦3⟧):
    s = ⟦4⟧
    number = ⟦5⟧
    if s == ⟦6⟧:
        print(number)
        break

Девять коротких проверок понимания

Ответ можно исправить и проверить повторно.

Скачать код и задания для практики в Python

Порядок работы: прочитай вопрос → выбери number или count → задай алфавит и длину → перенеси каждое ограничение в if → проверь один вариант вручную → запусти полный перебор.

Если ответ не совпадает

Для поиска ошибки временно выводи print(number, s) перед if в задаче о номере. В задаче о соседях проверь одну строку из таблицы: выведи s и masked либо bad_pairs. Затем убери отладочную печать и оставь только ответ.

Вопросы по заданию 8