Нерекурсивный алгоритм

Полный перебор с отсечением

Реализация рекурсивного алгоритма

Рекурсивный алгоритм

Пример сравнения рекурсивного и нерекурсивного алгоритма

Задача. Двое друзей решили пойти в поход, собрали и взвесили все необходимые вещи. Как им разделить набор предметов на две части наиболее честным образом?

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

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

program pohod_rec;

var f: text;

a: array[1..100] of integer;

n: integer;

min,obsh_ves: longint;

procedure step(t:byte; ves:longint);

var j: longint;

begin

j:= abs(obsh_ves - 2*ves);

if j<min then min:= j;

for j:= t+1 to n do step(j,ves+a[t]);

end;

begin

assign(f,'in');

reset(f);

n:=0; {кол-во всех предметов}

obsh_ves:= 0;

while not eof(f) do

begin inc(n);

read(f,a[n]);

inc(obsh_ves,a[n]);

end;

close(f);

min:= MaxLongInt;

step(1,0);

writeln('difference ',min)

end.

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

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

Здесь нам потребуется несколько дополнительных рассуждений и линейных массивов.

Основная часть приводимой ниже программы является итеративной реализацией алгоритма полного перебора всех возможных вариантов, удовлетворяющих входным ограничениям. Ее основное отличие от рекурсии - использование малого объема памяти для хранения текущих данных. Вся информация хранится в массивах ves, take и dif. Для вычислений на каждом шаге используется только эта информация. Такой подход позволяет избежать непрерывных перевычислений, которые и являются причиной "тяжеловесности" рекурсивного алгоритма.

Итак, первая часть программы должна заниматься подсчетом и упорядочением вводимых предметов по убыванию их весов. Для экономии места мы не станем приводить подробную реализацию этого блока: здесь годится любой метод сортировки (см. лекцию 4). Важно лишь, что в результате этой сортировки все входные данные будут записаны в два линейных массива длины k (количество разных весов).

Считаем теперь, что массив ves хранит различные веса предметов, упорядоченные по убыванию, а массив kol - количество предметов каждого веса.

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

Мы не приводим в тексте программы и реализацию функции min() - как не представляющую особенного интереса.