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

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

Нужно посчитать количество слов, удовлетворяющих условиям, или найти номер слова в упорядоченном списке.

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

• Число слов длины k из алфавита мощности n равно n в степени k.
• Алфавитный порядок слов соответствует записи чисел в системе счисления с основанием n, где буквам присвоены цифры по алфавиту.
• Номер слова в списке, начинающемся с единицы, равен значению этого числа плюс 1.
• Условия вида «ровно две буквы О» считают через сочетания: выбираем позиции для О, остальные заполняем оставшимися буквами.
• Условие чётности номера накладывает ограничение на последнюю букву.

Комбинаторика для задания 8

• Правило произведения: если первый символ выбирается n₁ способами, второй n₂ и так далее, всего вариантов n₁ · n₂ · ...
• Слова длины k из алфавита в n букв с повторениями: n^k.
• Без повторений: n · (n−1) · ... · (n−k+1).
• Перестановки n различных букв: n!. Если есть одинаковые буквы, делим на факториалы их количеств.
• Запреты («не начинается с гласной», «нет двух одинаковых подряд») удобнее считать через вычитание: всего минус запрещённые.
• Номер слова в алфавитном списке считается позиционно: сколько слов начинается с более ранних букв, затем то же для второй позиции и так далее.
• Нумерация в задании может начинаться с 1, поэтому сверьтесь с приведённым в условии примером.
• Если вариантов немного, надёжнее написать короткую программу перебора, чем считать вручную.

Как решать задание 8

1. Присвойте буквам цифры в алфавитном порядке, начиная с нуля.
2. Переведите условия задачи в ограничения на разряды числа.
3. Найдите самое большое (или нужное) слово, удовлетворяющее ограничениям.
4. Переведите его в десятичную систему и прибавьте единицу.
5. Запишите номер.

Разбор примера

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

• Забывают, что нумерация начинается с единицы, и ошибаются ровно на 1.
• Присваивают буквам цифры не в алфавитном порядке.