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

сечение на множества
сечение на множества - два взаимно пресичащи се правоъгълника
елементи в множество

Нека имаме две непразни крайни множества А и В. Трето множество 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");
return 0;
}//kraj na programa sechenie na mnovestwo

Начало на страницата

сечение на множества - два взаимно пресичащи се правоъгълника

Нека имаме две множества A и B. Дефиниционната област на двете множества се представя графично като правоъгълник. Имаме два правоъгълника с въведени съответни начална N1,N2 и крайна точка M1,M2 на диагонал, така че двата правоъгълника се пресичат взаимно. Въведени са K броя точки с техните координати. Трябва да се изведат всички точки принадлежащи едновременно и на двата правоъгълника.

Алгоритъм:
Ще означим долен ляв край на диагонала от първия правоъгълник с N1(x,y), горния десен край с M1(x,y). Аналогично за втория правоъгълник с N2(x,y) и M2(x,y).
Тук ще разгледаме само едно от възможните взаимни положения на двата правоъгълника.
Осъществява се проверка за коректно въведени данни:
N1x < N2x < M1x < M2x, както и N1y < N2y < M1y < M2y
Точка ще принадлежи на сечението на двете можества, ако е изпълнено съставното условие:
Tx >= N2x && Tx <= M1x && Ty >= N2y && Tx <= M1y

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

Начало на страницата

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

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

Спонсори

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

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

сечение на множества

сечение на множества - два взаимно пресичащи се правоъгълника