Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом граничного перебору
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Вінницький національний технічний університет
Інститут Інформаційних Технологій та Комп’ютерної Інженерії
Лабараторна робота № 2
з дисципліни: Дискретна математика.
Тема: Розробка алгоритму і програми для розв’язання задачі про покриття на множинах методом граничного перебору.
м.Вінниця 2012
Мета: набути навиків застосування методу методу граничного перебору для знаходження найкоротшого і мінімального покриття.
Порядок виконання роботи:
Ознайомитися з методом граничного перебору.
Отримати варіант індивідуального завдання для виконання.
Розробити схему алгоритму побудови покриття методом граничного перебору.
Розробити програму побудови покриття методом граничного перебору.
Для заданого варіанту принести результати тестування програми у покроковому режимі.
Зробити висновки про результати застосування цих методів для побудови покриття
Завдання для виконання №25
3.Блок-схема
Рисунок 1.
4. Приклади тестування програми
/
/
5. Висновок: Побудовано алгоритм, блок-схему програми, розроблено програму мовою C++ що реалізує побудову покриття методом граничного перебору для знаходження найкоротшого і мінімального покриття.
6.Додаток ( Лістинг програми що реалізує метод граничного перебору для знаходження найкоротшого і мінімального покриття)
#include <iostream>
#include <conio.h>
#include <stdio.h>
main(){
setlocale(LC_ALL,"Ukrainian");
int A[100][100],B[100]={0},C[100],K[100]={0},a,b,i,j,k,n,l,e,cina,cina1=20000,kil=0,kp=0,Q[100]={9},w=10,R[100]={9},k2,k1;
char ch[12]="АБВГДЕЖ ";
printf("ВВЕДIТЬ КIЛЬКIСТЬ МНОЖИН: \n");
scanf("%d",&a);
printf("ВВЕДIТЬ КIЛЬКIСТЬ СТОВПЦIВ:\n");
scanf("%d",&b);
printf(" ");
for(i=0;i<b;i++){
printf(" ");
printf("%d",i+1); }
printf(" цiна");
printf("\n");
for (i=0;i<a;i++){
printf("\n");
printf("%c",ch[i]);
for(j=0;j<=b;j++){printf(" ");
scanf("%d",&A[i][j]);
}
}
printf("\n");
for(e=0;e<a;e++){
cina=0;
k=1; l=0;for(i=0;i<b;i++){C[i]=0;B[i]=0;K[i]=0;}
for(j=e;j<a;j++){ C[l]=j;kil++;
n=0;
for(i=0;i<b;i++){
B[i]+=A[j][i]+K[i];
if(B[i]>0) n++;
} cina+=A[j][b];
if(n!=b) {n=0;
for(i=0;i<k;i++)printf("%c",ch[C[i]]);
printf(" - \n");
for(i=0;i<b;i++){K[i]=B[i];B[i]=0;}
k++;l++;
}
if(n==b) {n=0;kp++;if(k<w){for(i=0;i<k;i++)R[i]=C[i];w=k;k2=k;}
for(i=0;i<k;i++)printf("%c",ch[C[i]]);
if(cina<cina1) {cina1=cina;for(i=0;i<k;i++) Q[i]=C[i];k1=k;}
printf("+ цiна - %d\n",cina);cina=cina-A[j][b];
for(i=0;i<b;i++){B[i]=0;}
}
}if (C[j]==a) break;
}
printf("\n\n");
printf("Вiдповiдь:\n Кiлькiсть варiантiв - %d \n Кiльксть покриттiв - %d \n",kil,kp);
printf(" Найдешевше покриття - ");
for(i=0;i<k1;i++) printf("%c",ch[Q[i]]);
printf("\n");
printf(" Найкоротше покриття - ");
for(i=0;i<k2;i++) printf("%c",ch[R[i]]);
printf("\n");
getch();}
06.02.2014 01:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора