Дерево вариантов и перебор
💻 Информатика · 6 класс
Дерево вариантов и перебор
Дерево вариантов — это схема, которая помогает перечислить все возможные решения задачи и сосчитать их количество. Дерево начинается с одной точки — корня, от которой отходят ветви. Каждая ветвь — это один из возможных выборов на очередном шаге. Дойдя по ветвям до самого конца, получаем один полный вариант. Такую схему называют деревом, потому что она и правда напоминает ветвящееся дерево.
Как строить дерево
На каждом шаге задачи рисуем столько ветвей, сколько есть вариантов выбора в этот момент. От каждого нового узла снова отходят ветви для следующего шага. Так дерево «разрастается», и по нему легко увидеть все исходы, ничего не пропустив.
Правило: чтобы узнать общее число вариантов, перемножают количество возможностей на каждом шаге. Дерево же показывает не только число, но и сами варианты целиком.
Разбор примера
У Маши есть две футболки (красная и синяя) и три юбки (белая, чёрная, зелёная). Сколько разных нарядов она может составить, если в наряд входят одна футболка и одна юбка?
На первом шаге выбираем футболку — получаем 2 ветви. От каждой футболки отходит по 3 ветви — это выбор юбки. Перечислим все исходы.
красная → белая, чёрная, зелёная
синяя → белая, чёрная, зелёная
Всего вариантов: 2 × 3 = 6
| Номер | Футболка | Юбка |
|---|---|---|
| 1 | красная | белая |
| 2 | красная | чёрная |
| 3 | красная | зелёная |
| 4 | синяя | белая |
| 5 | синяя | чёрная |
| 6 | синяя | зелёная |
В таблице ровно шесть строк — столько же, сколько ветвей у нашего дерева на последнем уровне. Это подтверждает, что вариантов действительно шесть.
Ещё один пример
Пусть нужно составить трёхзначный код из цифр 1 и 2, причём цифры могут повторяться. На каждом из трёх мест можно поставить одну из двух цифр, поэтому дерево на каждом шаге раздваивается.
На первом месте: 2 варианта
На втором месте: 2 варианта
На третьем месте: 2 варианта
Всего: 2 × 2 × 2 = 8 кодов
Дерево покажет все восемь кодов — от 111 до 222. Так перебор по дереву помогает не только сосчитать варианты, но и выписать каждый из них.
Когда дерево особенно полезно
- Нужно не просто сосчитать варианты, но и выписать их все.
- Важно не пропустить ни одного и не повторить дважды.
- Выбор делается в несколько шагов подряд.
Частые ошибки
- Складывают числа вместо умножения и получают неверное количество.
- Пропускают некоторые ветви и теряют часть вариантов.
- Повторяют один и тот же вариант дважды.
Кратко о главном
- Дерево вариантов перечисляет все возможные решения.
- Каждая ветвь — это один из выборов на очередном шаге.
- Общее число вариантов равно произведению числа выборов на каждом шаге.
- Дерево помогает не пропустить и не повторить ни одного варианта.