Дерево всех вариантов

Определения и обозначения

Дерево всех вариантов — схема, которая показывает последовательное построение возможных вариантов выбора. Оно помогает увидеть, какие решения можно принять сначала и чем продолжить каждое из них. Такая схема нужна, чтобы систематически перечислять исходы и проверять, не пропущен ли какой-либо вариант.

Ветвь — линия на дереве, соответствующая одному из возможных выборов на очередном шаге. Например, ветвь с подписью «чай» показывает выбор чая среди напитков. Подписи помогают читать схему и понимать, какое решение привело к каждой части дерева.

Уровень дерева — совокупность вершин, соответствующих одному и тому же шагу выбора. Если сначала выбирают напиток, а затем булочку, вершины после первого выбора относятся к первому уровню, а вершины после второго — ко второму. Уровни помогают не перепутать порядок действий и увидеть, сколько шагов уже выполнено.

Путь в дереве — последовательность ветвей от начальной вершины до конечной; он задаёт один полный вариант. Например, ветви «чай» и «сдобная булочка» вместе образуют путь, то есть один выбор завтрака. По путям удобно перечислять готовые варианты и находить их общее количество.

Как это устроено

Построение дерева начинают с начальной вершины: она обозначает ситуацию до первого выбора. С неё удобно начинать, потому что пока ни одно решение не принято и все возможности ещё рассматриваются вместе. Начальная вершина служит общей точкой, от которой расходятся разные варианты действий.

Из каждой вершины проводят ветви по числу возможных продолжений и подписывают каждую выбранным вариантом. Вершина показывает, к какой ситуации уже пришли, поэтому её продолжения могут отличаться от продолжений других вершин. Если не подписывать ветви, станет трудно понять, какие решения образуют один и тот же путь.

Следующий уровень дерева соответствует следующему шагу выбора. Поэтому на каждом пути решения записаны в том порядке, в котором их принимают: сначала первое, затем его продолжение. Такой порядок нужен, чтобы не смешивать последовательности, в которых один и тот же набор действий выполнен по-разному.

Ветвление продолжают, пока не будут выполнены все шаги задачи. Остановка нужна именно после последнего решения: тогда конечные вершины соответствуют полным вариантам, а не промежуточным состояниям. Если из вершины ещё можно сделать выбор, путь до неё пока не описывает готовый результат.

Количество полных вариантов можно найти, посчитав конечные вершины или пути от начальной вершины до них. Эти способы дают один результат, потому что каждая конечная вершина завершает один полный путь. Считать нужно только завершённые пути: вершины на промежуточных уровнях показывают отдельные этапы, а не готовые варианты.

Как читать дерево всех вариантов

Читайте дерево от начальной вершины к конечным, последовательно собирая подписи ветвей. Таблица помогает различать отдельный выбор, шаг и готовый вариант. При подсчёте ориентируйтесь на конечные вершины или полные пути, а не на все вершины схемы.

Разбор задач

Завтрак из напитка и булочки

Для завтрака можно выбрать один из двух напитков и одну из двух булочек. Пусть напитки — чай и сок, а булочки — сдобная и ржаная. Сначала ветвим дерево по напиткам, затем от каждой полученной вершины проводим ветви к обеим булочкам.

1. От начальной вершины проведите две ветви: «чай» и «сок». Так будут учтены все возможные первые решения.
2. Из конца ветви «чай» проведите ветви «сдобная булочка» и «ржаная булочка». Такие же два продолжения добавьте из конца ветви «сок».
3. Прочитайте каждый путь от начала до конца и запишите его как сочетание напитка и булочки. Каждый путь содержит ровно один выбор из каждой группы.

Получаются варианты: чай и сдобная булочка; чай и ржаная булочка; сок и сдобная булочка; сок и ржаная булочка. Их четыре, потому что у каждой из двух ветвей напитков есть по два продолжения. Ответ: 4 варианта завтрака.

Поездка до музея

Участник выбирает один из трёх маршрутов до парка, а затем один из двух способов добраться от парка до музея. Выбор второго шага совершается после первого, поэтому дерево будет иметь два уровня ветвления. Если любой способ доступен после каждого маршрута, из каждой вершины первого уровня выходят две ветви.

1. Из начальной вершины проведите три ветви и подпишите их «маршрут 1», «маршрут 2» и «маршрут 3». Это все способы добраться до парка.
2. Из конца каждой ветви проведите по две ветви, обозначающие два способа продолжить путь от парка до музея. Итого на втором шаге получится шесть ветвей.
3. Посчитайте конечные пути: у каждого из трёх маршрутов есть два продолжения. Проверка умножением даёт 3 × 2 = 6.

Все пути различаются хотя бы одним выбором и описывают отдельные поездки. Проверка совпала с подсчётом по дереву, значит, при условии доступности обоих способов после любого маршрута учтены все сочетания. Ответ: 6 разных поездок.

Двузначные числа без повторения

Из цифр 1, 2 и 3 составляют двузначные числа без повторения цифр. На первом шаге выбирают цифру десятков, а на втором — цифру единиц. После первого выбора эту цифру нельзя использовать снова, поэтому число ветвей на втором шаге зависит от первой цифры.

1. Из начальной вершины проведите три ветви: первая цифра может быть 1, 2 или 3. Каждая такая ветвь задаёт начало будущего числа.
2. После выбора 1 проведите ветви к 2 и 3, после выбора 2 — к 1 и 3, после выбора 3 — к 1 и 2. Использованная цифра исключена, чтобы не нарушить запрет на повторение.
3. Прочитайте цифры вдоль каждого полного пути слева направо и соедините их в число. Проверьте, что каждое число состоит из двух разных цифр из заданного набора.

Получаются числа 12, 13, 21, 23, 31 и 32. В каждой ветви первого выбора есть по два продолжения, поэтому всего 3 × 2 = 6 полных путей. Ответ: 12, 13, 21, 23, 31 и 32.

Типичные ошибки

Пропущенная ветвь означает, что один из возможных выборов на шаге не учтён. Такое случается, когда ученик рассматривает только очевидные продолжения или забывает проверить одну из вершин. Чтобы проверить себя, для каждой вершины отдельно перечислите все доступные варианты и сравните их с ветвями.

Недопустимый вариант появляется, если при построении забыли об ограничении задачи, например разрешили повторить цифру там, где повторение запрещено. Ошибку часто допускают, перенося одинаковые ветви в каждую вершину без проверки условий. Проследите каждый полный путь и проверьте, соответствует ли он всем ограничениям.

Если посчитать вершины всех уровней, получится лишний результат: промежуточные вершины не являются полными вариантами. Путаница возникает потому, что вершины удобно считать, но их назначение на разных уровнях различается. Для проверки считайте только конечные вершины или пути от начала до конца.

Можно ошибочно посчитать одинаковые варианты разными или объединить различные последовательности выборов. Это происходит, если не учитывать порядок действий или, наоборот, считать порядок важным там, где он не меняет результат. Сравните подписи вдоль путей с условием и заранее определите, считаются ли разные последовательности разными вариантами.

Связь с другими темами

Для построения дерева нужно уметь выделять последовательные шаги выбора и перечислять результаты каждого шага. Это связывает тему с внимательным анализом условий: сначала выясняют, какие действия выполняются и какие ограничения действуют. Если шаги определены неверно, дерево не поможет получить правильный ответ.

Дерево вариантов используют в задачах на перебор и подсчёт комбинаций. Оно помогает проверить, что список возможных исходов полон, а каждый результат удовлетворяет условиям. В простых случаях число путей можно сопоставить с произведением количества выборов на шагах, если эти количества не зависят от предыдущих решений.

Что запомнить

• Каждый уровень дерева соответствует очередному шагу выбора.
• Каждая ветвь обозначает один возможный выбор на этом шаге.
• Полный путь от начальной до конечной вершины задаёт один вариант.
• Для полного перебора нужно учесть все допустимые ветви.
• Если условия ограничивают выбор, эти ограничения учитывают при построении ветвей.
• Число вариантов равно числу полных путей, если каждому пути соответствует ровно один вариант.