Лабораторная работа № 5. Задание для лабораторной работы

КОМБИНАТОРНЫЕ АЛГОРИТМЫ

Задание для лабораторной работы.

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

2. Написать программу, которая выполняет задание варианта с помощью генерации всех соответствующих комбинаций, используя комбинаторные алгоритмы. При этом:

a) во время генерации производить подсчет общего числа сгенерированных вариантов и число вариантов, удовлетворяющих условию задачи, вывести эти значения на экран;

b) если решение не единственное, то вывод комбинаций осуществлять в файл.

3. Формулу для расчета теоретического значения числа комбинаций, текст программы и результат её работы для контрольного примера оформить в отчёт.

Теоретическая часть

Приведём эффективные алгоритмы, генерирующие основные комбинаторные объекты.

1. Размещения с повторениями.

Данный алгоритм генерирует наиболее общий класс размещений с повторениями, когда i -ый элемент размещения выбирается из своего множества X_i. Генерация выполняется в лексикографическом порядке.

Используемые обозначения:

A – массив, содержащий размещение;

x – массив, содержащий минимальные значения элементов размещения;

y – массив, содержащий максимальные значения элементов размещения;

k – количество элементов в размещении.

Begin

i: = k; for j: =1 to k do A_j : = x_j ;

While i ³ 1 do

begin вывод массива A;

i: = k;

while A_i = y_i do i: = i -1;

if i ³ 1 then begin A_i : = A_i +1;

for j: = i +1 to k do A_j : = x_j ;

End

End

End.

2. Перестановки без повторений.

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

Используемые обозначения:

P – массив, содержащий перестановку;

n – количество элементов в перестановке;

«– поменять местами переменные.

procedure reverse (m)

begin i: =1; j: = m;

while i < j do begin P_i «P_j ;

i: = i +1; j: = j -1

End

end;

procedure Antilex (m)

begin if m =1 then вывод массива P

else for i: =1 to m do

begin Antilex (m -1);

If i < m then

begin P_i «P_m ;

reverse (m -1)

End

End

end;

Begin

for i: =1 to n do P_i : = i;

Antilex (n);

end.

3. Сочетания без повторений.

Генерация сочетаний без повторений так же, как и размещений с повторениями, выполняется в лексикографическом порядке.

Используемые обозначения:

С – массив, содержащий сочетание;

k – количество элементов в сочетании;

n – количество элементов в исходном множестве.

Begin

for i: =1 to k do C_i : = i;

p: = k;

While p ³ 1 do

begin вывод массива C;

if C_k = n then p: = p -1

else p: = k;

if p ³ 1 then for i: = k downto p do

C_i : = C_p + i – p +1

End

end.

4. Размещения без повторений.

При генерации размещений без повторений используется комбинация двух алгоритмов: генерация сочетаний без повторений и перестановок без повторений. Для этого в алгоритме генерации сочетаний без повторений вместо печати сгенерированной комбинации выполняется генерация всех её перестановок (так как размещения отличаются от сочетаний тем, что в них учитывается порядок выбранных элементов). При реализации этого алгоритма сначала в массиве С генерируется сочетание, затем, вместо вывода массива С, его элементы копируются в массив P и вызывается рекурсивная процедура генерации перестановок.