Розробка алгоритму та програми для розв’язання задачі про покриття на множинах методом повного та граничного перебору

Міністерство освіти та науки України

Вінницький національний технічний університет

Факультет інформаційних технологій та комп’ютерної інженерії

Кафедра КН

Дискретна математика

Лабораторна робота №1

Розробка алгоритму та програми для розв’язання задачі про покриття на множинах методом повного та граничного перебору

Виконав студент групи 2КН-17б

Канаєв Є. Ю.

Перевірила:

ас. Ваховська Л. М.

[pic 1]

Вінниця-2018

Тема: Розробка алгоритму та програми для розв’язання задачі про покриття на множинах методом повного та граничного перебору.

Мета: Набути навиків застосування методу повного перебору та методу граничного перебору для знаходження найкоротшого і мінімального покриттів.

1.Завдання для виконання(20 варіант).

2.Схема алгоритму.

[pic 2]

[pic 3]

3.Опис програми.

Середовище розробки – NetBeans.

Мова програмування – C++.

Для запуску потрібно натиснути F5. Далі  та на екрані буде виведено всі можливі множини, зі знаком “+” і ціною, якщо існує покриття, “-” – якщо покриття відсутнє.

Також буде виведено найдешевше покриття.

4.Результати тестування програми.

- метод повного перебору:

AB-

AC-

AD-

AE-

AF-

AG-

BC-

BD-

BE-

BF-

BG-

CD-

CE-

CF-

CG-

DE-

DF-

DG+6

EF-

EG-

FG-

ABC-

ABD-

ABE-

ABF-

ABG-

ACD-

ACE-

ACF-

ACG-

ADE-

ADF-

ADG+7

AEF-

AEG-

AFG-

BCD-

BCE-

BCF-

BCG-

BDE-

BDF-

BDG+8

BEF-

BEG-

BFG-

CDE-

CDF-

CDG+8

CEF-

CEG-

CFG-

DEF-

DEG+7

DFG+7

EFG-

ABCD+8

ABCE-

ABCF+6

ABCG-

ABDE-

ABDF-

ABDG+9

ABEF+6

ABEG-

ABFG+7

ACDE-

ACDF+7

ACDG+9

ACEF+6

ACEG-

ACFG-

ADEF+6

ADEG+8

ADFG+8

AEFG-

BCDE+8

BCDF-

BCDG+10

BCEF-

BCEG-

BCFG-

BDEF+7

BDEG+9

BDFG+9

BEFG-

CDEF-

CDEG+9

CDFG+9

CEFG-

DEFG+8