Дерево хранит варианты
У корневого дерева выделен корень; остальные вершины связаны с ним единственным путём.
В этом занятии
- Самостоятельно решить задачу по теме «Дерево хранит варианты» и объяснить проверку результата.
- Построй дерево выбора обложки: два цвета и три значка. Подпиши все конечные варианты.
Пригодится: informatics9-graph-paths
Разберёмся перед практикой+
Дерево хранит варианты
У корневого дерева выделен корень; остальные вершины связаны с ним единственным путём. Лист не имеет потомков, поддерево начинается в выбранной вершине. В этом уроке высота считается числом рёбер самого длинного пути от корня до листа.
Дерево удобно для иерархии папок и перебора решений. Каждая ветвь фиксирует очередной выбор, лист — полный вариант. Чтобы не получить дубли, нужно заранее задать порядок выбора и не смешивать один и тот же вариант с разными способами его записи.
У корня два потомка, у каждого по три листа. Полных вариантов 2×3=6, высота равна двум рёбрам.
- Определи корень и смысл выбора.
- Проследи пути до листьев.
Попробуй самостоятельно
Запиши рассуждения в черновик или сделай построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Построй дерево выбора обложки: два цвета и три значка. Подпиши все конечные варианты.
- Сначала предположи результат, затем проверь и объясни, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читай и разбирай пример в своём темпе. К практике можно перейти, когда будешь готов.