Задание 8 ЕГЭ по информатике: комбинаторика
Восьмое задание ЕГЭ по информатике про комбинаторику: сколько слов определённой длины можно составить из набора букв, с ограничениями или без. Иногда спрашивают, какое слово стоит на определённом месте в алфавитном списке. Простые задачи решаются формулой, сложные перебором.
Для 10–11 классов. Нумерация по проекту демоверсии ФИПИ на 2027 год.
Формулы
- Слова длины k из n букв, буквы могут повторяться: nᵏ.
- Без повторений, все n букв по разу: n! = 1·2·…·n.
- Буква на фиксированном месте: остальные места считаем отдельно и перемножаем.
Разбор задач
Все слова
Сколько существует слов длины 5 из букв А, Б, В, Г?
4⁵ = 1024.
Ответ: 1024
Ровно одна буква К
Сколько слов длины 4 из букв К, О, Т, в которых К встречается ровно один раз?
Место для К выбираем 4 способами.
На остальных трёх местах О или Т: 2³ = 8. Всего 4·8 = 32.
Ответ: 32
Без повторов
Сколько слов из 5 разных букв А, Б, В, Г, Д можно составить, если каждая буква используется ровно один раз?
5! = 120.
Ответ: 120
Слово на 50-м месте
Все слова длины 4 из букв А, Б, В записаны в алфавитном порядке и пронумерованы с 1. Какое слово стоит на 50-м месте?
Заменим А, Б, В на 0, 1, 2: слова стали числами в троичной системе, первое слово 0000 имеет номер 1.
50-е слово соответствует числу 49. 49 в троичной 1211.
1211 это БВББ.
Ответ: БВББ
Перебор на Python
from itertools import product count = 0 for w in product('КОТ', repeat=4): if w.count('К') == 1: count += 1 print(count)
product перебирает слова с повторениями, permutations без повторений. Условия любой сложности проверяются внутри цикла: «не начинается с гласной», «нет двух одинаковых букв рядом».
Проверь себя
- Слов длины 3 из 5 букв с повторениями? Ответ: 125.
- Слов из букв К, О, Т длины 4 без буквы К? Ответ: 16.
Где теряют балл
- Нумерация с единицы. Номер слова на единицу больше числа в системе счисления.
- Алфавитный порядок. Буквы в условии могут быть не по алфавиту. Сортируйте перед кодированием цифрами.
Как тренироваться
Комбинаторика с кодом на Python разобрана в статье ЕГЭ по информатике на Python. Все номера экзамена в статье ЕГЭ по информатике по номерам.
Разберём на занятии
Готовим к ОГЭ и ЕГЭ на живых занятиях в мини-группе до шести человек или один на один, с пробниками в формате экзамена и разбором каждой ошибки.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.
Частые вопросы
Что быстрее: формула или программа?
Для простых условий формула. Если условий два и больше, программа надёжнее.
Сколько баллов?
Один первичный балл.