Перебор вариантов полезен, когда нужно найти все сочетания, маршруты или коды. Главное — не пропустить вариант и не посчитать его дважды. Начинайте с упорядоченного списка или таблицы.
Таблица сочетаний
| Футболка | Красная кепка | Серая кепка | Чёрная кепка |
|---|---|---|---|
| Белая | Белая + красная | Белая + серая | Белая + чёрная |
| Синяя | Синяя + красная | Синяя + серая | Синяя + чёрная |
Если каждый выбор первого предмета можно сочетать с каждым выбором второго, число сочетаний равно произведению количеств вариантов.
Для каждой из двух футболок доступны три кепки. Всего 2 · 3 = 6 наборов. Каждый набор содержит одну футболку и одну кепку; перестановка слов не создаёт новый набор.
Когда складывать
Есть 3 вида сока и 2 вида чая. Выбирают один напиток, поэтому вариантов 3 + 2 = 5. Здесь не составляют пару «сок и чай», а берут один вид из двух непересекающихся групп.
Слова «один из всех» и «один каждого вида» описывают разные выборы. Если в группах есть одинаковые варианты, простая сумма требует осторожности: одинаковый вариант нельзя считать дважды.
Маршруты из двух этапов
Из A в B ведут 2 пути, из B в C — 3. Каждый первый путь можно продолжить любым вторым, значит маршрутов A–B–C будет 6. Вопрос относится именно к двухэтапным маршрутам через B.
Коды
Код из двух позиций использует цифры 0, 1 и 2. Повторения разрешены, первая цифра тоже любая из списка. Коды: 00, 01, 02, 10, 11, 12, 20, 21, 22. Всего 3 · 3 = 9.
Код может начинаться с нуля, если это разрешено. Двузначное натуральное число с нуля не начинается. Поэтому слова «код» и «двузначное число» нельзя подменять друг другом. Без повторений число вариантов тоже изменилось бы.
Номера включительно
Билеты пронумерованы от 7 до 11 включительно: 7, 8, 9, 10, 11. Их пять. Разность 11 − 7 = 4 считает промежутки между номерами; для числа билетов прибавляют 1.
Общий способ для последовательных целых номеров: последний − первый + 1. Условие «включительно» означает, что оба крайних номера входят в список.
Проверка перебора
Выберите порядок: сначала фиксируйте первый предмет, затем перебирайте все вторые. После завершения первой строки переходите к следующей. Для маленьких чисел сравните длину списка с результатом умножения.
В «Десанте» используются только два небольших количества вариантов и один выбор либо пара. Длинный перебор кодов и подсчёт номеров включительно оставлены другим играм.
Проверьте себя
1. 3 футболки и 2 кепки. Сколько наборов?
6.
2. 4 вида сока и 3 вида чая, один напиток. Вариантов?
7.
3. Код из двух позиций, цифры 0 и 1, повторы разрешены, первая любая. Сколько кодов?
4: 00, 01, 10, 11.
4. Номера от 12 до 18 включительно. Сколько?
18 − 12 + 1 = 7.