Koddo
начать бесплатно

Задание 8 ЕГЭ по информатике на Python: перебор слов через itertools

опубликовано
читать
≈ 4 мин
автор
среда и версия
Python 3.14.2 в браузере (Pyodide 314.0.3) — там же, где запускаются примеры на странице; вывод совпал с CPython 3.14.7
содержание решать задачи Python для начинающих

В задании 8 ЕГЭ по информатике считают слова или числа, которые можно составить по правилу: из заданных букв, перестановкой букв слова или из цифр какой-то системы счисления. Иногда слова выписывают по алфавиту и спрашивают номер нужного. Руками такой перебор долгий, и в нём легко сбиться, а на Python варианты выдаёт модуль itertools: product — слова, в которых буквы повторяются, permutations — перестановки. Примеры ниже запускаются прямо на странице и составлены для этой статьи: на экзамене буквы и условия будут другими, а шаблоны — те же.

ЕГЭ / 01

Номер слова в списке — четверичное число плюс один

Номер слова в списке — четверичное число плюс одинБуквы Л, О, Т, У записаны по алфавиту, поэтому их можно считать цифрами 0, 1, 2, 3. Тогда каждое слово — запись числа в четверичной системе, а номер слова — это число плюс один. ЛЛЛЛЛ — 00000, номер 1; ЛЛЛЛО — 00001, номер 2; ЛЛЛОЛ — 00010, то есть 4, номер 5. Слово ТЛЛОО — запись 20011, и int('20011', 4) + 1 = 518.1 · буквы по алфавиту — цифрыЛ О Т У→0 1 2 32 · слово — четверичная запись, номер — запись + 1номерсловозаписьпочему1ЛЛЛЛЛ000000 + 1 = 12ЛЛЛЛО000011 + 1 = 25ЛЛЛОЛ000104 + 1 = 5………518ТЛЛОО20011int('20011', 4) + 1 = 518
product перебирает слова в том же порядке, в каком растут четверичные числа. Поэтому номер, который нашёл цикл, проверяется вторым способом: int('20011', 4) + 1 даёт те же 518.

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

Все пятибуквенные слова из букв Л, О, Т, У записаны в алфавитном порядке и пронумерованы с единицы. Начало списка:

  1. ЛЛЛЛЛ
  2. ЛЛЛЛО
  3. ЛЛЛЛТ
  4. ЛЛЛЛУ
  5. ЛЛЛОЛ

Под каким номером стоит первое слово, которое начинается с буквы Т и содержит ровно две буквы О?

Решение

from itertools import product

words = [''.join(w) for w in product('ЛОТУ', repeat=5)]
print(words[:5])

first = last = None
for number, word in enumerate(words, 1):
    if word[0] == 'Т' and word.count('О') == 2:
        if first is None:
            first = number
        last = number
print(first, last)
['ЛЛЛЛЛ', 'ЛЛЛЛО', 'ЛЛЛЛТ', 'ЛЛЛЛУ', 'ЛЛЛОЛ']
518 758
  • product('ЛОТУ', repeat=5) выдаёт все 4⁵ = 1024 набора по пять букв. Буквы в строке записаны по алфавиту, поэтому и слова идут по алфавиту: первая строка вывода совпадает с началом списка из условия.
  • ''.join(w) склеивает набор букв в слово.
  • enumerate(words, 1) нумерует с единицы, как в условии.
  • word.count('О') == 2 — ровно две буквы О. «Не меньше двух» было бы >= 2.
  • first запоминает первое подходящее слово, а last перезаписывается до конца списка: так находят последнее, если спрашивают о нём.

Ответ: 518.

Проверка вторым способом

Буквы Л, О, Т, У можно считать цифрами 0, 1, 2, 3 четверичной системы, и список слов идёт в том же порядке, что и числа: номер слова — это его четверичная запись плюс один (схема выше).

word = 'ТЛЛОО'
digits = word.translate(str.maketrans('ЛОТУ', '0123'))
print(digits, int(digits, 4) + 1)
20011 518

str.maketrans задаёт таблицу замены, а translate меняет по ней буквы на цифры. Номер совпал с найденным перебором. Так же решают и обратный вопрос «какое слово стоит под номером N»: N − 1 переводят в четверичную запись и меняют цифры на буквы.

Перестановки букв слова

В другом виде задания слова получают перестановкой букв данного слова. Например: сколько различных слов можно составить из букв слова ПАСТА, если две буквы А не должны стоять рядом?

from itertools import permutations

words = set(permutations('ПАСТА'))
good = [w for w in words if 'АА' not in ''.join(w)]
print(len(words), len(good))
60 36

permutations переставляет буквы как разные предметы: две буквы А для неё различны, и каждое слово получается дважды. set оставляет по одному. Проверка формулой: всего слов 5! / 2! = 60, слов, где АА стоят рядом, — 4! = 24 (АА как одна буква), и 60 − 24 = 36.

Числа в другой системе счисления

Сколько существует четырёхзначных чисел в восьмеричной системе счисления, в записи которых ровно одна цифра 7?

from itertools import product

count = 0
for w in product('01234567', repeat=4):
    if w[0] != '0' and w.count('7') == 1:
        count += 1
print(count)
1225

Запись числа не начинается с нуля — отсюда w[0] != '0'. Проверка формулой: если 7 стоит первой, остальные три цифры — любые из семи, кроме 7: 7³ = 343. Если 7 не первая, первая цифра — одна из шести (от 1 до 6), место для 7 — одно из трёх, две оставшиеся цифры — из семи: 6 · 3 · 7² = 882. Всего 343 + 882 = 1225.

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

Буквы не по алфавиту. product перебирает буквы в том порядке, в каком они записаны в строке: product('ТОЛУ', repeat=5) начнёт с ТТТТТ, и номера разойдутся со списком из условия. Записывай буквы по алфавиту и сверяй начало списка, как в решении выше.

Нумерация с нуля. enumerate(words) без второго аргумента считает с нуля и даст 517 вместо 518.

Перестановки без set. Для слова ПАСТА без set получится 72 вместо 36: каждое слово посчитано дважды.

Ведущий ноль. Без проверки w[0] != '0' в подсчёт попадут записи вроде 0712, и ответ выйдет 1372 вместо 1225.

Какие ещё задания решают программой — в статье «Python для ЕГЭ по информатике», задание 5 о двоичной записи — в статье «Задание 5 ЕГЭ на Python». Свой вариант задания удобно проверять в песочнице Python: там можно вывести весь список слов и посмотреть, где начинается нужная буква.

Источники