Обединение на крайни множества - различни елементи без повторение
Нека имаме две непразни крайни множества A, B.
Трето множество е обединение на множества А и В,
ако неговите елементи са всички различни елементи на първите две множества, но без повторение.
Така елементите на тяхното обединение са само различни елементи без повторение включващи:
а) елементи на множество А;
б) елементи на множество В;
в) елементи и на двете множества едновременно, но без повторение.
При обединение на две и повече множества често се използва логическа функция OR (ИЛИ).
Операцията обединение на множества е комутативна.
Алгоритъм:
Използват се два отделни масива за съхраняване стойности на цели числа - елементи за всяко едно множество.
Самите числа се генерират като псевдослучайни и няма гаранция, че всички елементи на дадено множество са различни.
За да се избегне усложнената проверка в масива - множество не се записва самото число, а в клетка с индекс генерираното число се увеличава с 1.
Така след края на цикъла във всяко отделно множество можем да имаме различен брой неповтарящи се елементи.
При самото обединение се следи (чрез логическа функция OR) кои от елементите на всеки от двата масива са със стойност по-голяма от 0.
В третия масив - обединение на двете множества се записват еднократно само индексите на клетки със стойност 1 или по-голяма.
Следващата примерна програма дава решена задача за обединение на две множества:
#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 elementi ot mnovestwa
void gener(int mas3[], int br)
{ int i=0,c;
do {
c=1+rand()%Max;//generira sluchajno chislo ot interwala [1..Max] element na 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 element na mnovestwo
} while(i<br);
cout<<endl;
}// elementi 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]++;};
//obedinenie elementite prisystwashi pone w ednoto mnovestwo
} //w masiwa mas0 se wywevdat samo onezi stojnosti, koito sa walidni za obrabotkata
cout<<endl;
return kolko;//broj elementi w obedinenie na mnovestwa
}// obedinenie na mnovestwa
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 obedinenie elementite sa:\n";
kolko=mnoves(mas0, mas1, mas2);
cout<<" Obsho:"<<kolko<<" elementa\n";
}//void obrabotka 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 obedinenie.\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 mnovestwo obedinenie
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.
Начало на страницата
