Комбинаторика- это раздел математики, который изучает различные комбинации, различных элементов.
В ЕГЭ по информатике, комбинаторика явно представлена в задании №8. А так же тесно связана с системами счисления, кодированием и алгеброй логики.
Мы начнем изучение комбинаторики с размещения с повторениями. А в конце лекции разберем задание №8 из демоверсии по информатике 2021. И не забывайте подписываться на мой канал, чтобы не пропустить следующие статьи по комбинаторике!
Размещение с повторениями
Давайте для примера вспомним как мы составляли бинарное дерево, для нахождения кодовых слов. Предположим, что нам нужно найти количество кодовых слов длина которых равна трем. Причем напоминаю что кодовые слова состоят из 0 и 1. На первой позиции кодового слова, может быть 0 или 1, на второй позиции тоже 0 или 1, и на третьей позиции, так же 0 или 1.
Если мы продолжим строить наше бинарное дерево, то получим кодовые слова длиной = 4, и их уже будет 16.
Количество размещений с повторениями из n по k, равно n в степени k.
где n - в нашем случае, это 0 или 1, а k - это количество мест (длина слова).
Рассмотрим бытовой пример. Всем наверно знакомы чемоданы с кодовым замком.
Мы с вами можем посчитать сколько всего вариантов кодов может быть на этом замке. Все очень просто. У нас с вами три позиции и в каждой из позиции может быть одна из десяти цифр(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
Нужно просто перемножить 10*10*10 = 1000. Значит такой замок всего может иметь целую 1000 вариантов, как его закодировать.
А теперь давайте представим, что когда-то давно мы уже установили код на этот замок. И конечно жу забыли его, но мы помним что первое число было - 0. То количество вариантов возможных кодов сокращается до 100. Но сто вариантов тоже многовато. И после нескольких неудачных попыток, мы вспомнили, что последняя цифра либо 3, либо 7 (потому что это наши любимые числа). Тогда уже код подобрать совсем несложно, ведь нужно перебрать всего 20 вариантов.
Задание №8 из ЕГЭ по информатике 2021
Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует свое кодовое слово. В качестве кодовых слов Игорь использует трехбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А причем буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?
Давайте для начала разберемся с буквой К. Потому что она в слове может встречаться всего один раз. Длина слова = 3, и К может быть на 1, 2 или 3 месте. Других вариантов для буквы К у нас нет.
Всего для составления кодовых слов, Игорь, может использовать 5 букв. Но так как К мы уже проставили в наших словах, для оставшихся позиций он может использовать одну из четырех букв(Ш, О, Л, А)
Остается только все посчитать.
Ответ: 48
