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

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

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

Зачем перебирать по порядку

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

Правило. Чтобы найти все варианты и ничего не пропустить, перебирайте их по порядку: от меньшего к большему или столбиком. Беспорядочный, случайный перебор почти всегда приводит к ошибкам и пропускам.

Пример: двузначные числа

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

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

Перебор в таблице

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

Различных пар получилось три. Обратите внимание: пару «шоколад и ваниль» отдельно записывать не нужно — это та же самая пара, что и «ваниль и шоколад», ведь порядок вкусов в стаканчике не важен. Одинаковые варианты считать дважды нельзя.

Когда перебор удобен

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

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

Кратко о главном

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