Полный перебор

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

Идея полного перебора

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

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

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

Математическая модель и оценка числа нұсқа

Пусть есть \(k\) позиций, а на каждую позицию можно независимо поставить один из \(n\) символов. Тогда количество последовательностей равно \(n^k\). Если на первой позиции \(n_1\) нұсқа, на второй \(n_2\) и так далее, общее число нұсқа находится правилом произведения.

Если выбираются \(k\) различных элементов из \(n\) без повторений и порядок важен, число нұсқа равно \(n(n-1)\ldots(n-k+1)\). Если порядок не важен, варианты считают иначе — это относится к перебору комбинаций. На практике сначала удобно оценить \(N\), а уже затем решать, допустим ли полный перебор по времени.

Для каждой проверки оценивают время жұмысы. Если нұсқа \(N\), а проверка бір нұсқа занимает \(O(1)\), то весь алгоритм имеет сложность \(O(N)\). Если проверка сама требует \(k\) действий, сложность становится \(O(Nk)\). Подробные способы сокращения такого поиска рассматриваются на странице сложность перебора с возвратом.

Как построить алгоритм перебора

Удобный план шешімдер состоит из последовательных қадам.

1. Определить, что именно является одним вариантом: число, пару чисел, слово или набор значений.
2. Записать допустимые границы каждой переменной.
3. Понять, допускаются ли повторения и важен ли порядок.
4. Сформулировать точную проверку условия.
5. Выбрать действие после успешной проверки: посчитать, вывести, найти максимум, минимум или сохранить вариант.
6. Проверить граничные случаи: пустой набор, нулевые значения, одинаковые элементы и крайние границы циклов.

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

answer := 0
for x from xmin to xmax:
    for y from ymin to ymax:
        if condition(x, y):
            answer := answer + 1

Разобранный пример

Найдём количество трёхзначных чисел \(abc\), составленных из цифр \(0,1,2,3,4\), в которых цифры не повторяются и число делится на 5. Первая цифра не может быть нулём. Число делится на 5 тогда и только тогда, когда последняя цифра равна 0 или 5. Цифры 5 среди разрешённых нет, значит последняя цифра обязана быть 0.

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

1count = 0
2for a in range(1, 5):
3    for b in range(5):
4        for c in range(5):
5            if len({a, b, c}) == 3 and (100 * a + 10 * b + c) % 5 == 0:
6                count += 1
7print(count)

Программа перебирает \(4\cdot5\cdot5=100\) троек, но засчитывает только подходящие. Ответ равен 12. Вручную мы использовали свойство делимости и сократили перебор до подсчёта \(4\cdot3\).

Ошибки и проверка результата

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