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

В условии этого задания всегда три части: алфавит из нескольких букв, длина слова и правило, по которому часть слов отсеивается. Спрашивают после этого одно из двух: сколько слов подходит либо какое место занимает названное слово, если все слова выписаны по алфавиту. Ответ — одно целое число. Проверяющая машина сравнивает его с эталоном буквально, поэтому разница в единицу превращает задание в ноль, и ошибаются здесь чаще всего именно на единицу.

Номер задания и его тему сверяйте с демоверсией 2027 года на сайте ФИПИ: статья описывает типы условий, которые держались в последних демоверсиях, и не пересказывает конкретный вариант. Общий порядок первой части экзамена разобран в статье карта заданий первой части, там же видно, где это задание стоит среди соседей. Проверяет оно умение подсчитывать объекты, то есть школьную комбинаторику, пересаженную на информатический материал: слова и коды.

Какие вопросы задают про слова

Условия отличаются друг от друга меньше, чем кажется. Вопросов в основном четыре:

• сколько слов заданной длины удовлетворяют правилу;
• под каким номером в алфавитном списке стоит названное слово;
• какое слово стоит на названном месте списка;
• сколько слов лежит между двумя названными.

«По алфавиту» означает порядок букв в алфавите языка, а не порядок, в котором их перечислили в условии. Если сказано «буквы К, А, Р, Т», то А идёт раньше К, и список начинается со слова из одних А. Пока читаешь внимательно, это очевидно, на пятом задании подряд это забывается. Есть тонкость и для тех, кто сортирует программой: буква Ё в кодировке стоит после Я, а в алфавите между Е и Ж. Попадётся она в условии или нет, решает год, но заглянуть в алфавит условия стоит.

Руками: правило произведения

На слово из четырёх мест, где каждая буква выбирается независимо, приходится столько вариантов, сколько букв в алфавите, умноженное само на себя четыре раза. Для алфавита из четырёх букв это 4 в четвёртой степени, то есть 256 слов. Дальше накладывается правило. Пусть надо найти слова длины четыре из букв А, К, О, Р, где буква А стоит ровно два раза. Места для двух А выбираются шестью способами (первое и второе, первое и третье, и так далее до третьего и четвёртого), а на двух оставшихся местах стоит любая из трёх прочих букв, то есть девять сочетаний. Итого 6 умножить на 9, получается 54.

Проверка у такой задачи есть всегда, и она бесплатная: разбейте все слова по числу букв А и сложите. Без А — 81 слово, ровно одна А — 108, ровно две — 54, ровно три — 12, четыре — одно. Сумма 81, 108, 54, 12 и 1 обязана дать 256, и она даёт. Если не даёт, ошибка в одном из слагаемых, и искать её нужно среди них, а пересчитывать всё заново незачем.

Ещё один приём ручного счёта нужен для условия «две одинаковые буквы подряд не стоят». Первую букву выбирают любую, то есть четырьмя способами, а каждую следующую — любую, кроме предыдущей, то есть тремя. Слово из пяти мест тогда допускает 4 умножить на 3 в четвёртой степени, это 324. Такие задачи решаются за минуту, пока видно устройство, и теряют на них время те, кто сразу садится за перебор.

Стоит запомнить, что у задания нет приложенных файлов: по перечню файлов, который сопровождает проект демоверсии 2027 года, они положены другим номерам, а здесь условие целиком на экране. Отсюда следует практическое правило, которое экономит минуты: сначала прикиньте на черновике, сколько слов вообще получается, и только потом решайте, считать руками или писать перебор. Прикидка занимает полминуты. Три-четыре строки на черновике, где выписаны размер алфавита, длина слова и общее число слов без правила, не дают принять миллион за тысячу и, наоборот, хорошо отсекают случаи, когда перебор заведомо не нужен.

Способ срабатывает, пока правило простое: «ровно», «не более», «начинается на», «соседние различны». Условия вроде «никакие две гласные не стоят рядом» руками считаются уже плохо, и тогда проще перебрать.

Номер слова как число

Одна задача решается красивее, чем кажется: найти номер слова в полном алфавитном списке без отсева. Возьмите алфавит А, Б, В и слова длины три. Замените буквы цифрами: А — 0, Б — 1, В — 2. Слово БАВ превращается в 102 по основанию три, то есть 1·9 + 0·3 + 2 = 11. Нумерация слов начинается с единицы, поэтому ответ 12. Проверьте перечислением: девять слов начинаются с А, затем БАА десятое, БАБ одиннадцатое, БАВ двенадцатое.

Когда в списке стоит отсев, нумерация меняется: номер слова теперь означает его место среди подошедших, и слова, отброшенные условием, в нём не участвуют. Это единственное место, где красивая арифметика с основанием не работает, и ловят на нём тех, кто применил её по привычке. Как отличить случай? Если в условии сказано «все слова записаны в алфавитном порядке», отсева нет. Если сначала слова отбирают по правилу, а потом нумеруют, отсев есть.

Принцип тот же, что в задачах на системы счисления: слово — это число в позиционной записи, где основание равно размеру алфавита. Обратная задача (найти слово по номеру) решается переводом номера минус один в систему по основанию, равному числу букв, и подстановкой букв вместо цифр. С отсевом эта красота ломается, и тогда нужна программа. Перевод чисел между системами как отдельное задание экзамена разбирается в статье про системы счисления в задании 14.

Программой: перебор всего

В Python все слова алфавита длины n выдаёт функция product из стандартного модуля itertools. Подключение — одна строка, from itertools import product, а вызов выглядит как product("АКОР", repeat=4): на выходе кортежи букв, и они идут именно в алфавитном порядке, если алфавит передан отсортированным. Каждый кортеж склеивается в слово через join, слово проверяется по условию, нужные считаются. Для вопроса про номер слова добавляется счётчик, который стартует с единицы, а перебор останавливается на нужном слове. Если в списке есть отсев, нумеруются только слова, прошедшие его: считать надо после проверки.

Размер перебора оценивается заранее: степень размера алфавита. Семь букв, слово из семи мест — 823 543 слова, это секунды. Десять на десять — десять миллиардов, и тут перебор не пройдёт, придётся считать руками или делить задачу на части.

Условие «две гласные не стоят рядом» в программе пишется короче, чем объясняется на словах. Проходим по слову и смотрим на каждую пару соседних букв, если обе гласные — слово не подходит. Гласные заранее собираются в одну строку, и проверка принадлежности делается обычным оператором in. Пары соседних букв получаются срезами слова: одним со второй буквы, другим — до предпоследней.

Путают чаще всего две функции. Product выдаёт слова, где буквы могут повторяться, permutations — только такие, где каждая буква использована не больше одного раза. Выбирается функция по тексту условия, и фраза «буквы в слове могут повторяться» или «каждая буква используется ровно один раз» это решает. Взяли не ту — ответ получится столь же уверенным и столь же неверным.

Порядок работы и четыре места, где съезжает единица

Программой я решал бы всё, где слов меньше нескольких миллионов, а руками считал только для проверки порядка величины. С этим можно спорить: ученик, у которого правило произведения в голове, управляется быстрее, чем пишет перебор. Ошибка в ручном счёте остаётся незаметной, ошибка в переборе видна: программу можно запустить на алфавите из двух-трёх букв и сверить с полным списком из десятка слов, выписанным на черновике. Поэтому для ученика, который выбирает один способ, я советую именно программу.

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

Четыре места повторяются из года в год. Первое — нумерация: ученик находит позицию слова в списке, считая от нуля, потому что так устроены индексы в Python, а в условии номера начинаются с единицы. Второе — слова «ровно», «не менее», «не более»: граница включается или нет, и это зависит от одного слова условия. Третье — порядок букв в алфавите, о котором шла речь выше, и четвёртое — неверно выбранная функция, product вместо permutations или наоборот. Все четыре исправляются привычкой выписать условие своими словами ещё раз и проверить решение на двух-трёх коротких словах, где ответ виден глазами.

Что делать, если ответ не получается

Различайте два случая. Первый: непонятно, откуда берётся именно 54 слова, когда вы ожидали 24 или 81, то есть путаются размещения, сочетания и перестановки. Это пробел в самой комбинаторике, возвращаться надо в алгебру, и на тему уйдёт пара занятий. Второй: идея ясна, но написать перебор не получается, и это уже пробел в программировании — циклы и строки. Он вернётся в других заданиях, поэтому закрывать его стоит раньше, чем искать ещё один вариант с комбинаторикой. Модуль itertools в школьных учебниках, насколько я знаю, не встречается вовсе, так что его приходится осваивать отдельно, а про соотношение школьного курса и экзамена написано в статье информатика в школе: что учить и в каком порядке.

Начать поиск:

• репетиторы по информатике для подготовки к ЕГЭ
• все репетиторы для подготовки к ЕГЭ

Остальные типы заданий первой половины работы собраны в разборе структуры экзамена. Следующее по теме задание с файлом — задание 9 про электронные таблицы.

Вопросы и ответы

Можно ли решить задание без Python, только на листе? Можно, если правило простое, как в примере с буквой А. Когда условие сложное, лист не спасёт: придётся выписывать слова вручную.

Что вводить в ответ? Одно целое число без пробелов и пояснений. Формат записи ответа проверьте в демоверсии: в информатике лишний знак делает верный ответ неверным.

Хватит ли времени на перебор в Python, если слов миллион? Хватит, миллион слов проверяется за секунды. Про десять миллиардов сначала надо подумать, потому что простым перебором они не пройдут.

Нужна ли комбинаторика, если у меня есть программа? Нужна для оценки размера: прежде чем запускать перебор, полезно знать, сколько там слов, и ответ программы тоже сверяют с этой прикидкой. Глубокая теория при этом не требуется, хватает правила произведения и сочетаний на двух-трёх примерах.

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