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