Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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





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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Begin

i: = k; for j: =1 to k do Aj : = xj ;

While i ³ 1 do

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

i: = k;

while Ai = yi do i: = i -1;

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

for j: = i +1 to k do Aj : = xj ;

End

End

End.

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

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

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

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

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

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

procedure reverse (m)

begin i: =1; j: = m;

while i < j do begin Pi «Pj ;

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 Pi «Pm ;

reverse (m -1)

End

End

end;

Begin

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

Antilex (n);

end.

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

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

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

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

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

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

Begin

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

p: = k;

While p ³ 1 do

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

if Ck = n then p: = p -1

else p: = k;

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

Ci : = Cp + ip +1

End

end.

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

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







Дата добавления: 2014-11-10; просмотров: 845. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


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


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Классификация потерь населения в очагах поражения в военное время Ядерное, химическое и бактериологическое (биологическое) оружие является оружием массового поражения...

Факторы, влияющие на степень электролитической диссоциации Степень диссоциации зависит от природы электролита и растворителя, концентрации раствора, температуры, присутствия одноименного иона и других факторов...

Йодометрия. Характеристика метода Метод йодометрии основан на ОВ-реакциях, связанных с превращением I2 в ионы I- и обратно...

Конституционно-правовые нормы, их особенности и виды Характеристика отрасли права немыслима без уяснения особенностей составляющих ее норм...

Толкование Конституции Российской Федерации: виды, способы, юридическое значение Толкование права – это специальный вид юридической деятельности по раскрытию смыслового содержания правовых норм, необходимый в процессе как законотворчества, так и реализации права...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

Studopedia.info - Студопедия - 2014-2025 год . (0.012 сек.) русская версия | украинская версия