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

В восьмом задании нужно посчитать количество слов, кодов или чисел, удовлетворяющих набору условий. Например: сколько пятибуквенных слов можно составить из заданных букв, если одна буква должна встретиться ровно два раза, а слово не может начинаться с определённой буквы; сколько существует шестизначных чисел в восьмеричной системе с неповторяющимися цифрами; под каким номером в упорядоченном списке стоит слово.

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

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

• правило умножения: если первый элемент можно выбрать a способами, а второй — b способами, то пару — a · b способами;
• правило сложения для взаимоисключающих случаев;
• число размещений с повторениями: слов длины n из алфавита мощности m — m^n;
• число сочетаний C(n, k) — способов выбрать k позиций из n;
• умение правильно учитывать ограничения: «ровно», «хотя бы», «не начинается с», «нет двух одинаковых рядом».

Типичные формулировки

1. «Сколько существует слов длины 5, составленных из букв …, в которых буква О встречается ровно 2 раза?»
2. «… слово не начинается с буквы Н и не заканчивается гласной».
3. «Сколько существует n-значных чисел в k-ичной системе счисления, у которых …?» — например, все цифры различны или соседние цифры разной чётности. Помните: число не может начинаться с нуля.
4. «Все слова записаны в алфавитном порядке и пронумерованы. Под каким номером стоит слово …?» или «Какое слово стоит под номером …?»

Пошаговый метод

1. Определите алфавит и длину. Выпишите буквы (цифры) и количество позиций. Если буквы в слове-образце повторяются, алфавит состоит из различных букв.
2. Переведите условие в проверку для одного слова: «ровно две буквы О» — w.count('О') == 2, «не начинается с Н» — w[0] != 'Н'.
3. Посчитайте формулой, если ограничения простые: выберите позиции для особых букв, затем заполните остальные позиции.
4. Проверьте перебором: itertools.product(алфавит, repeat=n) выдаёт все слова длины n в алфавитном порядке (если алфавит упорядочен).
5. Сверьте результаты. Расхождение почти всегда означает неверно понятое условие.

Разбор примера 1: слова

Петя составляет пятибуквенные слова из букв П, И, Т, О, Н. Каждая буква может встречаться любое количество раз или не встречаться вовсе, но буква О должна встречаться ровно два раза, а слово не может начинаться с буквы Н. Сколько слов может составить Петя?

Шаг 1. Только условие про О. Выбираем 2 позиции из 5 для букв О: C(5, 2) = 10 способов. На оставшиеся 3 позиции ставим любую из четырёх других букв: 4^3 = 64. Всего 10 · 64 = 640 слов.

Шаг 2. Вычитаем слова, начинающиеся с Н. Первая буква — Н, тогда в оставшихся четырёх позициях ровно две О: C(4, 2) = 6 способов выбрать их место и 4^2 = 16 способов заполнить две другие позиции. Итого 6 · 16 = 96 слов.

Шаг 3. Ответ. 640 − 96 = 544.

Ответ: 544.

Разбор примера 2: числа

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

Шаг 1. Цифры. В семеричной системе цифры 0–6. Чётные: 0, 2, 4, 6 — четыре; нечётные: 1, 3, 5 — три.

Шаг 2. Шаблоны. Чётность чередуется, поэтому возможны только два шаблона: Ч Н Ч Н Ч и Н Ч Н Ч Н.

Шаг 3. Первая цифра. Число не начинается с нуля. Для шаблона Ч Н Ч Н Ч первая цифра — одна из 2, 4, 6 (три варианта): 3 · 3 · 4 · 3 · 4 = 432. Для шаблона Н Ч Н Ч Н: 3 · 4 · 3 · 4 · 3 = 432.

Шаг 4. Ответ. 432 + 432 = 864.

Ответ: 864.

Код на Python

Шаблон перебора одинаков для любых условий: генерируем все слова и считаем подходящие.

from itertools import product

# пример 1
count = 0
for w in product('ПИТОН', repeat=5):
    if w.count('О') == 2 and w[0] != 'Н':
        count += 1
print(count)  # 544

# пример 2: цифры как числа 0..6
count = sum(1 for d in product(range(7), repeat=5)
            if d[0] != 0 and all(d[i] % 2 != d[i + 1] % 2 for i in range(4)))
print(count)  # 864

Для задач на номер слова в списке используйте enumerate(product(sorted(алфавит), repeat=n), 1) и ищите нужное слово — так нумерация начнётся с единицы, как в условии. Если алфавит из условия уже упорядочен, sorted ничего не изменит, но страхует от ошибки.

Для «все буквы разные» вместо product удобна функция permutations(алфавит, n), а для проверки «нет двух одинаковых букв рядом» — условие all(w[i] != w[i + 1] for i in range(n - 1)).

Номер слова в упорядоченном списке

Задачи на нумерацию решаются через аналогию с системами счисления. Если алфавит состоит из m букв, упорядоченных по алфавиту, каждой букве можно сопоставить цифру от 0 до m − 1, и тогда список всех слов длины n — это все n-значные числа в m-ичной системе по возрастанию. Номер слова равен значению такого числа плюс один. Например, для букв А, Б, В слово «БАВ» соответствует троичному числу 102, то есть 11 в десятичной системе, и стоит под номером 12. Перебором это проверяется одной строкой.

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

• Считают «хотя бы две» вместо «ровно две» (или наоборот). Перечитайте условие и запишите его как проверку в коде.
• Забывают о ведущем нуле в задачах про числа: пятизначное число не начинается с 0.
• Нумеруют слова с нуля. В условии нумерация обычно начинается с 1.
• Используют повторяющиеся буквы как разные. Если слово-образец «КАРКАС», алфавит — К, А, Р, С (четыре буквы), а не шесть.
• Применяют формулу без проверки. Если ограничений несколько и они пересекаются, формула легко теряет случаи — сверьтесь с перебором.

Потренируйтесь

Порешайте задачи на слова, числа и нумерацию: задания № 8 в банке. Программы перебора можно отрабатывать в задачах с проверкой кода. Теория — в статье «Комбинаторика: подсчёт слов и кодов», а следующее задание — задание 9: электронные таблицы.