Сечение на две крайни множества - общи елементи
Нека имаме две непразни крайни множества А и В.
Трето множество C = A ∩ B е сечение на множества А и В, ако съдържа само елементите,
които са общи за двете множества.
Пример: А {1,2,5,7,9}; B{2,4,6,8}, то C{2}
сечение на две крайни множества може да бъде илюстрирано с булева функция AND -
в крайното множество влизат само елементи, които присъстват ednowremenno и в двете множества.
Някои характерни свойства за
сечение на множество:
сечение на множество А със себе си е същото множество - има еднн и същи общи елементи;
сечението на множество А с празното множество е празното множество - липсват общи елементи;
сечение на множество А с универсалното множество U е същото множество А - множеството A е подмножество на универсалното множество U;
сечение на множество А с множество В е равно на сечението на множеството В с множеството А - и в двата случая има едни и същи общи елементи.
Операцията сечение на множества е комутативна.
Алгоритъм:
Като структура за съхраняване стойността на елементите за всяко отделно множество ще използваме едномерен масив.
В самото начало стойността на всички елементи за всеки отделен масив се инициализира, т.е. всички елементи са 0 - void inici.
Стартира се генератор на случайни числа - за генериране стойност на елементи за всяко отделно множество.
При генериране на различнте числа няма гаранция, че всички елементи за дадено множество ще са различни, затова вмвсто поредна стойност се увеличава с 1 стойността на клетка от масива с индекс генерираното число.
Тази операция се повтаря за всяко множество поотделно.
Самата операция сечение се осъществява чрез логическа функция AND - ако във всяко от дете множества има еднакъв елемент, то в множството сечение се записва този елемент.
Така неявно се ползва наредба за всяко от началните две множества, участващи в операцията сечение.
Следващата примерна програма дава решена задача за сечение на две множества
#include <iostream>
#include <stdlib.h>
using namespace std;
int const Max=25;//maksimalen diapazon na generiranite chisla i tehniq broj
void inici(int mas0[], int mas1[], int mas2[])
{ int i;
for (i=0;i<Max;i++)
{mas0[i]=mas1[i]=mas2[i]=0;}
//sega wseski elemnt w masiwite/mnovestwata ima stojnost 0
} iztriwa stojnosti na elementi w mnovestwo
void gener(int mas3[], int br)
{ int i=0,c;
do {
c=1+rand()%Max;//generira sluchajno chislo ot interwala [1..Max] element w mnovestwo
//ako ne e bila wywevdana do momenta takawa stojnost
if (!mas3[c]) {mas3[c]++;i++;cout<<c<<"; ";};
//realno w masiwa se zapiswa 1 w kletka s indeks generiranoto chislo
} while(i<br);
cout<<endl;
}// element w mnovestwo
int mnoves(int mas0[], int mas1[], int mas2[])
{int i, kolko=0;
for (i=0;i<Max;i++)
{ if (mas1[i] && mas2[i]) {kolko++;cout<<i<<"; ";mas0[i]++;};
// sechenie ednakyw element prisystwa ednowremenno w dwete mnovestwa
} //w masiwa / mnovstwo mas0 se wywevdat samo onezi stojnosti, koito sa walidni za obrabotkata
return kolko;
}// sechenie na mnovestwo
void obrabotka(int mas0[], int mas1[], int mas2[], int br)
{ int koe,kolko;
inici(mas0, mas1, mas2);
cout<<"Generiram "<<br<<" broq razlichni sluchajni chisla za mnovestwo A:\n";
gener(mas1, br);
cout<<"Generiram "<<br-1<<" broq razlichni sluchajni chisla za mnovestwo B:\n";
gener(mas2, br-1);
cout<<"Pri operaciq sechenie na 2 mnovestwa elementite sa:\n";
kolko=mnoves(mas0, mas1, mas2); cout<<" Obsho:"<<kolko<<" elementa\n";
}// element w mnovestwo
int main()
{ int mas0[Max],mas1[Max],mas2[Max],br;
char ose;
cout<<"Da se systawi programa, chrez koqto se wywevdat razlichni \n";
cout<<"estestweni chisla ot interwala [1..25] w dwe otdelni mnovestwa.\n";
cout<<"Chislata w dwete mnovestwa se generirat kato sluchajni.\n";
cout<<"Programata da izwede generiranite chisla wyw wsqko ot mnovestwata,\n";
cout<<"i movestewoto, predstwlqwasho tqhnoto sechenie.\n";
do {
cout<<"Wywedete broi elementi w mnovestwo A [10..15]: ";cin >> br;
//ne e slovena zashita po whod
obrabotka(mas0, mas1, mas2, br);
cout<<"She wywevdate li drugi danni <y/n>: ";cin>>ose;
} while (ose=='y');
system("pause");//ochakwa natiskane na klawish
return 0;//oswobovdawa zaetite resursi i wrysha kod za greshka 0
}//kraj na programa sechenie na mnovestwo
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.