Розробка алгоритму і програми розв’язання задачі про покриття на множинах методом мінімального стовпчика - максимального рядка та методо
Автор: Retniw • Май 19, 2024 • Лабораторная работа • 1,495 Слов (6 Страниц) • 88 Просмотры
Міністерство освіти і науки України
Вінницький національний технічний університет
Факультет інтелектуальних інформаційних технологій та автоматизації
Кафедра КН
Лабораторна робота №2
з дисципліни «Дискретна математика»
Розробка алгоритму і програми розв’язання задачі про покриття на множинах методом мінімального стовпчика - максимального рядка та методом ядерних рядків.
Виконав: ст. гр. 2КН-23б.
Вінтер Олександр
Перевірив викладач:
Ваховська Л.М.
Вінниця 2024
Мета: набути навиків застосування методу мінімального стовпчика - максимального рядка та методу ядерних рядків для побудови покриття на множинах.
Варіант №2
2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | а | |
A | А | 1 | 1 | 1 | 1 | ||||||
B | Б | 1 | 1 | 1 | 2 | ||||||
C | В | 1 | 1 | 1 | 1 | 1 | 3 | ||||
D | Г | 1 | 1 | 1 | 1 | ||||||
E | Д | 1 | 1 | 1 | 1 | 3 | |||||
F | Е | 1 | 1 | 1 | 1 | 1 | 2 | ||||
G | Ж | 1 | 1 | 1 | 2 |
Практична частина
Метод мінімального стовпчика - максимального рядка
[pic 1]
[pic 2]
Метод ядерних рядків
[pic 3]
[pic 4][pic 5]
Схеми алгоритмів побудови покриття методом мінімального стовпчика - максимального рядка та методом ядерних рядків.
[pic 6]
Рисунок 1 – Схема алгоритму побудови покриття методом мінімального стовпчика - максимального рядка
[pic 7]
Рисунок 2 - Схема алгоритму побудови покриття методом ядерних рядків
Опис програми
Ця програма призначена для знаходження найефективнішого покриття множини. Вона приймає на вхід кількість множин та кількість стовпців, після чого користувач вводить дані у вигляді матриці. Програма обчислює покриття методом мінімального стовпчика - максимального рядка.
Основних кроки програми:
- Користувач вводить кількість множин (`a`) та кількість стовпців (`b`).
- Користувач вводить дані у вигляді матриці, де кожний рядок представляє множину.
- Матриця `arr` заповнюється з введених даних, де `1` позначає наявність елемента в множині, а `0` його відсутність.
- Обчислюється найефективніше покриття. Для цього перебираються всі множини, обчислюється кількість елементів у кожній множині, та вибирається та, де ця кількість максимальна.
- Після знаходження найефективнішого покриття програма обчислює його ціну, тобто суму значень останнього стовпця вибраної множини.
Програма використовує масив `B`, щоб відстежувати, які елементи вже включені в покриття. Коли всі елементи покриття вже вибрано, вона завершує свою роботу та виводить результат.
Результати тестування програми
[pic 8]
Висновок: в ході виконання лабораторної роботи практично побудовані покриття на множинах методом мінімального стовпчика - максимального рядка та методом ядерних рядків. Для кожного з них були розроблені відповідні схеми алгоритмів. Для методу мінімального стовпчика - максимального рядка була створена програма на мові C++, яка здійснює побудову покриттів. Після виконання програми було отримано покриття CE з ціною 6.
...