Полный конечный перебор и границы

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

Когда применять

  • Параметры и ограничения взяты из условия.
  • Все перечисляемые значения целые; границы области установлены до перебора.

Почему это работает

  1. Устанавливаем из условия конечные границы всех параметров.
  2. Доказываем, что каждый допустимый объект попадает в эту область.
  3. Проверяем условие для каждого набора; для положительного ответа предъявляем подходящий набор, для отрицательного исключаем все наборы.

Пример

Из цифр 0, 1, 2 трехзначное число образуется выбором первой цифры из двух ненулевых и двух остальных цифр из трех: 2⋅3⋅3=182\cdot 3\cdot 3=18. Этот перебор полон, потому что разрядная запись однозначна. Для монет по 2 и 5 рублей с количествами не больше 2 и 1 полная таблица сумм: 0, 2, 40,\,2,\,4 и 5, 7, 95,\,7,\,9. Например, 7=2+57=2+5, а 8 недостижимо.

Граница применения

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

В задаче сначала устанавливаем область, затем находим допустимые значения и предъявляем пример достижения ответа.

Учебные основания
  • Потапов, Шевкин. Математика. Методические рекомендации. 5 класс. Просвещение, 2017.
  • Потапов, Шевкин. Математика. Методические рекомендации. 5 класс. Просвещение, 2017.
  • Потапов, Шевкин. Математика. Методические рекомендации. 5 класс. Просвещение, 2017.
  • Потапов, Шевкин. Математика. Методические рекомендации. 5 класс. Просвещение, 2017.

Авторский вывод из прочитанных правил; задача банка не объявляется примером из книги.

Задачи по этому правилу