Интернет-энциклопедия по школьным предметам от Maximum Education. Учебник поможет решить домашнее задание, подготовиться к контрольной и вспомнить прошлые темы.
Комбинаторика
В экзамене по информатике под номером 8 вам встретится тема, которая имеет скорее математический уклон, хотя и играет огромную роль для всех компьютерных наук. Речь сейчас идет о комбинаторике.
«Сколькими способами можно положить три одинаковых мяча в две корзины?» «Сколько комбинаций пятизначного шифра можно составить из шести символов?» «Сколько существует вариантов переставить между собой семь различных деревянных фигурок?» Это все примеры вопросов, на которые отвечает комбинаторика.
Под «объектом» в классических комбинаторных задачах понимается способ или возможность что-то сделать, соответственно, количество объектов – это количество таких способов или возможностей. Для решения задач на комбинаторику в ЕГЭ понадобится всего лишь два правила, которые очень похожи на правила вычисления вероятности нескольких событий. Далее приведено два примера, из которых напрямую следуют эти правила.
На столе лежит 4 кубика: красный, желтый, синий и зеленый. Сколькими способами их можно переставить местами?
Есть 4 способа занять первое место (поставить любой из четырех кубиков), 3 способа занять второе место (мы ведь не можем поставить какой-то один кубик на два места сразу), 2 способа занять третье место и 1 способ поставить оставшийся кубик в конце. Поскольку эти события происходят вместе (мы поставили на стол И первый кубик, И второй, И третий, И четвертый), то количества способов будут перемножаться. Получаем 4 × 3 × 2 × 1 = 4! = 24.
Сколько способов взять хотя бы один кубик из трех (красный, желтый и зеленый), лежащих на столе?
Хотя бы один – это либо 1, либо 2, либо 3. Есть 3 способа взять 1 кубик (потому что кубиков всего 3). Еще есть 3 способа взять два кубика (красный/желтый, желтый/зеленый, зеленый/красный) и еще один способ взять 3 кубика сразу. Эти ситуации (взять один кубик, ИЛИ же два, ИЛИ же три) происходят независимо, каждый из них удовлетворяет нас в отдельности от остальных. В этом случае количества способов будут складываться. Получаем: 3 + 3 + 1 = 7.
Правила суммы и произведения
Приведенные выше примеры иллюстрируют два важнейших комбинаторных правила – правило суммы и правило произведения. Они абсолютно аналогичны тем, что приведены выше для подсчета вероятности составных событий. Комбинаторные правила суммы и произведения удобнее всего представить виде таблицы:
| ПРАВИЛО ПРОИЗВЕДЕНИЯ | ПРАВИЛО СУММЫ |
|---|---|
| ЕСЛИ СОБЫТИЯ | |
| Происходят вместе | Не могут произойти вместе (взаимоисключающие) |
| ТО КОЛИЧЕСТВО СПОСОБОВ ВЫПОЛНИТЬ | |
| И первое, И второе, … | ИЛИ первое, ИЛИ второе, … |
| БУДЕТ РАВНО | |
| N1* N2 * N3* … | N1 + N2 + N3 + … |
| ГДЕ N1, N2, N3, … – количество способов для каждого события |
Существует 2 основных прототипа задания № 10, которые могут вам встретиться на экзамене – прототип на составление слов из указанных букв и прототип с уже готовым списком слов. Давайте по очереди разберемся с решением каждого из них.
Прототип на составление слов
В начале обратим внимание на ограничение, связанное с бутовой О. Мы можем поставить её 6 способами:
Оххххх
хОхххх
ххОххх
хххОхх
ххххОх
хххххО
Для каждого из 6 способов показанных выше остаётся 5 свободных мест. На каждое свободное место можно поставить любую из букв Д и М. Получаем, что по правилу произведения для каждого из 6 вариантов расстановки буквы О есть 2*2*2*2*2=32 варианта расстановки букв Д и М.
Теперь вступает правило суммы: есть 6 наборов комбинаций, которые не могут произойти вместе.
Получаем 32+32+32+32+32+32 (или 32*6) = 192 различных слова.
Прототип со списком слов
Ниже приведено начало списка.
-
ГГГГ
-
ГГГО
-
ГГГР
-
ГГГН
-
ГГОГ
……
Запишите слово, которое стоит на 84-м месте от начала списка.
Алгоритм решения данного прототипа выглядит следующим выглядит следующим образом:
1. Основание «системы счисления» равно числу различных букв.
2. По порядку крайних первых букв в списке «слов» сопоставлять каждую букву с цифрой (первая – 0, вторая -1,и так далее).
3. Если необходимо найти положение «слова» в списке – переписываем его в выбранной СС, переводим в десятичную и прибавляем 1.
4. Если надо найти слово по положению – из порядкового номера вычитаем 1, переводим в выбранную СС и переписываем в буквенном обозначении.э
Имеем четыре буквы - Г, О, Р, Н, с помощью которых кодируем 4-буквенные 'слова'. Если внимательно посмотрим на последовательность, которая дана в условии, то можно увидеть сходство с числами, которые записаны в порядке возрастания в какой-то системе счисления. У нас есть 4 различных символа, чтобы записать слово, значит мы можем провести аналогию с четверичной системой счисления. При этом важно понять, какая буква закреплена за какой 'цифрой': сначала у нас все Г, значит, это '0'. Потом появляется О, получается, О - это '1'. Затем идет Р, значит, Р – это '2'. Ну и Н - это '3'. Получается, вопрос задачи можно перефразировать: какое 'число' будет 84-м в списке? Иначе, какое число в четверичной системе кодируется как 83? Нам нужно именно 83, а не 84, потому что первое по порядку для нас - это 'Г'. Значит, 84-е - 83. 8310 = 11034. Теперь вспоминаем, что '0' - это Г, '1' - это О, '2' - это Р, '3' - Н : ООГН.
Следует отметить, что бывают прототипы со списком слов, где слово уже дано и нужно найти его порядковый номер. Алгоритм решения у вас уже есть, самое главное – не забыть, что список начинается с единицы, а не с нуля, поэтому после получения номера в десятичной системе счисления нужно прибавить 1.