Перебор и подсчёт числа вариантов
💻 Информатика · 6 класс
Перебор и подсчёт числа вариантов
Часто нужно узнать, сколькими способами можно что-то составить: например, собрать наряд из кофты и брюк или придумать код из цифр. Чтобы не ошибиться, варианты перебирают по порядку и подсчитывают. Удобный инструмент для этого — дерево вариантов.
Дерево вариантов
Дерево вариантов — это схема, в которой от каждого выбора ветвятся все возможные продолжения. Сначала рисуют ветви для первого выбора, от каждой из них — ветви для второго выбора, и так далее. Число «листьев» на концах ветвей равно числу всех вариантов.
| Первый выбор | Второй выбор | Готовый набор |
|---|---|---|
| красная кофта | синие брюки | красная + синие |
| красная кофта | чёрные брюки | красная + чёрные |
| белая кофта | синие брюки | белая + синие |
| белая кофта | чёрные брюки | белая + чёрные |
Правило умножения
Если первый выбор можно сделать несколькими способами, а второй — независимо ещё несколькими, то общее число вариантов равно произведению этих чисел. Это правило умножения, которое ускоряет подсчёт без полного рисования дерева.
Разбор примера
Есть 2 кофты и 3 пары брюк. Сколько разных нарядов можно составить? Перечислим перебором и проверим правилом умножения:
кофт: 2
брюк: 3
вариантов: 2 · 3 = 6
Дерево даст ровно 6 листьев: от каждой из 2 кофт отходит по 3 ветви брюк. Перебор и правило умножения дают один и тот же ответ — это хороший способ себя проверить.
Частая ошибка: сложить числа вместо умножения. Сложение даёт неверный ответ: 2 + 3 = 5 — это не число нарядов. Перемножают тогда, когда выборы делаются один за другим и независимо друг от друга.
Три выбора и больше
Правило умножения работает и для трёх, и для большего числа выборов — нужно просто перемножить все возможности. Например, если к 2 кофтам и 3 парам брюк добавить ещё выбор из 2 шапок, общее число нарядов станет таким:
кофт: 2, брюк: 3, шапок: 2
вариантов: 2 · 3 · 2 = 12
| Что выбираем | Сколько способов |
|---|---|
| Кофта | 2 |
| Брюки | 3 |
| Шапка | 2 |
| Всего нарядов | 12 |
Рисовать дерево из двенадцати листьев уже долго, и здесь правило умножения особенно выручает: ответ получается за одно действие.
Где применяется
Подсчёт вариантов нужен, чтобы узнать, сколько разных паролей можно составить, сколько маршрутов ведёт к цели, сколькими способами рассадить гостей. Это основа комбинаторики — раздела математики о подсчёте. В информатике такой подсчёт помогает понять, насколько надёжен пароль: чем больше возможных вариантов, тем труднее его подобрать.
Кратко о главном
- Число вариантов находят перебором или по дереву вариантов.
- Дерево вариантов показывает все продолжения каждого выбора.
- Правило умножения: число вариантов равно произведению возможностей.
- Складывать вместо умножения — частая и грубая ошибка.