"Занимательные задачи по информатике", Босова Л.Л., Босова А.Ю., Коломенская Ю.Г.
Комбинаторная задача помогает узнать, сколько способов выбрать предметы или расположить их. Такие задачи встречаются, когда нужно составить значок, выбрать одежду или записать числа из заданных цифр. Чтобы найти ответ, сначала выясняют, что считается отдельным вариантом и какие условия нужно соблюдать. Затем варианты перечисляют по порядку, показывают на схеме или считают умножением, если выборы независимы.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Комбинаторная задача — задача, в которой нужно найти или подсчитать, сколько существует способов выбрать или расположить предметы. Например, можно выяснять, сколькими способами выбрать карандаш или составить число из цифр. Это определение помогает узнать задачи, где нужно не просто выполнить вычисление, а разобраться с набором возможностей. Такие задачи решают, чтобы точно сосчитать все способы и не перечислять их наугад.
Вариант — один возможный способ выполнить условие задачи. Если выбрать один карандаш из нескольких, каждый подходящий карандаш — отдельный вариант. Нужно заранее понять, что именно считать одним вариантом: например, отличаются ли два случая только порядком предметов. Тогда ответ будет соответствовать условию, а не случайному способу записи.
Полный перебор — последовательная запись всех подходящих вариантов без пропусков и повторов. Это не просто список примеров: в нём должны оказаться все случаи, которые разрешены условием. Удобно заранее выбрать порядок, например перебирать сначала один цвет, потом следующий. Так легче проверить, что каждый вариант учтён ровно один раз.
Дерево вариантов — схема, показывающая, как из последовательных выборов получаются все возможные варианты. От начала отходят ветви для первого выбора, а от них — ветви для следующего. Один путь по ветвям показывает один полный вариант. Такая схема нужна, когда выбор делают в несколько шагов и важно не потерять ни одно продолжение.
В комбинаторной задаче сначала выясняют, что считается отдельным вариантом и какие условия ограничивают выбор. Без этого можно случайно считать разными случаи, которые условие считает одинаковыми, или включить запрещённый случай. Например, если составляем двузначное число без повторов, числа с одинаковыми цифрами не подходят. Поэтому сначала прочитай условие и назови признаки, по которым варианты отличаются.
Чтобы не пропустить варианты и не посчитать один и тот же несколько раз, перебор проводят по единому порядку. Можно сначала зафиксировать первый выбор, затем выписать все возможные продолжения для него и перейти к следующему первому выбору. Тогда варианты распределяются по группам, и группы не мешаются друг с другом. Например, при выборе формы и цвета сначала рассматривают одну форму со всеми цветами, потом другую.
Если выбор состоит из нескольких шагов, каждому шагу соответствуют ветви дерева. Сначала рисуют или мысленно задают начало, затем проводят ветви для первого решения и продолжают их для следующих решений. Путь от начала до конца показывает один полный вариант, поэтому по путям можно проверять, какие сочетания получаются. Дерево особенно полезно, когда простого списка уже трудно придерживаться.
Когда на каждом шаге число возможностей известно и выборы независимы, общее число вариантов находят умножением числа возможностей на каждом шаге. Независимость здесь означает, что любой выбор на одном шаге можно сочетать с любым выбором на следующем. Например, при двух формах значка и трёх подходящих каждому цветах получается 2 · 3 вариантов. Если часть сочетаний запрещена, это правило нельзя применять без поправки: число продолжений может различаться.
Перед подсчётом полезно проверить результат. При списке или дереве просмотри все группы и убедись, что каждый вариант подходит условию; при умножении проверь, что возможности действительно можно сочетать свободно. Если можно, сравни результат двумя способами: например, посчитай по дереву и отдельно умножением. Такая проверка помогает обнаружить пропуск, повтор или случай, который не должен был попасть в ответ.
| Способ | Как применять | Когда удобен |
|---|---|---|
| Последовательный список | Записывать варианты в установленном порядке | Когда вариантов немного |
| Таблица | Расположить варианты по строкам и столбцам | Когда нужно сочетать два признака или выбора |
| Дерево вариантов | Разветвлять схему при каждом следующем выборе | Когда выборы выполняются по шагам |
| Умножение числа возможностей | Перемножить число вариантов на каждом независимом шаге | Когда каждый выбор можно сочетать с любым выбором на следующем шаге |
Сначала выбери способ, который соответствует устройству задачи: список помогает при небольшом числе случаев, а таблица — при сочетании двух признаков. Если выборы идут один за другим, удобно построить дерево; при независимых шагах можно воспользоваться умножением. Даже если используешь умножение, мысленно проверь, какие сочетания оно считает.
У Маши есть красный, синий и зелёный карандаши. Сколькими способами она может выбрать один карандаш? Нужно считать выборы, а не порядок, в котором карандаши лежат на столе. Условие просит взять ровно один карандаш, поэтому каждый цвет даст один вариант.
В списке три подходящих варианта, и все они удовлетворяют условию. Ответ: 3 способа.
Для школьного значка выбирают одну из двух форм и один из трёх цветов. Сколько разных значков можно составить? Вариант здесь — пара из одной формы и одного цвета. Будем считать, что любой цвет подходит к каждой форме, значит, запретных сочетаний нет.
Список показывает, что каждый цвет сочетается с обеими формами, а умножение сокращает подсчёт. Ответ: 6 разных значков.
Из цифр 1, 2 и 3 составляют двузначные числа без повторения цифр. Сколько таких чисел можно составить? Здесь порядок важен: число 12 отличается от числа 21, потому что цифры стоят на разных местах. Но одинаковая цифра не может занимать оба места.
Всего записано 2 + 2 + 2 = 6 подходящих чисел. Ответ: 6 чисел.
Если перечислять варианты без установленного порядка, легко пропустить один из них. Так случается, когда записи вспоминают произвольно и переходят от одного случая к другому без плана. Перед перебором реши, по какому признаку разделить варианты на группы, например по первой цифре или форме. Для проверки пересчитай каждую группу и убедись, что все возможные первые выборы рассмотрены.
Иногда один вариант записывают несколько раз, изменив порядок записи, хотя условие не считает порядок важным. Это происходит, если не определить заранее, чем один вариант отличается от другого. Проверь, имеет ли порядок значение в задаче: при выборе двух фруктов пара может быть той же самой, а при составлении числа перестановка цифр меняет число. Если условие не уточняет порядок, внимательно перечитай его и не считай один набор дважды.
Умножение чисел возможностей даёт ошибку, если выборы не независимы или некоторые сочетания запрещены. Такое случается, когда правило применяют сразу, не проверив, сколько продолжений есть у каждого выбора. Просмотри ветви дерева: если у разных ветвей разное число продолжений, обычное умножение этих чисел может быть неверным. В таком случае посчитай варианты отдельно для каждой ветви и сложи результаты.
Можно включить в ответ вариант, который нарушает условие, например число с повторяющимися цифрами. Часто это происходит потому, что после подсчёта проверяют только количество записей, а не каждую запись. Проверь каждый вариант по всем ограничениям задачи: сколько предметов выбирают, разрешены ли повторы и какие сочетания допустимы. Удаляй неподходящие случаи до того, как назовёшь ответ.
Для комбинаторных задач нужно внимательно читать условия, сравнивать случаи и выполнять сложение и умножение натуральных чисел. Перебор помогает увидеть, какие варианты отличаются, а вычисления — быстро подсчитать их количество. Если не разобрать условие, даже правильное умножение может дать ответ не на тот вопрос. Поэтому сначала определяют допустимые случаи, а потом считают.
Такие способы подсчёта пригодятся при решении задач на вероятность: чтобы рассуждать о шансах, часто сначала считают все возможные исходы и подходящие исходы. Перечисление, таблица и дерево помогают сделать такой подсчёт аккуратно. Кроме того, комбинаторные идеи связаны с представлением данных: таблица упорядочивает сведения по признакам, а схема показывает последовательность выборов. Это полезно, когда нужно не только получить ответ, но и понятно показать ход рассуждений.
Как понять, что задачу можно решить перебором?
Перебор подходит, если можно по очереди выписать все случаи, которые удовлетворяют условию. Особенно удобно так решать задачи, где вариантов немного или нужно проверить ограничения.
Как выбрать удобный порядок перечисления вариантов?
Выбери один признак, по которому удобно разбить варианты, и придерживайся его до конца. Например, сначала рассматривай каждый цвет, а внутри него — все подходящие формы.
Когда для подсчёта вариантов нужно умножать?
Умножай числа возможностей на последовательных шагах, если каждый выбор можно сочетать с любым выбором на следующем шаге. Если есть запрещённые сочетания или выборы влияют друг на друга, сначала учти эти ограничения.
Чем дерево вариантов отличается от обычного списка?
В списке варианты записаны один за другим. В дереве видно, каким выбором начинается каждый путь и какие продолжения возможны на следующих шагах.
Как проверить, что при переборе ничего не пропущено?
Раздели варианты на группы по одному признаку и проверь каждую группу отдельно. Затем убедись, что все записи подходят условию и не повторяют друг друга.
Комбинаторные задачи
