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

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

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

 
Размер на шрифта
Increase Font Size Option 3 Reset Font Size Option 3 Decrease Font Size Option 3
Bulgarian Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish
Търсене в сайта: