Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом повного перебору
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2014
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Вінницький національний технічний університет
ІнІТКІ
Кафедра комп’ютерних наук
Лабораторна робота № 1
З дисципліни Дискретна матиматика
Тема: : Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом повного перебору
Мета: набути навиків застосування методу повного перебору для знаходження найкоротшого і мінімального покриття
Хід роботи
Блок-схема програми, що обчислює всі можливі покриття за у мовами задачі про покриття представлена на Рисунку 1.
/
Рисунок 1 - Блок-схема програми, що обчислює всі можливі покриття за умовами задачі про покриття
Висновок
Виконавши дану лабораторну роботу, було набуто практичних навичок обчислення всіх можливих покриттів за у мовами задачі про покриття і реалізовано досліджуваний алгоритм обчислення на практиці у вигляді програми «DM_lab1»в програмному середовищі С++. Результати тестування програми підтвердили її працездатність.
Додатки.
Інструкції користувача:
Запустити програму, відкривши файл під назвою «DM_lab1.exe».
Вводимо таблицю покриттів по якій необхідно обчислити всі можливі покриття за умовою задачі про покриття та натиснути кнопку «Enter».
Вводимо таблицю цін та натиснути кнопку «Enter».
Буде здійснюватися обчислення всіх можливих покриттів за у мовами задачі про покриття.
Нижче відобразяться всі можливі покриття за у мовами задачі про покриття.
Нижче відобразяться номер мінімального покриття та номер найкоротшого покриття.
Лістинг програми:
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
void main()
{ int n,m;
n=7; m=9;
int A[100][100];
int B[100];
cout<<"Enter array A:\n";
for(int i = 0; i< n; i++)
{for(int j=0; j<m; j++)
{std::cin>>A[i][j];}}
cout<<"Enter array B:";
for(int j=0; j<n; j++)
{std::cin>>B[j];}
cout<<'\n';
int C[100];
int cina=0;
for(int i1=0; i1<n; i1++)
for(int i2=i1+1; i2<n; i2++)
for (int j=0; j<m; j++)
{ C[j]=A[i1][j] + A[i2][j];
}
if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0)
{ cina = B[i1]+ B[i2];
std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<"}="<<cina;
cina=0;
std::cout<<'\n';
for(int i1=0; i1<n; i1++)
for(int i2=i1+1; i2<n; i2++)
for(int i3=i2+1; i3<n; i3++)
for (int j=0; j<m; j++)
{ C[j]=A[i1][j] + A[i2][j]+ A[i3][j];
}
if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0)
{ cina = B[i1]+ B[i2]+ B[i3];
std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<","<<(i3+1)<<"}="<<cina;
cina=0;
std::cout<<'\n';
for(int i1=0; i1<n; i1++)
for(int i2=i1+1; i2<n; i2++)
for(int i3=i2+1; i3<n; i3++)
for(int i4=i3+1; i4<n; i4++)
for (int j=0; j<m; j++)
{ C[j]=A[i1][j] + A[i2][j]+ A[i3][j] + A[i4][j];
}
if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0)
{ cina = B[i1]+ B[i2]+ B[i3]+ B[i4];
std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<","<<(i3+1)<<","<<(i4+1)<<"}="<<cina;
cina=0;
std::cout<<'\n';
for(int i1=0; i1<n; i1++)
for(int i2=i1+1; i2<n; i2++)
for(int i3=i2+1; i3<n; i3++)
for(int i4=i3+1; i4<n; i4++)
for(int i5=i4+1; i5<n; i5++)
for (int j=0; j<m; j++)
{C[j]=A[i1][j] + A[i2][j]+ A[i3][j] + A[i4][j]+ A[i5][j];
}
if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0)
{ cina = B[i1]+ B[i2]+ B[i3]+B[i4]+ B[i5];
std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<","<<(i3+1)<<","<<(i4+1)<<","<<(i5+1)<<"}="<<cina;
cina=0;
std::cout<<'\n';
for(int i1=0; i1<n; i1++)
for(int i2=i1+1; i2<n; i2++)
for(int i3=i2+1; i3<n; i3++)
for(int i4=i3+1; i4<n; i4++)
for(int i5=i4+1; i5<n; i5++)
for(int i6=i5+1; i6<n; i6++)
for (int j=0; j<m; j++)
{ C[j]=A[i1][j] + A[i2][j]+ A[i3][j] + A[i4][j]+ A[i5][j]+A[i6][j];
}
if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0)
{ cina = B[i1]+ B[i2]+ B[i3]+B[i4]+ B[i5]+B[i6];
std::cout<<"{"<<(i1+1)<<","<<(i2+1)<<","<<(i3+1)<<","<<(i4+1)<<","<<(i5+1)<<","<<(i6+1)<<"}="<<cina;
cina=0;
std::cout<<'\n';
for (int j=0; j<m; j++)
{ C[j]=A[0][j] + A[1][j]+ A[2][j] + A[3][j]+ A[4][j]+A[5][j]+ A[6][j];
}
if(C[0]!=0 && C[1]!=0 && C[2]!=0 && C[3]!=0 && C[4]!=0 && C[5]!=0 && C[6]!=0 && C[7]!=0 && C[8]!=0)
{ cina = B[0]+ B[1]+ B[2]+B[3]+ B[4]+B[5]+ B[6];
std::cout<<"{1,2,3,4,5,6,7}="<<cina;
cina=0;
std::cout<<'\n';
}
std::cout<<'\n';
system("pause");}
Результати тестування:
//
13.02.2015 18:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора