Программы полного перебора (brute force)

Зачем это в ЕГЭ.
Задание 25 в ЕГЭ по информатике проверяет умение применять метод полного перебора для решения задач. Оно оценивается в 2 первичных балла и встречается практически в каждом варианте ФИПИ. Задачи могут быть связаны с поиском оптимальных значений, перебором комбинаций или анализом данных.

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

Алгоритм (чеклист).
1. Определить все возможные варианты, которые нужно перебрать.
2. Организовать циклы для перебора всех комбинаций.
3. Внутри циклов проверить условие задачи.
4. Если условие выполняется, сохранить результат или вывести его.
5. Проверить корректность работы программы на тестовых данных.

Опоры (кратко).
- Количество комбинаций: $N = k_1 \times k_2 \times \dots \times k_n$, где $k_i$ — количество вариантов для каждого параметра.
- Вложенные циклы для перебора всех вариантов.
- Условие задачи, которое проверяется внутри циклов.

Пример 1 (перебор комбинаций)
Шаг 1. Даны числа от 1 до 5. Необходимо найти все пары чисел, сумма которых равна 6.
Шаг 2. Организуем два вложенных цикла: внешний для первого числа, внутренний для второго.
Шаг 3. Внутри циклов проверяем условие: если сумма чисел равна 6, выводим пару.
Шаг 4. Получаем пары: (1, 5), (2, 4), (3, 3), (4, 2), (5, 1).

Пример 2 (оптимизация перебора)
Шаг 1. Даны числа от 1 до 10. Необходимо найти тройки чисел, сумма которых равна 15.
Шаг 2. Организуем три вложенных цикла, но для оптимизации ограничиваем диапазон каждого числа.
Шаг 3. Внутри циклов проверяем условие: если сумма чисел равна 15, выводим тройку.
Шаг 4. Получаем тройки: (1, 5, 9), (2, 4, 9), (3, 5, 7) и т.д.

Типичные ошибки.
1. Неправильный диапазон перебора. Ученики забывают включить граничные значения или перебирают лишние числа.
2. Избыточные циклы. Использование большего количества циклов, чем требуется, что замедляет выполнение программы.
3. Пропуск проверки условий. Забывают добавить условие внутри циклов, что приводит к выводу всех комбинаций.
4. Некорректная проверка результатов. Не тестируют программу на простых данных, чтобы убедиться в её правильности.

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