Привет, я Елена TeachYou, твой репетитор по информатике. Читая этот блог и отрабатывая задания самостоятельно, ты сможешь сдать ЕГЭ на 83 балла (и это решая задачи только базового и продвинутого уровня!). Поэтому не забудь подписаться на канал.
Если ты чувствуешь, что самостоятельно разбираться с задачами не получается, не понимаешь, какие задачи могут встретиться на ЕГЭ, а какие могут прийти только в кошмарах, пиши мне в личку или в комментах. У меня еще есть окошки на оффлайн-занятия.
О чем эта статья
Ниже я покажу формулы из комбинаторики, которые вы наверняка проходили на уроках математики. Я приведу три формулы, которые встречаются при решении задач по информатике. Если вы считаете, что какой-то формулы не хватает - пишите в комментариях, я добавлю.
Далее разберем пару задач уровня ЕГЭ, в конце я задам домашнее задание. По моим ощущениям, статья должна получиться легче, чем предыдущие)
Опять же - часть задач можно решать программно, но я адепт умения решать ручками на бумажке. Кстати, работая в окружении программистов, я видела, что у них весь стол завален бумажками с идеями. Так что привыкайте, программисты много думают на бумаге.
Теория. Некоторые формулы из комбинаторики
Перестановки. Факториал. Задача с флагами
Рассмотрим конкретный пример задачи с перестановками, которая запомнилась мне с пятого или шестого класса.
Задача. Пусть у нас имеются три цвета - белый, синий и красный. Сколько различных флагов с тремя горизонтальными полосами можно придумать, используя эти цвета? Цвета в одном флаге не должны повторяться.
Это задача на перестановки. Перестановкой называются наборы, состоящие из одного и того же числа элементов и отличающиеся только порядком следования элементов. Белый-синий-красный - один набор, синий-белый-красный - его перестановка (и наоборот). Количество перестановок для трех объектов - белого, синего и красного цветов и нужно найти в этой задаче.
В галерее дано определение факториала, но в тексте тоже пропишу. Если вы помните со средних классов, что такое факториал и для чего он нужен, угостите себя конфеткой 🍬. Если не помните, тоже можете взять конфетку, так как теперь вы это знаете 😉.
Факториалом натурального числа n называется произведение целых чисел от 1 до n. Пишется n!, читается "эн факториал".
Примечание: иногда требуется вычислить 0! Мировое сообщество договорилось считать, что 0! = 1. Если у вас есть сомнения, добавлю, что 1! тоже равен 1.
Размещения
Пусть у нас есть n различных объектов. Будем выбирать из них m объектов и переставлять всеми возможными способами между собой. Получившиеся комбинации называются размещениями. Задача состоит в поиске количества размещений n объектов по m местам.
Прежде чем перейти к формуле, с помощью которой можно найти количество размещений, рассмотрим следующую задачу.
Задача. Сколько трехзначных чисел можно составить из нечетных десятичных цифр? При этом цифры в числе не могут повторяться.
Смотрите внимательно: это задача на поиск количества размещений пяти объектов (пяти нечетных десятичных цифр - 1, 3, 5, 7, 9) по трем местам. Давайте решим ее деревом (я предлагаю такое решение не потому, что я друид, а затем, чтобы вы понимали, откуда берутся формулы. В этом случае вам можно ее и забыть, но все равно верно решить задачу - вы же понимаете, откуда она взялась).
Внезапное ДЗ. А теперь давайте вы посчитаете, сколько трехзначных чисел, в которых все цифры разные, можно составить из четных десятичных цифр? Спойлер: ответ будет другим. Пишите ответ в комментариях, обязательно проверю, сколько у вас получилось. И похвалю за правильный ответ 😉.
Сочетания
Последняя формула - количество сочетаний. Сочетанием называется набор из k элементов, выбранных из n-элементного множества, в котором не учитывается порядок элементов. Существует формула для подсчета количества сочетаний:
Если вы забыли, пролистайте галерею, там сочетания проиллюстрированы парочкой задач.
А теперь будем учиться решать егэшные задачки.
Задача 1
Условие: шифр кодового замка представляет собой последовательность из пяти символов, каждый из который является цифрой от 1 до 4. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 встречается ровно два раза, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?
Давайте по порядку:
- Кратенько: у нас пять мест, на которые нужно поставить цифры от 1 до 4.
- Условие "цифра 1 встречается ровно два раза". Вопрос: как посчитать, сколькими способами можно расставить два объекта на пяти местах? Нужна формула "це из эн по ка", которая в этом случае будет иметь вид "це из пяти по три": 5!/(2!*(5-2)!)=5!/(2!*3!)=4*5/2=10. Запоминаем эту 10.
- Если мы фиксируем две единицы на каком-то месте, то остается три свободных места, на которые нужно расставить цифры 2, 3 и 4 так, что они могут повторяться. Сколько цифр может стоять на первом месте? Одна из трех. А на втором? Одна из трех (они же могут повторяться!). И на третьем тоже одна из трех. Значит, количество способов расставить три цифры на трех местах с возможностью повторения равно 3*3*3=27.
- И последнее - перемножаем количество размещений двух единиц на количество размещений с повторениями трех цифр на трех местах: 10*27=270.
А теперь то же самое, но в картинках:
Кстати, на картинки в этой статье я добавила рукописный шрифт. Читаемо? Маякните в комментариях, стоит ли его и дальше использовать.
Задача 2
Условие: Вася составляет слова из букв слова ПРЕПАРАТ. Код должен состоять из 8 букв, и каждая буква в нём должна встречаться столько же раз, сколько в заданном слове. Кроме того, в коде должны стоять рядом две гласные или две согласные буквы. Сколько различных слов может составить Вася?
Давайте разберем условие "в коде должны стоять рядом две гласные или две согласные буквы". В исходном слове 8 букв, из них пять букв согласные и три гласные. Заявляю, что, как ни переставляй буквы, две согласные точно будут стоять рядом. Получается, это условие лишнее, можем решать задачу, не обращая на него внимания.
Задачи можно решать по-разному. Мне нравится такой "последовательный" способ.
1. Считаем количество различных букв, входящих в слово:
П - 2 шт, Р - 2 шт, А - 2 шт; Е, Т - по 1 шт.
2. Выбираем букву, входящую в слово максимальное количество раз (в нашем случае это П, Р или А). Для определенности возьмем П. Считаем количество способов, которыми две П можно расставить на восьми местах.
3. "Фиксируем" две П на каких-то местах. Остается шесть свободных мест. Берем следующую букву, которая встречается два раза, пусть Р. Считаем, сколькими способами можно расставить две Р на шести местах.
4. "Фиксируем" еще и две Р. Теперь остается четыре свободных места, и осталась одна буква, встречающаяся в слове два раза - буква А. Считаем "це из четырех по два".
5. Фиксируем еще и две А. Остается два места и две буквы - Е и Т. Сколькими способами их можно расставить на двух местах? Это количество перестановок двух объектов, 2!
6. Перемножаем результаты вычислений в пп. 2, 3, 4 и 5.
Я думаю, что с вычислениями вы справитесь сами) Я как тот математик из анекдота, который убедился, что решение есть, и расслабился.
Ваша любимая домашка
Я стараюсь в ДЗ набирать разные задачи, чтобы вы могли отработать задания в разных формулировках. Да, они обычно бывают сложнее, чем те, которые я разобрала в статье. Но самообучение - великая вещь! В конце концов, вы можете написать мне в личку и договориться об оффлайн-уроке 😉
Сайт К. Полякова, номера 5428, 5087, 5086, 5013, 5010 (да, и эту, мы же ее не дорешали!), 4248, 4246, 4234.
Успехов вам с подготовкой! Я знаю, что последний школьный год очень напряженный, но советую вам расставить приоритеты, научиться планировать время, отдыхать необходимое количество времени, хорошо кушать и не забывать гулять! У вас все получится! А я вам помогу. Подписывайтесь на канал TeachYou, чтобы не потерять меня.