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

Определения и обозначения

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

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

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

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

Как это устроено

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

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

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

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

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

Этапы решения задачи методом перебора

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

Разбор задач

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

Условие: составьте все двузначные числа, которые можно записать с помощью цифр 1, 2 и 3 без повторения цифр. Число состоит из цифры десятков и цифры единиц, поэтому их порядок важен. Будем выбирать десятки по очереди, а для каждого выбора перебирать оставшиеся цифры.

1. Поставим в разряд десятков цифру 1. В разряд единиц можно поставить 2 или 3, поэтому получаем числа 12 и 13. Цифру 1 повторять нельзя.

2. Теперь выберем для десятков цифру 2. На месте единиц остаются цифры 1 и 3, значит, получаются числа 21 и 23. Каждый из этих вариантов записан один раз.

3. Последней фиксируем цифру 3 в разряде десятков. Для единиц остаются 1 и 2, поэтому получаем числа 31 и 32. Все три цифры уже побывали в разряде десятков.

Ответ: 12, 13, 21, 23, 31, 32. Перебор завершён, потому что для каждой цифры десятков проверены все две оставшиеся цифры единиц.

Комплекты одежды

Условие: у Маши есть 3 футболки и 2 пары брюк. Нужно узнать, сколько различных комплектов она может составить. Каждый комплект состоит из одной футболки и одной пары брюк. Чтобы не потерять сочетания, переберём брюки отдельно для каждой футболки.

1. Обозначим футболки буквами А, Б и В, а пары брюк — цифрами 1 и 2. Для футболки А подходят оба варианта брюк, значит, получаются комплекты А1 и А2. Здесь рассмотрены все сочетания с первой футболкой.

2. Для футболки Б снова проверяем обе пары: получаем Б1 и Б2. Смена футболки создаёт новые комплекты, даже если пара брюк та же самая.

3. Для футболки В получаем В1 и В2. Других футболок нет, а у каждой перебраны обе пары брюк, поэтому список полный.

Ответ: 6 различных комплектов. Такой список можно расположить в таблице: каждой футболке соответствует строка с двумя вариантами брюк.

Трёхзначные числа, делящиеся на 3

Условие: из цифр 0, 1, 2 и 3 составьте все трёхзначные числа без повторения цифр, которые делятся на 3. Ноль не может стоять первым, иначе число не будет трёхзначным. Сначала систематически составим допустимые числа, а затем проверим делимость: число делится на 3, если сумма его цифр делится на 3.

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

2. Проверим числа по сумме цифр. Если в числе использованы 0, 1 и 2, сумма равна 3; если использованы 0, 2 и 3, сумма равна 5. Набор цифр 0, 1 и 3 даёт сумму 4, а набор 1, 2 и 3 — сумму 6.

3. Подходят наборы 0, 1, 2 и 1, 2, 3, потому что их суммы делятся на 3. Перебирая перестановки каждого набора, исключаем те, где первой стоит 0: для первого набора остаются 4 числа, для второго — все 6.

Ответ: 102, 120, 201, 210, 123, 132, 213, 231, 312, 321. В каждом числе цифры не повторяются, первая цифра не нулевая, а сумма цифр делится на 3.

Типичные ошибки

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

Один вариант иногда записывают несколько раз в разном порядке, не разобравшись, важен ли порядок объектов. Например, числа 12 и 21 — разные числа, а в задаче о выборе двух одинаковых по роли предметов перестановка может не создавать новый вариант. Чтобы проверить себя, уточни по условию, считается ли изменение порядка новым результатом, и придерживайся одного правила записи.

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

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

Связь с другими темами

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

Что запомнить

• Метод перебора означает последовательную проверку всех допустимых вариантов.
• Перебор применяют, когда число вариантов конечно и их можно перечислить.
• Перебор должен быть полным.
• Варианты нужно рассматривать систематически.
• Каждый вариант проверяют по условию задачи.
• Нельзя допускать пропуски и повторы.
• Ответ формулируют только после завершения полного перебора.