Разлика на две крайни множества
Нека имаме две непразни крайни множества A и B.
След извършване на операцията разлика на множества, то множеството C = A \ B
ще съдържа само елементите на множество А, които не са елементи на множество В.
Операцията изваждане на множества или разлика на множества не е комутативна и не е асоциативна,
т.е. операцията разлика A \ B е различна от операцията разлика B \ A.
Да разгледаме следната задача с дадени две крайни множества А и В, представени със своите елементи.
Пример: А {1,2,5,7,9}; B{2,4,6,8}, то C{1,5,7,9}
Операцията разлика на две множества може да се илюстрира с логическата функция забрана по Y.
F(0,0) = 0; F(0,1) = 0; F(1,0) = 1; F(1,1) = 0;
0 > 0 = 0; 0 > 1 = 0; 1> 0 = 1; 1>1 = 0.
симетрична разлика
Нека имаме 2 крайни множества A и B. Ако |A \ B| = |B \ A| ще казваме, че разликата между двете множества е симетрична.
В този случай разглеждаме равенство на броя елементи в множеството C, а не тяхната стойност.
Пример: A = {1,3,5,7}; B = {3,4,5,6}
Броят на елементите в двете разлики са равни |A \ B| = |B \ A| , т.е. и в двата случая мощността на крайното множество е една и съща.
|A \ B| = {1,7}
|B \ A| = {4,6}
Следващата примерна програма дава решена задача за разлика между две множества:
#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
}//void inici(
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 element w mnovestwo
} while(i<br);
cout<<endl;
}//void elementi w mnovestwo
int mnoves(int mas0[], int mas1[], int mas2[], int koe)
{int i, kolko=0;
for (i=0;i<Max;i++) {mas0[i]=0;}//for i
//sega mnovestwo mas0 e prazno
for (i=0;i<Max;i++)
{ switch (koe)
{
case 1: if (mas1[i] > mas2[i])
{kolko++;cout<<i<<"; ";mas0[i]++;}; break;// razlika A-B
case 2: if (mas2[i] > mas1[i])
{kolko++;cout<<i<<"; ";mas0[i]++;}; break;// razlika B-A
}//shwitch - opredelq kakwa obrabotka se izwyrshwa w momenta razlika A-B ili B-A
} //for (i=0;i<br;i++)
//w masiwa mas0 se wywevdat samo onezi stojnosti, koito sa walidni za obrabotkata
return kolko;
}// void 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 razlika A-B elementite sa:\n";
kolko=mnoves(mas0, mas1, mas2, 1); cout<<" Obsho:"<<kolko<<" elementa\n";
cout<<"Pri operaciq razlika B-A elementite sa:\n";
kolko=mnoves(mas0, mas1, mas2, 2); 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 tqhnata razlika.\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 razlika
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.
