#хакнем_информатика 👈 новое направление нашей медиагруппы 🥳
Всем привет! В этом году я сдаю ЕГЭ по информатике. В 2021 году он проводится в компьютерной форме (КЕГЭ). Многие задания теперь можно решить с помощью программ, написанных на разных языках программирования.
С теми, кто также, как и я сейчас готовится к этому экзамену, хочу поделиться решениями некоторых задач. В этой статье я разберу, как решить комбинаторную задачу под номером 8 .
Разберём первый пример задания:
Р-09. Маша составляет 5-буквенные коды из букв В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом код буква Ь не может стоять на первом месте и перед гласной. Сколько различных кодов может составить Маша?
Сначала разберёмся, как решать такое задание «руками» (замечу, что данное решение подготовлено по материалам сайта Константина Полякова):
1) проще всего сначала найти общее количество возможных слов, а затем вычесть из него количество «запрещённых» слов — тех, которые начинаются на букву Ь или содержат комбинации ЬУ и ЬА
2) сначала найдём общее количество слов, не накладывая никаких ограничений; при этом есть 5 способов выбрать первую букву, 4 способа выбрать вторую и т.д., так что общее число вариантов равно 5! = 5 × 4 × 3 × 2 × 1 = 120
3) первой буквой не может быть Ь, это исключает 1 × 4 × 3 × 2 × 1 = 24 варианта
4) теперь определим, сколько слов содержит запрещённую комбинацию символов ЬУ; эта комбинация может располагаться на одной из 4-х позиций:
ЬУ***, *ЬУ**, **ЬУ*, ***ЬУ
первый случай уже исключён (слово не может начинаться с буквы Ь), для каждого из остальных случаев количество вариантов распределения остальных букв равно 3 × 2 × 1 = 6 варианта, то есть запрет сочетания ЬУ исключает 3× × 3 × 2 × 1 = 18 кодов
5) аналогично запрет сочетания ЬА исключает ещё 18 кодов
6) таким образом, из 120 слов запрещёнными являются 24 варианта с первой буквой Ь, 18 варианта, содержащие ЬУ в середине слова, и 18 вариантов, содержащие ЬА в середине слова
7) остаётся 120 – 24 – 18 – 18 = 60 кодов
8) Ответ: 60 .
Теперь хочу показать очень красивый метод решения комбинаторных задач с помощью программы:
Код без комментариев:
Программа выводит ответ 60, что является правильным ответом.
Хочу также описать примерный план написания этой программы:
1) Импортируем библиотеку itertools для перестановок;
2) Заводим счётчик наших перестановок;
3) Заводим строку, в которой содержится набор букв, который дан нам по условию;
4) Создаём цикл перебора всех перестановок;
5) Создаём условия, по которым нужно отбирать перестановки;
6) Считаем количество подходящих нам перестановок.
Разберём ещё один пример задания:
Р-07. Вася составляет 3-буквенные слова, в которых есть только буквы В, Е, С, Н , А, причём буква А используется в каждом слове хотя бы 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?
Сначала разберёмся, как решать «руками»:
1) буква А может стоять на одном из трёх мест: А**, *А*, **А, где * обозначает любой из пяти символов;
2) в каждом случае в остальных двух позициях может быть любая из пяти букв;
3) для шаблона А** получаем (перемножая количество вариантов для каждой позиции)
1 × 5 × 5 = 25 слов;
4) для шаблона *А* тоже получим 25 слов, но нужно учесть, что все слова, в которых первая буква А мы уже подсчитали, поэтому считаем только слова, где на первом месте стоит какая-то другая буква (В, Е, С или Н);
5) отсюда находим, что шаблон *А* добавляет 4 × 1 × 5 = 20 новых слов;
6) рассматривая шаблон **А, не учитываем уже подсчитанные слова, в которых буква А есть на первом или втором местах, количество новых слов: 4 × 4 × 1 = 16;
7) всего получается 25 + 20 + 16 = 61 слово;
8) Ответ: 61.
Код программы с комментариями:
В отличие от прошлого примера здесь в условии говорится не о перестановках, а о том, что буквы могут использоваться любое количество раз. Поэтому придётся поменять одно условие: мы используем не permutations, а product . Также нужно указать значение repeat , которое соответствует количеству букв в задании.
Код без комментариев (для удобства):
План написания программы тот же самый, что и в предыдущем примере.
Таким образом, можно решить любую, даже сложную комбинаторную задачу, буквально в несколько строк, главное правильно написать условие отбора наших комбинаций.
Я надеюсь, эта статья будет Вам полезной при подготовке к экзамену! Удачи!
Автор: #матвей_ч 17 лет, город Ярославль
Читайте наш канал в телеграм - по этой ссылке