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

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

Лабораторная работа № 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. Нарушение авторских прав; Мы поможем в написании вашей работы!




Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


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


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


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

В эволюции растений и животных. Цель: выявить ароморфозы и идиоадаптации у растений Цель: выявить ароморфозы и идиоадаптации у растений. Оборудование: гербарные растения, чучела хордовых (рыб, земноводных, птиц, пресмыкающихся, млекопитающих), коллекции насекомых, влажные препараты паразитических червей, мох, хвощ, папоротник...

Типовые примеры и методы их решения. Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно Пример 2.5.1. На вклад начисляются сложные проценты: а) ежегодно; б) ежеквартально; в) ежемесячно. Какова должна быть годовая номинальная процентная ставка...

Выработка навыка зеркального письма (динамический стереотип) Цель работы: Проследить особенности образования любого навыка (динамического стереотипа) на примере выработки навыка зеркального письма...

Характерные черты немецкой классической философии 1. Особое понимание роли философии в истории человечества, в развитии мировой культуры. Классические немецкие философы полагали, что философия призвана быть критической совестью культуры, «душой» культуры. 2. Исследовались не только человеческая...

Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит...

Кран машиниста усл. № 394 – назначение и устройство Кран машиниста условный номер 394 предназначен для управления тормозами поезда...

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