Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

Перебор вариантов и дерево вариантов

Содержание

В уроке Диаграммы в задачах вы делили целое на части и находили, какую долю занимает каждая. Теперь посчитаем, из скольких вариантов состоит целое, когда нужно что-то выбрать или составить. Вы научитесь выписывать все варианты без пропусков и повторов — списком, таблицей и деревом — и считать их умножением.

Чтобы ничего не потерять, варианты выписывают по порядку

Замок школьного шкафчика открывается кодом из трех разных цифр $1$, $2$, $3$. Код вы забыли, но помните, что каждая цифра входит в него один раз. Сколько попыток понадобится в худшем случае, если пробовать каждый код по одному разу? Сначала выпишем все коды по порядку, а в конце урока получим тот же ответ без списка — одним умножением.

Если записывать коды как придется — $213$, $123$, $312$, $132$… — легко пропустить один код или записать другой дважды. Поэтому каждый возможный ответ называют вариантом, а выписывание всех вариантов по одному — перебором. Чтобы перебор был полным, его ведут по порядку: сначала все коды на $1$, затем на $2$, затем на $3$. Внутри каждой группы так же: по второй цифре от меньшей к большей.

Пример 1

Задача. Выпишите все коды из цифр $1$, $2$, $3$, в которых каждая цифра встречается один раз.

Решение. Первая цифра $1$: вторая может быть $2$ или $3$, третья — оставшаяся. Получаем $123$, $132$.

Первая цифра $2$: $213$, $231$. Первая цифра $3$: $312$, $321$.

В каждой группе по $2$ кода, групп $3$. Код $213$ и код $231$ разные: те же цифры, но в другом порядке.

Ответ: $6$ различных кодов.

Коды из цифр 1, 2, 3: сверху список как придется (213 повторился, 231 и 321 пропали), снизу по порядку три группы по первой цифре, всего шесть
Список по порядку делится на группы по первой цифре: в каждой группе по 2 кода, всего 6

Ошибка

Иногда считают, что $123$ и $213$ — один вариант: цифры те же.

Проверим на замке. Если код $123$, а вы набрали $213$, замок не откроется. Значит, это два разных варианта.

Где сломалось рассуждение. В коде и в числе важно, на каком месте стоит цифра: поменяли порядок — получили другой вариант, как $12$ и $21$: цифра $1$ может стоять и на первом, и на втором месте.

В наряде иначе. «Белая футболка и черные шорты» и «черные шорты и белая футболка» — один наряд: футболку выбирают на первом шаге, шорты на втором, футболка не может оказаться на месте шорт. Второе название — просто другая запись того же наряда.

Правило

Перебор ведут по порядку: сначала делят варианты на группы по первому выбору, внутри группы — по второму и так далее. Тогда каждый вариант попадет в список ровно один раз.

Когда выбирают два раза, варианты удобно уложить в таблицу

У Маши три футболки — белая (Б), красная (К), зеленая (З) — и двое шорт — черные (Ч) и синие (С). Наряд — это одна футболка и одни шорты. Сделаем таблицу: строки — футболки, столбцы — шорты. На пересечении строки и столбца стоит один наряд.

Таблица нарядов 3 на 2: три футболки в строках, двое шорт в столбцах, 6 клеток-нарядов
Каждая клетка — один наряд: 3 строки по 2 клетки дают 6 нарядов

Что видно в таблице? Каждая футболка встречается в своей строке столько раз, сколько есть шорт, — два. Ни одна клетка не пустая и ни одна не повторяется. Значит, таблица сама следит, чтобы не было пропусков и повторов. Нарядов столько, сколько клеток: $3$ строки по $2$ клетки, то есть $3 \cdot 2 = 6$.

Правило

Если выбирают из двух наборов и каждый элемент первого сочетается с каждым элементом второго, число вариантов равно числу клеток таблицы:

$$\text{число вариантов} = \text{строки} \cdot \text{столбцы}$$

Почему так? Клетки таблицы можно считать по строкам: в каждой строке столько клеток, сколько столбцов, а строк — сколько элементов в первом наборе. Это и есть умножение.

Дерево вариантов показывает каждый выбор отдельным шагом

Таблица хороша для двух выборов, а для трех она не годится: в ней нельзя показать три выбора сразу. Нарисуем те же наряды по-другому. Из одной точки слева проведем три линии — по одной на каждую футболку. Из конца каждой проведем две линии — по одной на каждые шорты. Получилось дерево вариантов.

Определение

Дерево вариантов — схема, в которой каждый шаг выбора — это ярус, каждый возможный выбор на шаге — ветвь, а конец пути от начала дерева — лист. Каждый путь от начала до листа — один вариант. Точку, с которой начинается дерево, называют корнем, а точки, где ветви расходятся или заканчиваются, — вершинами.

Дерево нарядов: три футболки, из каждой две пары шорт, 6 листьев; выделен путь К, С и лист КС; подписаны корень, ярусы, ветвь и лист
Путь К → С — это наряд «красная футболка и синие шорты»; листьев 6, как клеток в таблице

Прочитаем выделенный путь: на первом ярусе выбрана красная футболка, на втором — синие шорты. Каждый лист дерева совпадает с одной клеткой таблицы: шесть листьев — шесть клеток. Список кодов из раздела 1 тоже был деревом, только записанным строчками: группы по первой цифре — это ветви первого яруса.

Чем дерево удобнее таблицы? К каждому листу можно дорисовать еще ярус — например, кроссовки. Число листьев сразу видно, и любой вариант можно прочитать по пути.

Связь работает и в обратную сторону. Если листьев $6$, а вершин первого яруса $3$, то из каждой вершины выходит $6 : 3 = 2$ ветви.

Запрет срезает ветви дерева

Иногда не все варианты разрешены. Составим двузначные числа из цифр $0$, $1$, $2$ без повторов цифр. Двузначное число не может начинаться с нуля: запись $01$ — это просто число $1$. Значит, на первом ярусе ветвь «$0$» запрещена.

Пример 2

Задача. Сколько двузначных чисел без повторов цифр можно составить из цифр $0$, $1$, $2$?

Решение. Первый ярус — первая цифра: $0$, $1$ или $2$. Ветвь $0$ вычеркиваем: число не начинается с нуля.

Второй ярус — вторая цифра, любая из двух оставшихся. Из $1$ идут ветви $0$ и $2$, из $2$ — ветви $0$ и $1$.

Листья: $10$, $12$, $20$, $21$. Без запрета было бы $3 \cdot 2 = 6$ вариантов, запрет убрал $01$ и $02$.

Ответ: $4$ числа.

Двузначные числа из цифр 0, 1, 2 без повторов: ветвь с первой цифрой 0 запрещена, остаются 10, 12, 20, 21
Ветвь «0» на первом ярусе срезана вместе с ее листьями: из 6 вариантов остается 4

Обратите внимание: на втором ярусе цифра $0$ разрешена — число $10$ правильное двузначное. Запрет касается только первого места. А условие «без повторов» видно по числу ветвей: из каждой вершины первого яруса выходят две ветви второго яруса, а не три, потому что одна цифра уже занята.

Правило

Запрет вычеркивает ветвь вместе со всеми ее продолжениями. Чтобы посчитать варианты с запретом, считают все варианты и вычитают запрещенные — или сразу не рисуют запрещенные ветви.

Число листьев можно найти, не рисуя дерево

Посмотрите еще раз на дерево нарядов. На первом ярусе $3$ ветви, и из каждой вырастает одинаковая группа — $2$ ветви. Число листьев равно числу групп, умноженному на размер группы: $3 \cdot 2 = 6$. Если ярусов три, то каждая вершина второго яруса даст свою одинаковую группу ветвей, и число листьев снова умножается.

Правило умножения

Если на первом шаге есть $a$ вариантов, а на втором — $b$ вариантов при любом первом выборе, то всего вариантов $a \cdot b$. Если есть третий шаг с $c$ вариантами при любых первых двух выборах, то:

$$\text{число вариантов} = a \cdot b \cdot c$$

Ошибка

Клеозавр считает: «$3$ футболки и $2$ пары шорт — значит, $3 + 2 = 5$ нарядов».

Проверим на числах. Выпишем все наряды по таблице: БЧ, БС, КЧ, КС, ЗЧ, ЗС. Их $6$, а не $5$.

Где сломалось рассуждение. Сложение подходит, когда выбирают что-то одно: либо футболку, либо шорты. В наряде есть и футболка, и шорты, и каждая футболка сочетается с каждыми шортами. На дереве это видно: к каждой из $3$ ветвей первого яруса вырастают $2$ ветви, поэтому листьев $3 \cdot 2$.

Ошибка: 3 + 2 = 5 считает предметы одежды отдельно; дерево показывает 6 листьев, то есть 3 · 2 = 6
Сумма 3 + 2 считает отдельные предметы одежды; нарядов 3 · 2 = 6

Измените число ветвей на первом и втором ярусе. Добейтесь $12$ листьев двумя разными настройками и найдите настройку, при которой счет Клеозавра верен.

Пример 3

Задача. Из поселка $A$ в поселок $B$ ведут $2$ дороги, из $B$ в $C$ — $3$ дороги, из $C$ в $D$ — $2$ дороги. Сколько есть маршрутов из $A$ в $D$ через $B$ и $C$?

Решение. Маршрут — это три выбора подряд: дорога $A \to B$, дорога $B \to C$, дорога $C \to D$.

Дерево имеет три яруса: $2$ ветви, из каждой по $3$, из каждой из них по $2$.

Листьев $2 \cdot 3 \cdot 2 = 12$. Проверка по дереву: на втором ярусе $2 \cdot 3 = 6$ вершин, каждая дает $2$ листа.

Ответ: $12$ маршрутов.

Маршрут A, B, C, D: на участках 2, 3 и 2 дороги; дерево из трех ярусов дает 12 листьев, 2 · 3 · 2 = 12
Три яруса дерева — три участка пути: 2 · 3 · 2 = 12 маршрутов

Теперь вернемся к замку. Первая цифра кода — любая из $3$, вторая — любая из $2$ оставшихся, третья — одна оставшаяся. Вариантов $3 \cdot 2 \cdot 1 = 6$, значит, в худшем случае понадобится $6$ попыток. Список из раздела 1 тоже дал $6$ кодов: ни один код не пропущен и не записан дважды.

Важно

Умножают, когда нужны оба выбора сразу: футболка и шорты. Если выбирают что-то одно — пирожок или булочку, — числа вариантов складывают. Если в буфете $3$ вида пирожков и $2$ вида булочек, а покупают что-то одно, вариантов $3 + 2 = 5$.

Вывод

Подсчет вариантов нужен, чтобы узнать, сколько кодов у замка, сколько обедов можно составить в столовой или сколько маршрутов ведет в соседний поселок. Главное — не потерять ни одного варианта и не посчитать один дважды. Все способы этого урока — одно и то же дерево вариантов: каждый вариант — путь от начала до листа.

Дальше эти подсчеты понадобятся в задачах на вероятность.

Часто задаваемые вопросы

Чем перебор отличается от правила умножения?

Перебор выписывает сами варианты, а умножение только считает, сколько их. Перебор нужен, когда варианты надо назвать или когда условия разные для разных ветвей. Умножение быстрее, но работает, только если на каждом шаге число вариантов одинаково при любом предыдущем выборе.

Когда числа вариантов складывают, а не умножают?

Складывают, когда выбирают что-то одно из нескольких наборов: например, взять либо яблоко из 3 видов, либо грушу из 2 видов — это 5 вариантов. Умножают, когда выбирают из каждого набора по одному и соединяют: футболку и шорты.

Обязательно ли рисовать дерево целиком?

Целиком рисовать необязательно, если из условия известно, что на каждом шаге число продолжений одинаково при любом предыдущем выборе. Тогда можно показать один путь и подписать числа выборов на шагах. Если числа продолжений различаются, разберите группы отдельно. Дерево полезно нарисовать целиком, когда есть запреты: так легче не пропустить срезанные ветви.

Можно ли в задаче про двузначные числа из 0, 1, 2 просто умножить 3 на 2?

Само произведение 3 · 2 = 6 дает лишнее: в него попадают записи 01 и 02, а нуль нельзя ставить первым. Их вычитают: остается 4 числа. Можно сразу учесть запрет: первая цифра — 2 способа (1 или 2), вторая — тоже 2 способа, всего 2 · 2 = 4.

Награды за урок
5
5
1
Количество опыта, полученного за урок 5
Ускорьте прогресс с полным доступом

Переходите к следующим темам и закрепляйте пройденное на практике.

  • Более 330 000 пользователей по всей России, из них 39 000 учителей.
  • Повышение среднего балла по предмету до 20 % после месяца занятий.
  • Всплеск интереса к учебе и более глубокое понимание предметов.
Не потеряйте прогресс!

Создайте бесплатный аккаунт — и откройте больше возможностей:

  • Отслеживайте прогресс освоения тем
  • Получайте персональные подборки полезных уроков и заданий
  • Проводите работу над ошибками после занятий

Спросить Зави Спросить Зави
Получить еще подсказку

Верно! Посмотрите пошаговое решение

Предложить улучшение