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

  • 3 мин чтения
  • Послушать — 2 мин
  • 7 карточек

Математика, 5 класс · Н. Я. Виленкин, В. И. Жохов, А. С. Чесноков, С. И. Шварцбурд

Сколько флагов из двух вертикальных полос разного цвета можно составить из жёлтого, белого и чёрного цветов? Переберём варианты по порядку.

Левая полоса может быть любого из 3 цветов. Для каждого её цвета правая полоса — любой из 2 оставшихся. Это удобно рисовать деревом: от корня — 3 ветки (левая полоса), от каждой — ещё по 2 (правая полоса). Концов у дерева 3 · 2 = 6 — столько и флагов.

Задачи, в которых перебирают все возможные варианты (комбинации), называют комбинаторными, а раздел математики — комбинаторикой.

Типичная ошибка: перебирать «как придётся» и пропустить или повторить вариант. Перебор по дереву ничего не теряет.

Зачем это

1 / 7

Сколько флагов?

Флаг — из двух вертикальных полос разного цвета. Цвета: жёлтый, белый и чёрный.

Сколько разных флагов можно составить?

Наглядно

2 / 7

Дерево вариантов

Дерево вариантов: от начала три ветки — жёлтый, белый, чёрный (левая полоса), от каждой ещё по две ветки — два оставшихся цвета (правая полоса); внизу шесть флагов: ЖБ, ЖЧ, БЖ, БЧ, ЧЖ, ЧБ
Дерево вариантов: от начала три ветки — жёлтый, белый, чёрный (левая полоса), от каждой ещё по две ветки — два оставшихся цвета (правая полоса); внизу шесть флагов: ЖБ, ЖЧ, БЖ, БЧ, ЧЖ, ЧБ

От начала — 3 ветки: левая полоса. От каждой — ещё 2: правая полоса.

Концов 3 · 2 = 6 — столько и флагов.

Определение

3 / 7

Комбинаторика

Задачи, в которых перебирают все возможные варианты (комбинации), называют комбинаторными.

Раздел математики о таких задачах — комбинаторика.

Разбор

4 / 7

Капитан и вратарь

В команде 4 игрока. Нужно выбрать капитана и вратаря — двух разных ребят. Сколькими способами?

  1. Капитан

    Капитаном может стать любой из 4.

  2. Вратарь

    Для каждого капитана вратарь — любой из 3 остальных.

  3. Ответ

    4 · 3 = 12 способов.

Проверь себя

5 / 7

Четыре цвета

Левая полоса — любой цвет, правая — любой из оставшихся.

Сколько флагов из двух вертикальных полос разного цвета можно составить из 4 цветов?

81612
Ответ и объяснение

Левая полоса — 4 цвета, правая — 3 оставшихся: 4 · 3 = 12.

Частая ошибка

6 / 7

Перебор как придётся

Ошибка: ЖБ, БЧ, ЧЖ, БЖ, ЖБ — пять флагов? (Первая буква — левая полоса.)

ЖБ записан дважды, а ЖЧ и ЧБ потеряны.

По дереву: ЖБ, ЖЧ, БЖ, БЧ, ЧЖ, ЧБ — ровно 6.

Главное

7 / 7

Главное

  • Комбинаторные задачи — перебор всех вариантов; раздел — комбинаторика.
  • Перебирают по порядку, удобно — деревом.
  • Флаги из 2 полос разного цвета, 3 цвета: 3 · 2 = 6.
  • Концы дерева — все варианты.

Проверь себя: тест по теме

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

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест