ЕГЭ · задание 8 · от условия к алгоритму
Комбинаторика и перебор: как решать задание 8 ЕГЭ по информатике
Сколько слов можно составить из букв? Сколько чисел удовлетворяют ограничениям? Научитесь переводить условие в понятные правила и выбирать между вычислением по формуле и перебором на Python.
Что вы будете разбирать
Слова и числа
Алфавит, длина записи, повторения и запрет ведущего нуля. Почему похожие условия дают разные ответы.
Ограничения
Нужное количество символов, соседние буквы и допустимые позиции. Как не потерять условие при подсчёте.
Проверка кодом
Перебор с itertools.product, фильтрация вариантов и сверка с ручным решением.
Пример: трёхзначные числа из четырёх цифр
Составляем трёхзначные числа из цифр 0, 1, 2, 3. Цифры могут повторяться. Сколько разных чисел получится?
Первый разряд не может быть нулём: запись 012 не является трёхзначным числом. В двух оставшихся позициях доступны все четыре цифры.
Проверить решение перебором на Python
from itertools import product
count = 0
for digits in product("0123", repeat=3):
if digits[0] != "0":
count += 1
print(count) # 48product создаёт записи с повторениями, а условие отбрасывает записи с ведущим нулём.
Самопроверка: сколько таких чисел без повторения цифр?
На первой позиции 3 варианта, на второй — 3 оставшиеся цифры (включая 0), на третьей — 2. Ответ: 18. Правило 3 × 4 × 4 здесь уже не подходит.
Кому подойдёт
Тем, кто готовится к ЕГЭ по информатике и путается, когда умножать количество вариантов, а когда писать перебор. Для примера с кодом пригодятся базовые знания цикла for, условия if и строк.
Как получить доступ к курсу
Этот пример открыт всем. Учебный курс с уроками и практикой преподаватель назначает профилю в рамках занятий. Одна регистрация не открывает все закрытые материалы автоматически.
Не уверены в исходном уровне? Пройдите бесплатную диагностику. Для повторения синтаксиса: чтение кода Python с объяснениями.
Автор объяснения — Никита Саралашвили. Пример составлен для объяснения метода; это не цитата экзаменационного задания.