infraegebeta
v1.0.0
К курсу

Python с нуля для ЕГЭ · Полный перебор: строим и проверяем варианты

Урок курсаPython 35 задачБесплатно

Полный перебор: строим и проверяем варианты

Научимся задавать конечное пространство вариантов и проверять каждый вариант по условию.

Теория

Полный перебор проверяет все допустимые варианты

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

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

solutions = []for number in range(1, 21):    if number % 4 == 0 and number % 6 == 0:        solutions.append(number)

Как доказывается полнота

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

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

Разберём на примере
Найдём пары a меньше b
Обе переменные принимают значения 1, 2 и 3.
  1. Внешний цикл выбирает a, внутренний перебирает все b.
  2. Условие оставляет пары (1,2), (1,3) и (2,3).
  3. Каждая допустимая пара встречается один раз; равные и обратные пары исключены.
Проверьте себя
Почему проверка диапазона так же важна, как условие внутри цикла?
Идеальное условие не сможет принять вариант, который цикл вообще не породил.

Найденный пример ещё не доказывает полноту

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

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

Отделите генерацию кандидатов от проверки. Сначала убедитесь, что range или коллекция покрывает пространство, затем выразите ограничения как проверяемое условие.

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

Практика

Задайте пространство вариантов

Сколько чисел от 1 до 10 включительно делятся на 3?

Подсказка
Проверьте 3, 6 и 9.
Решение

Подходящие варианты — 3, 6 и 9. Их три.

Найдите подходящий вариант

Цикл перебирает x от 1 до 10 и проверяет x * x == 25. Какое x подойдёт?

Подсказка
Нужно найти положительное число с квадратом 25.
Решение

В заданном диапазоне условие выполняется при x = 5.

Посчитайте решения

Сколько чётных чисел среди целых от 1 до 8 включительно?

Подсказка
Чётные числа делятся на 2 без остатка.
Решение

Подходят 2, 4, 6 и 8 — всего четыре варианта.

Проследите вложенный перебор

a и b принимают значения 1, 2, 3. Сколько пар удовлетворяют a < b?

Подсказка
Перечислите пары (1,2), (1,3), (2,3).
Решение

Подходят ровно три упорядоченные пары. Остальные либо равны, либо идут в обратном порядке.

Найдите первое общее кратное

Переберите числа от 1 до 20. Какое наименьшее число делится и на 4, и на 6?

Подсказка
Проверяйте остаток от деления на оба числа.
Решение

Первое число с двумя нулевыми остатками — 12. Число 12 делится на 4 и на 6.

Итог

Теперь вы можете задать конечный перебор, проверить варианты и объяснить, почему ответ не потерян.

Выберите числа от 1 до 30, найдите удовлетворяющие двум условиям и сначала вручную проверьте границы и один отклонённый кандидат.

Прогресс

0 / 5
x

Вы ещё не решали задания