2.17. Перебор возможных вариантов

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

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

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

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

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

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

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

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

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

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

Способы перебора возможных вариантов

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

Разбор задач

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

У Маши есть красная и синяя футболки и чёрные и белые брюки. Нужно составить комплекты из одной футболки и одних брюк, то есть в каждом комплекте должны быть оба предмета. Будем перебирать по цвету футболки, чтобы не смешивать группы. Для каждой футболки запишем все возможные брюки.

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

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

Маршруты между городами

Из города А в город Б ведут две дороги, а из Б в В — три. Нужно узнать число способов проехать из А в В через Б. Дорога от А до Б — первый выбор, дорога от Б до В — следующий. Для каждой дороги первого участка надо учесть все три продолжения.

1. Обозначим дороги из А в Б как первая и вторая.
2. Для первой дороги перечислим три дороги из Б в В: получатся три маршрута.
3. Для второй дороги снова перечислим все три продолжения: получатся ещё три маршрута.
4. Сложим две группы: 3 + 3 = 6. В дереве это две ветви первого шага, и от каждой отходят три ветви второго шага.

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

Двузначные числа

Нужно составить все двузначные числа из цифр 1, 2 и 3, не повторяя цифры. В двузначном числе есть цифра десятков и цифра единиц, поэтому сначала сгруппируем числа по цифре десятков. Затем для каждой группы возьмём только оставшиеся цифры единиц. Так запрет на повторение будет соблюдён автоматически.

1. Если цифра десятков 1, то в единицах могут стоять 2 или 3: получаются 12 и 13.
2. Если цифра десятков 2, то остаются 1 и 3: получаются 21 и 23.
3. Если цифра десятков 3, то остаются 1 и 2: получаются 31 и 32.
4. В каждой группе два числа, а групп три: всего 2 + 2 + 2 = 6.

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

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

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

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

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

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

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

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

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

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