Систематический перебор вариантов

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

Алгебра, 8 класс · Л. Г. Петерсон, Н. Х. Агаханов, А. Ю. Петрович, О. К. Подлипский, М. В. Рогатова, Б. В. Трушин · § 1. Элементы комбинаторики

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

Пример 1 (таблица). Двузначный код составляют из букв К, Л, М, Н, О, У, Ы так, что на первом месте стоит гласная, а на втором — согласная. Строки таблицы — гласные, столбцы — согласные, в каждой клетке — свой код:

КЛМН
ООКОЛОМОН
УУКУЛУМУН
ЫЫКЫЛЫМЫН

Ни один код не пропущен и не повторён: кодов 3 · 4 = 12.

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

Пример 2 (дерево). Сколько «слов» из трёх разных букв можно составить из букв П, Р, С, Т? Закрепим на первом месте букву П. Вторая буква — Р, С или Т (три ветви), третья — одна из двух оставшихся (по две ветви): ПРС, ПРТ, ПСР, ПСТ, ПТР, ПТС — шесть слов. Любая из четырёх букв может стоять первой, и для каждой слов столько же: 6 · 4 = 24.

Метод систематического перебора (подсчёт комбинаций из различных символов)

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

Пример 3 (ограничение). Сколько двузначных чисел с различными цифрами можно составить из цифр 0, 3, 5, 8? Ноль не может стоять первым — у него свойство не такое, как у остальных цифр. Для первой цифры 3 вторая — 0, 5 или 8 (три числа), так же для 5 и для 8, а для 0 — ни одного: 3 + 3 + 3 + 0 = 9 чисел.

Зачем это

1 / 12

Найти все варианты

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

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

Пример

2 / 12

Таблица вариантов

Код из двух букв: первая — гласная О, У, Ы, вторая — согласная К, Л, М, Н.

КЛМН
ООКОЛОМОН
УУКУЛУМУН
ЫЫКЫЛЫМЫН

Ни один код не пропущен и не повторён: кодов 3 · 4 = 12.

Проверь себя

3 / 12

Добавили букву

К гласным О, У, Ы добавили Э; согласные те же: К, Л, М, Н.

Сколько теперь кодов?

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

Строк 4, столбцов 4: 4 · 4 = 16 кодов.

Правило

4 / 12

Схема-дерево

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

Каждая ветвь сверху вниз — один вариант.

Наглядно

5 / 12

Дерево для буквы П

Дерево: вверху П; от неё три ветки Р, С, Т; от каждой две ветки к двум оставшимся буквам. Внизу шесть слов: ПРС, ПРТ, ПСР, ПСТ, ПТР, ПТС.
Дерево: вверху П; от неё три ветки Р, С, Т; от каждой две ветки к двум оставшимся буквам. Внизу шесть слов: ПРС, ПРТ, ПСР, ПСТ, ПТР, ПТС.

«Слова» из трёх разных букв П, Р, С, Т с буквой П первой — их шесть.

Разбор

6 / 12

Все слова

Сколько «слов» из трёх разных букв можно составить из букв П, Р, С, Т?

  1. Первая П

    С буквой П первой — 6 слов (по дереву).

  2. Любая первая

    Первой может стоять любая из 4 букв, и для каждой слов столько же.

  3. Ответ

    6 · 4 = 24 слова.

Правило

7 / 12

Метод перебора

Метод систематического перебора (комбинации из различных символов):

  1. Закрепить на первом месте один из символов.
  2. Для этого случая выписать все варианты таблицей, деревом или иначе и сосчитать их.
  3. Если любой символ может стоять на любом месте, умножить это число на количество символов.
  4. Если есть ограничения, сосчитать варианты отдельно для символов с разными свойствами и сложить.

Проверь себя

8 / 12

Слова из трёх букв

«Слова» из трёх разных букв А, Б, В.

Сколько таких слов?

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

Первая А: АБВ, АВБ — 2 слова; 2 · 3 = 6.

Разбор

9 / 12

Ноль первым не бывает

Сколько двузначных чисел с различными цифрами можно составить из цифр 0, 3, 5, 8?

  1. Ограничение

    Ноль не может стоять первым: его свойство не такое, как у остальных цифр.

  2. Подсчёт

    Первая 3: вторая 0, 5 или 8 — три числа; так же для 5 и для 8; первая 0 — ни одного.

  3. Ответ

    3 + 3 + 3 + 0 = 9 чисел.

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

10 / 12

Забыли про ноль

«3 · 4 = 12 чисел» — неверно!

Среди этих записей 03, 05, 08 — не двузначные числа.

12 - 3 = 9 — сходится с подсчётом по группам.

Проверь себя

11 / 12

Цифры 0, 1, 2

Двузначные числа с различными цифрами из цифр 0, 1, 2.

Сколько таких чисел?

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

10, 12, 20, 21: 2 + 2 + 0 = 4.

Главное

12 / 12

Главное

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

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

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

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