8 задание ЕГЭ по информатике: формулы, код и разбор
В задании № 8 ЕГЭ по информатике нужно считать слова, коды или числа, составленные по определённым правилам, а иногда — находить их номер в упорядоченном списке. Решение строится на двух подходах: подсчёте вариантов по формулам и переборе на Python. Сначала переведи условие в ограничения, затем выбери способ и проверь, что учёл каждое требование.
8 задание ЕГЭ: информатика и теория комбинаторики
Слово в таких задачах — любая последовательность символов заданной длины. Оно не обязано иметь смысл: АБВ и ВВВ могут быть допустимыми словами, если условие разрешает повторения. Алфавит — набор доступных символов, а длина слова — количество позиций в нём.
Основной инструмент — правило произведения: если для первой позиции есть a вариантов, а после каждого такого выбора для второй остаётся b вариантов, получится a * b последовательностей. Для n позиций с одинаковыми k вариантами на каждой число слов равно k^n. Здесь знак ^ обозначает степень; в Python степень записывается через **.
Правило суммы применяют, когда подходящие слова разбиты на непересекающиеся группы. Например, можно отдельно посчитать слова с одной гласной и с двумя гласными, затем сложить результаты. Если группы пересекаются, простое сложение посчитает некоторые слова повторно.
- Алфавит определяет, какие символы доступны.
- Длина определяет количество позиций.
- Ограничения определяют, какие последовательности нужно оставить.
Как решать 8 задание ЕГЭ по информатике вручную
Перед вычислениями выпиши длину, размер алфавита и все ограничения. Подчеркни слова «ровно», «хотя бы», «не более», «не повторяются», «не стоят рядом». Это разные условия: «ровно одна А» исключает слова без А и слова с несколькими А, а «хотя бы одна А» допускает несколько таких букв.
Если особая буква встречается ровно один раз, сначала выбери её позицию. Затем заполни остальные позиции символами алфавита, исключив эту букву. При длине n и размере алфавита k получишь n * (k − 1)^(n − 1). Такой подсчёт работает, если других ограничений нет.
Полезно нарисовать n клеток и подписать число вариантов над каждой. Когда особая буква уже размещена, она больше не должна появляться в остальных клетках. Указание об алфавитном порядке само по себе не меняет количество подходящих слов: порядок нужен, когда спрашивают номер слова или слово под заданным номером.
- Определи, что требуется: количество, номер или конкретное слово.
- Размести символы, для которых заданы особые условия.
- Посчитай варианты заполнения оставшихся позиций.
- Проверь, что каждое допустимое слово учтено ровно один раз.
Пример задания из банка «Ранга»
В этом примере удобно отработать подсчёт слов с ровно одним появлением заданной буквы: сначала выбрать её место, затем заполнить остальные позиции. Сравни ручное решение с перебором и проверь, влияет ли алфавитный порядок на искомое количество.
Условие. Все четырёхбуквенные слова, составленные из букв А, Б, В, Г, записаны в алфавитном порядке (буквы в слове могут повторяться). Слова длиной 4 буквы составляются из того же набора букв.
Сколько существует слов длиной 4 буквы, в которых буква А встречается ровно один раз? В ответе запиши только целое число.
Показать ответ и решение
- Считаем слова с ограничением. Нужную букву можно поставить на любую из позиций слова, а каждая из остальных позиций заполняется любой из прочих букв алфавита.
- Определи две величины: длину слова и число букв алфавита, кроме той, что должна встретиться ровно один раз.
Ответ: 108
8 задание ЕГЭ по информатике: формулы для основных типов
Формулу выбирают по условиям повторения и расположения символов. Обозначим длину через n, размер алфавита через k, число появлений выделенной буквы через r. Сочетание C(n, r) — количество способов выбрать r позиций из n без учёта порядка выбора.
Если выделенная буква должна встретиться хотя бы один раз, удобно вычесть запрещённые слова из всех возможных: k^n − (k − 1)^n. Для условия «не более двух раз» можно отдельно посчитать случаи с нулём, одним и двумя появлениями и сложить их.
Условия о соседстве требуют отдельного разбора. Если одинаковые буквы не должны стоять рядом, число вариантов следующего символа зависит от предыдущего. При нескольких ограничениях перебор часто проще проверить, чем длинную формулу.
- Повторения разрешены, ограничений нет: k^n.
- Повторения запрещены: k * (k − 1) * … * (k − n + 1), если n ≤ k; иначе вариантов нет.
- Выделенная буква встречается ровно r раз: C(n, r) * (k − 1)^(n − r).
- Используются все n различных букв по одному разу: n!.
- Заданы количества повторяющихся букв: n! / (m1! * m2! * …), где сумма всех m равна n.
8 задание ЕГЭ по информатике на питоне: шаблон с itertools
Функция product из itertools создаёт последовательности фиксированной длины с повторениями. Для примера выше можно перебрать слова и оставить только те, где А встречается ровно один раз. Каждый результат product — кортеж символов; метод count работает с ним напрямую.
from itertools import product alphabet = 'АБВГ' length = 4 answer = 0 for word in product(alphabet, repeat=length): if word.count('А') == 1: answer += 1 print(answer)
При переносе шаблона в другую задачу замени алфавит, длину и условие внутри if. Каждое требование переводи в отдельную проверку, соединяя их через and. Например, word[0] != 'А' запрещает А на первой позиции, а word.count('А') <= 2 разрешает не более двух появлений.
До запуска оцени размер перебора: программа рассмотрит k^n последовательностей. Большие длины могут сделать такой подход неудобным. Если количество вариантов велико, ищи формулу или разбивай задачу на случаи.
- product допускает повторения символов.
- permutations подходит для размещений без повторений, если исходные символы различны.
- Не добавляй одинаковый символ в alphabet несколько раз: это создаёт повторный учёт.
Разбор 8 задания ЕГЭ по информатике: алфавитный порядок
Когда спрашивают номер слова, сопоставь символам цифры от 0 до k − 1 в указанном порядке. Тогда слово фиксированной длины можно прочитать как запись числа в системе счисления с основанием k. Первый символ отвечает за старший разряд.
Если цифры слова равны d1, d2, …, dn, его значение равно d1 * k^(n − 1) + d2 * k^(n − 2) + … + dn. При нумерации списка с единицы номер слова на один больше этого значения. Для обратной задачи сначала вычти единицу из номера, затем переведи число в нужную систему и дополни запись нулями слева до заданной длины.
Этот способ напрямую работает для полного списка слов одной длины. Если сначала исключены слова по дополнительному условию, номера в оставшемся списке меняются. При переборе enumerate(product(alphabet, repeat=n), start=1) нумерует полный список; счётчик внутри фильтра нумерует только подходящие слова.
- Бери порядок букв из условия.
- Проверь, начинается ли нумерация с единицы.
- Уточни, нумеруется полный список или отфильтрованный.
Типичные ошибки и проверка ответа
Различай код и число. Код может начинаться с нуля, если запрета нет. У многозначного числа первая цифра нулём быть не может. Поэтому формула для последовательностей цифр не всегда подходит для подсчёта чисел той же длины.
При проверке кода временно выведи несколько подходящих последовательностей. Среди них не должно быть слов, нарушающих ограничения. Затем возьми несколько заведомо запрещённых примеров и проверь, что условие их отбрасывает.
Ещё один способ проверки — уменьшить алфавит и длину, чтобы выписать варианты вручную. Совпадение ручного списка и результата программы помогает обнаружить неверное условие или лишнее увеличение счётчика.
- Количество подходящих слов не может превышать k^n.
- В формуле для ровно r появлений исключи выделенную букву из остальных позиций.
- При проверке соседей сравнивай word[i] и word[i + 1] для i от 0 до n − 2.
- Сверь формулу и перебор на одной небольшой задаче.
Как тренировать задание № 8
Начни со слов без ограничений, затем добавляй условия по одному: точное количество букв, запрет первой позиции, отсутствие соседних символов. После этого переходи к алфавитной нумерации и сочетаниям нескольких требований. Для каждого решения записывай, почему выбранная формула или проверка учитывает все условия.
В «Ранге» можно потренироваться на задании № 8 с проверкой ответа. После ошибки полезно определить её причину: неверно прочитанное ограничение, повторный учёт, ошибка в формуле или коде. Затем реши похожую задачу с изменёнными данными.
Соответствие материалов текущему году проверяй по демоверсии, спецификации и кодификатору на сайте ФИПИ. Демоверсия показывает примеры формулировок, спецификация — характеристики экзаменационной работы, кодификатор — проверяемое содержание. Не переноси сведения из материалов прошлого года автоматически.
- Сначала объясни решение словами.
- Затем выполни расчёт или напиши программу.
- После проверки сформулируй правило, которое пригодится в следующей задаче.
Частые вопросы
Можно ли решить 8 задание ЕГЭ по информатике руками?
Да, если ограничения позволяют посчитать варианты по позициям или разбить их на несколько случаев. Перед вычислением объясни, почему случаи не пересекаются и охватывают все допустимые слова.
Обязательно ли использовать код в задании № 8?
Код нужен как инструмент решения, когда перебор удобен по объёму и условиям. Если формула получается короткой и понятной, можно вычислить ответ вручную.
Как выбрать между product и permutations?
Используй product для последовательностей с повторениями. Если каждый символ разрешено использовать не более одного раза, а исходный алфавит состоит из различных символов, подойдёт permutations.
Почему программа считает лишние слова?
Проверь, учтены ли все ограничения и увеличивается ли счётчик только после их проверки. Также убедись, что алфавит не содержит повторяющихся символов и что условие «ровно» не заменено на «хотя бы».
Что включить в шпаргалку для задания № 8?
Запиши правило произведения, формулы для повторений и точного количества выделенных букв, шаблон product и связь алфавитного номера с системой счисления. Рядом укажи условия применимости: формула без пояснения легко приводит к ошибке.
Полезно по теме
Читать дальше
Проверить себя в тренажёре
Открывается тренировочное задание в формате ЕГЭ: условие видно сразу, краткий ответ проверяется без регистрации.
Решить задание в тренажёреМатериал — разъяснение «Ранг». Официальные правила экзамена, расписание, шкалы баллов и перечни заданий публикуют ФИПИ (fipi.ru) и Рособрнадзор (obrnadzor.gov.ru). Мы не обещаем конкретных баллов: результат зависит от твоей работы.