Разборы · ЕГЭ, задание 8

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

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

В задании 8 составляют слова (или числа) из заданных букв и считают, сколько их, или находят номер слова в алфавитном списке. 1 балл. Большинство вариантов быстрее и надёжнее решить перебором на Python.

Что нужно знать

• Число слов длины n из алфавита мощностью m — mⁿ. Если буквы не повторяются — m · (m − 1) · … (n множителей).
• itertools.product(letters, repeat=n) перебирает все слова длины n. Если буквы в letters отсортированы, слова идут в алфавитном порядке — как в списке из условия.
• itertools.permutations(letters) — слова без повторения букв.
• enumerate(…, start=1) даёт номер слова в списке, начиная с 1.

Как решать

1. Отсортируйте буквы: sorted("АКЦЕНТ"). Сверьте начало списка с условием.
2. Переберите слова через product, пронумеровав их.
3. Проверьте условия и выведите нужное: номер, количество или само слово.

Пример из демоверсии 2027

Все пятибуквенные слова из букв А, К, Ц, Е, Н, Т записаны в алфавитном порядке и пронумерованы (1. ААААА, 2. ААААЕ, 3. ААААК, …). Под каким номером стоит первое слово с чётным номером, которое не начинается с А, Е или К и содержит хотя бы одну букву Т?

from itertools import product

letters = sorted("АКЦЕНТ")                   # А Е К Н Т Ц
for i, w in enumerate(product(letters, repeat=5), start=1):
    if i % 2 == 0 and w[0] not in "АЕК" and "Т" in w:
        print(i, "".join(w))                 # 3914 НААТЕ
        break

Ответ: 3914. Проверим рассуждением. Алфавитный порядок: А, Е, К, Н, Т, Ц. Слов на А, Е и К — 3 · 6⁴ = 3888, поэтому первое слово на Н — НАААА — имеет номер 3889. Пока буква Т стоит только на последнем месте, номер слова равен 3889 + 6k + 4 — он всегда нечётный. Первое слово с Т на четвёртом месте — НААТА под номером 3889 + 4 · 6 = 3913 (нечётный), а следующее за ним НААТЕ стоит под номером 3914.

Решение на экзамене не проверяется — засчитывается только число в поле ответа, так что перебор здесь честный и самый надёжный путь.

Типичные ошибки

• Не сортируют буквы и получают неалфавитный порядок: product("АКЦЕНТ", …) идёт в порядке А, К, Ц…
• Нумеруют с нуля: enumerate по умолчанию начинает с 0.
• Путают «первое слово, удовлетворяющее условию» и «количество таких слов».

Потренироваться: задание 8 новые варианты с проверкой ответа