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