Подготовка школьников к олимпиадам по программированию: решение задач на полный перебор

На олимпиадах по программированию частая гостья – задача, в которой приходится из данного множества выбирать некоторое подмножество, удовлетворяющее определенным условиям. Например, из некоторой группы людей выделить подгруппу, которая наилучшим образом взаимодействует друг с другом и делает подгруппу эффективной. Или, из множества ящиков выбрать подмножество, которое наилучшим образом помещается в грузовик и имеет наибольшую ценность.

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

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

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