Комбинаторные задачи

Министерство образования Республики Беларусь

Учреждение образования

«Гомельский государственный университет им. Ф. Скорины»

Математический факультет

Кафедра МПУ

Реферат

Комбинаторные задачи

Исполнитель:

Студентка группы М-42 Макарченко А.Ю.

Научный руководитель: Долинский М.С.

Гомель 2005

Содержание

Введение

Генерация k-элементных подмножеств

Генерация всех подмножеств данного множества

Генерация всех перестановок n-элементного множества

Разбиения множества

Заключение

Литература

Введение

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

const nmax = 24;

type list = array[1..nmax] of integer;var k,i,j,n,q : integer;a,p : list;procedure print(k : integer);

var i:integer;beginfor j:=1 to k dowrite(p[j]:4);writelnend;{print}

procedure cnk(n,k : integer);procedure gen(m,L : integer);var i:integer;beginif m=0 then print(k) elsefor i:=L to n-m+1 dobegin

p[k-m+1]:=a[i];

gen(m-1,i+1)

end

end;{gen}

begin {cnk}gen(k,1)end;{cnk}begin {main}readln(n,k);for i:=1 to n doa[i]:=i;{заполнить массив можно и по-другому}

cnk(n,k)

end.

Заметим, что собственно генерация сочетаний производится в рекурсивной подпрограмме gen. Она имеет следующие параметры: m - сколько элементов из множества нам еще осталось выбрать и L - начиная с какого элемента исходного множества, следует выбирать эти m элементов. Обратите внимание, что именно вложенная структура описания процедур cnk и gen позволяет не передавать при рекурсивных вызовах значения n и k, а из основной программы обращаться к процедуре cnk с параметрами, соответствующими постановке задачи, не вдаваясь в подробности ее решения. Такой способ будем применять и в дальнейшем.

Далее процедура дословно совпадает с предыдущей версией. В основной же программе единственное обращение к данной процедуре следует заменить следующим фрагментом:

k:=0;

flag:=false;

repeat

k:=k+1;

cnk(n,1,flag)

until flag or (k=n);

if flag then print(k)

else writeln('no solution');

Очевидно также, что в основной программе запрос значения переменной k теперь не производится.

Существует также альтернативный подход к перебору всех подмножеств того или иного множества. Каждое подмножество можно охарактеризовать, указав относительно каждого элемента исходного множества, принадлежит оно данному подмножеству или нет. Сделать это можно, поставив в соответствие каждому элементу множества 0 или 1. То есть каждому подмножеству соответствует n-значное число в двоичной системе счисления (строго говоря, так как числа могут начинаться с произвольного количества нулей, которые значащими цифрами не считаются, то следует заметить, что в соответствие ставятся n- или менее - значные числа). Отсюда следует, что полный перебор всех подмножеств данного множества соответствует перебору всех чисел в двоичной системе счисления. Теперь легко подсчитать и количество различных подмножеств данного множества. Оно равно 2n - 1 (или 2n, с учетом пустого множества). Таким образом, сопоставляя два способа перебора всех подмножеств данного множества, мы получили следующую формулу:

То есть, в рамках сделанной выше оценки на количество допустимых вариантов в переборе, мы можем рассмотреть все подмножества исходного множества только при n 20.

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

Условие. Дан целочисленный массив a[1..N] (N 20) и число M. Найти подмножество элементов массива a[i1], a[i2], ...a[ik] такое, что 1 i1 < i2 < i3 < ... < ik N и a[i1] + a[i2] + ... + a[ik] = M.

Решение. В качестве решения приведем процедуру генерации всех подмножеств, которые можно составить из элементов массива и функцию проверки конкретного подмножества на соответствие условию задачи.

function check(j:longint):boolean;

var k:integer; s:longint;

begin

s:=0;

for k:=1 to n do

if ((j shr (k-1))and 1)=1 {данное условие означает, что в

k-й справа позиции числа j, в 2-й системе, стоит 1}

then s:=s+a[k];

if s=m then

begin

for k:=1 to n do

if ((j shr (k-1))and 1)=1 then write(a[k]:4);

writeln

end

end;

procedure subsets(n:integer);

var q,j:longint;

begin

q:=1 shl n; {таким образом мы помещаем в q число 2^n}

for j:=1 to q-1 do {цикл по всем подмножествам}

if check(j) then exit

end;

Заметим, что если все элементы в массиве положительные, то, изменив порядок рассмотрения подмножеств, решение приведенной выше задачи можно сделать более эффективным. Так, если сумма элементов какого-либо подмножества уже больше, чем M, то рассматривать подмножества, включающие его в себя уже не имеет смысла. Пересчет же сумм можно оптимизировать, если каждое следующее сгенерированное подмножество будет отличаться от предыдущего не более, чем на один элемент (такой способ перечисления подмножеств показан в [2]). Приведенная же программа черезвычайно проста, но обладает одним недостатком: мы не можем ни в каком случае с ее помощью перебирать все подмножества множеств, состоящих из более, чем 30 элементов, что обусловлено максимальным числом битов, отводимых на представление целых чисел в Турбо Паскале (32 бита). Но, как уже было сказано выше, на самом деле, перебор всех подмножеств у множеств большей размерности вряд ли возможен за время, отведенное для решения той или иной задачи.

Страницы: 1, 2