Алгебра

Сечение на две крайни множества - общи елементи

Нека имаме две непразни крайни множества А и В. Трето множество 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

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

Размер на шрифта

Търсене в сайта:

Полезни връзки

Изпълними приложения за

Сечение на две крайни множества - общи елементи