Міністерство освіти і науки України Вінницький національний технічний університет Кафедра КН Лабораторна робота №1 з дисципліни «Дискретна математика» Тема: «Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом повного та граничного переборів» Виконали: студенти групи 2КН – 15б Ваховський Віталій Ільченко Оксана Перевірила: Ваховська Л. М. Вінниця 2016 Мета роботи: набути навиків застосування методу повного перебору та методу граничного перебору для знаходження усіх можливих покриттів. Завдання: розробити алгоритм та програму для розв’язання задачі про покриття методом повного і граничного перебору. Продемонструвати роботу програми на прикладі. Варіант №28 1 2 3 4 5 6 7 8 9 a  А 1 1    1    1  Б  1 1 1 1     2  В      1 1 1  1  Г  1 1    1  1 3  Д 1  3 4      2  Е 1   1 1 1  1  3  Ж     1   1 1 1   Варіант №24 1 2 3 4 5 6 7 8 9 a  А   1   1   1 2  Б 1    1  1 1  2  В  1 1 1      1  Г 1   1 1    1 3  Д     1 1  1  2  Е 1 1     1  1 1  Ж  1 1   1 1 1  3   Схема алгоритму:
Рисунок 1 – Блок-схема програми повного перебору
Рисунок 2 – Блок-схема програми граничного перебору Результати роботи: Варіант №28 Рисунок 3 – Результат роботи програми повного перебору / Рисунок 4 – Результат роботи програми граничного перебору Варіант №24 Рисунок 5 – Результат роботи програми повного перебору / Рисунок 6 – Результат роботи програми граничного перебору Висновок Під час виконання лабораторної роботи було набуто практичні навички застосування методу повного перебору та методу граничного перебору для знаходження покриття на множинах. Було розроблено дві програми для знаходження покриття на множині: перша використовує метод повного перебору (результат: для варіанту №8 знайдено 52 покриття, для варіанту №10 – 49 покриттів), друга – метод граничного перебору (результат: для варіанту №8 знайдено 10 покриттів, для варіанту №10 – 8 покриттів). Додаток 1. Інструкція користувача Для запуску програми повного перебору необхідно запустити файл Lab1-1.exe, для запуску програми граничного перебору – Lab1-2.exe. Подальші дії однакові для обох програм. Розставити «одиниці» у відповідні комірки таблиці для вводу початкових даних та вказати «ціни» збірок у стовпчику «Ціна». Натиснути на кнопку «Почати» для виконання пошуку покриттів. Програма виведе покриття, їхню кількість, а також найдешевші та найкоротші покриття. Додаток 2. Лістинги програм Лістинг програми повного перебору: Лістинг програми граничного перебору: