Елементи в множество, Декартово произведение

елементи в множество
Декартово произведение на множества
допълнение на множество
обединение на множества
разлика на множества
сечение на множества
задачи с множества
диаметър на множество

множество - представяне, видове

  Понятията „множество“, „елемент на множество“ и „принадлежност към множество“ понякога се приемат за първични, интуитивно ясни и не се дефинират. Ще перифразираме определението на Г.Кантор - "множество това са много елементи възприемани като едно цяло". Това в пълния смисъл на думата не е логическо определение за понятието множество, а само пояснение, т.к. да се даде определение за нещо означава да се ползват предварително дефинирани понятия - рекурсивна дефиниция.
  В математиката с множеството се представя съвкупност от обекти, наричани още елементи, които имат еднакви, определящи множеството качества. Множествата се отбелязват с главни букви от латинската азбука, а принадлежащите им елементи с малки букви. Начинът на подреждане (наредбата) на елементите както и броят на срещанията на определен елемент са без особено значение, т.е. с „{а, b, c }“, „{b, c, a}“ и „{a, a, c, c, c, b, b}“ се означава едно и също множество, чиито елементи са a, b и с.
  Така с означенията „{а, b}“, „{b, a}“ и „{a, b, b}“ се представя едно и също множество, чиито елементи са a и b. С теоретично значение се въвежда понятието празно множество, което представлява множество без елементи. Всяко множество съдържа поне едно подмножество, което е празното множество. Празното множество се съдържа във всяко множество, а универсалното множество, съдържа в себе си всички подмножества от дадения тип елементи.
  Едно множество се описва по два начина - с изброяване на неговите елементи или със задаване на условие, което те удовлетворяват.
  Две множества са равни тогава и само тогава, когато всеки елемент на едното е елемент и на другото или и двете са празни.
  Едно множество се нарича крайно, ако то съдържа n на брой елемента, където n е естествено число (може да бъде и 0). В противен случай, множеството се нарича безкрайно. Пример: за безкрайно множество са естествените числа, реалните числа и др.п. Едно безкрайно множество се нарича изброимо, когато е равномощно на множеството на естествените числа.

Начало на страницата за множество

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

В едно множество се съдържат само различни по стойност елементи. В множеството не е задължително да съществува наредба.

Да разгледаме следната задача: Трябва да се въведат N броя различни естествени числа принадлежащи на даден числов интервал.
Ще се използват библиотечните функция srand и rand за генериране на случайни цели числа - тип int. Използва се библиотека stdlib.h. Обърнете внимание на изискването за начална инициализация rand((unsigned) time(&t));. В противен случай ще се започва с едни и същи числа.
Условието на задачата налага проверка дали новото случайно число не е вече записано като елемент на множеството.
Следващата примерна програма илюстрира решение на задача за въвеждане на различни по стойност елементи в множество:
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
int const broi=255, kolko=20;

 int mnov(int Min, int Max, int mas[])
  {int chis,k,j,i=0;
  if ((Max-Min)<2*kolko)  {cout<<"Wywedete nowi granici za interwala.\n";}
  else
  { do //dokato ne se generirat tyrseniq broj razlichni chisla - elementi w mnovestwo
     {chis=Min+rand () %(Max-Min);//sluchajno chislo ot interwala [Min..Max]
     k=0;
      for (j=0;j<i;j++)  //prowerqwa ilma li weche takowa chislo
      {if (mas[j]==chis) k++; //weche ima takowa chislo
      }//for              
    if (!k) {mas[i]=chis;i++;} //zapis na nowoto chislo           
   }while (i<kolko);        
  } //prowerkata za granici i broj chisla
  return i;//po podrazbirane i=0
 }//int mnov elementi w mnovestwo

int main()
 { int i,n,k,Min,Max,d,mas[broi] ;
   time_t t;
   cout<<"Da se systawi programa, chrez koqto se wywevdat N broq razlichni\n";
   cout<<"sluchajni estestweni chisla prinadlevashi na daden chislow interwal.\n";
   cout<<"Wywedete dolna granica za interwala [10..255]: ";cin>>n;
   cout<<"Wywedete gorna granica za interwala [1000..2550]: ";cin>>k;
   srand((unsigned) time(&t));//inicializira generator na suchajni chisla    
    //sledwa proweka dali ne sa obyrnati granicite za chislowiq interwal
   Min=(k+n - abs(k-n))/2;
   Max=(k+n + abs(k-n))/2;
   cout<<"She generiram "<<kolko<<" sluchajni chisla ot interwala ["<<Min<<".."<<Max<<"]:\n";
   d= mnov(Min, Max, mas);//funkciqta she generira sluchajni chisla ot interwala
   if (d)//ako wywedenite granici na interwala sa dostatychni za generirane na razlichni chisla
  {cout<<"Mnovestwoto sydyrva slednite "<<kolko<<" razlichni chisla ot interwala ["<<Min<<".."<<Max<<"]:\n";
    for(i=0; i<kolko; i++) cout<<mas[i]<<"; ";
    cout<<endl;
    }//if (d)
  system("pause");
 return 0; 
} //kraj na programa elementi w mnovestwo

Начало на страницата за множество

Декартово произведение на множества

Произведение на две множества се нарича Декартово произведение на името на френския математик Рене Декарт. Нека са дадени две множества с техните елементи: множество A {Габрово, Севлиево, Дряново, Трявна} и множество B{Ловеч, Троян} Тогава тяхното Декартово произведение ще включва следните множества:
{Габрово, Ловеч}, {Габрово, Троян},{Севлиево, Ловеч}, {Севлиево, Троян}, {Дряново, Ловеч}, {Дряново, Троян},{Трявна, Ловеч}, {Трявна, Троян}
Да разгледаме следната задача:
Дадени са два списъка с имена, съдържащи елементи на две отделни множества. Няма повтарящи се елементи в кое да е от тези множества. Трябва да се изведе съответното Декартово произведение на тези множества.
Описаният алгоритъм включва: въвеждане на брой и стойност за елементи в двете множества, както и формирането на тяхното Декартово произведение. Елементите на всяко множество се съхраняват в отделен масив. В решението на тази задача е използван вложен цикъл за получаване на всички възможни подмножества с по два елемента. Броят елементи във всяко от двете множества не е непременно равен - ще ги означим съответно с m, n. Броят елементи в създаденото Декартово произведение на двете множества е m*n.
Следващата примерна програма дава решение на задача за Декартово произведение на две множества:
#include<iostream>
using namespace std;
int const broi=20, dyl=25;

int broi_el (char mnov[][dyl], int koe)
{ int i,j;
 cout<<"Kolko elementa she ima mnovestwo "<<(char)(64+koe)<<": "; cin>>i;
 for(j=0;j<i;j++) {//gets(mnov[i]);
  cout<<"Wywedete duma za novestwo "<<(char)(64+koe)<<": ";
  cin>>mnov[j];
  }
   return i; 
} //broi_el elementi w mnovestwo

void pechat (  char mnov_A[][dyl], int br_A, char mnov_B[][dyl], int br_B)
{int i,j;
 cout<<"Dekartowoto proizwedenie na mnovestwo A["<<br_A<<"] s mnovestwo B["<<br_B<<"]\n";
 cout<<"formira slednite nowi mnovestwa: \n";
 for (i=0;i<br_A;i++)
 {  for (j=0;j<br_B;j++)
  cout<<mnov_A[i]<<" : "<<mnov_B[j]<<endl;
  }//for i   
}//Dekartowo proizwedenie  

 int main() //nachalo na programata
{ char mnov_A[broi][dyl],mnov_B[broi][dyl],ose;
   int br_A,br_B;
  //deklarira promenliwite. W C++ tipyt String se predstawq kato masiw ot Char
  cout<<"Imete dwe otdelni mnovestwa, wsqko ot koito sydyrva do 20 dumi. \n";
  cout<<"Wsqka duma e s dylvina do 25 znaka i sydyrva bukwi i ili cifri \n";
  cout<<"bez interwal. Trqbwa da se formira dekartowo proizwedenie\n";
  cout<<"mevdu elementite na dwete mnovestwa.\n";
  cout<<"Da se systawi programa, chrez koqto se wywevdat elementite  \n";
  cout<<"w mnovestwata i se izwevda tqhnoto dekartowo proizwedenie.\n";
  cout <<"Primer: A,B; 1,2,3 Izhod: A-1, A-2, A-3 B-1, B-2, B-3\n";
 do {
  br_A=broi_el (mnov_A, 1);
  br_B= broi_el (mnov_B, 2);
  pechat ( mnov_A, br_A, mnov_B, br_B);
  cout<<"She wywevdate li drugi danii <y/n>: ";cin>>ose;
  } while ( ose=='y');
  system("pause"); 
  return 0;
}//kraj na programa Dekartowo proizwedenie na dwe mnovestwa

Начало на страницата за множество

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

Да разгледаме следната примерна задача: Випуск в едно училище има 120 ученика, от които 60 са активни спортисти, 50 харесват точните науки и с лекота си решават задачите, 13 са едновременно спортисти и математици. Колко от учениците не се занимават нито със спорт, нито с точни науки?
Имаме множество с U елемента, включващо две множества A, B, както и тяхното сечение AnB. Търсим допълнението към това множество.
Алгоритъмът включва следните стъпки:
Сечението на двете множества AnB включва едновременно елементи и от двете множества. За да получим броя елементи в двете множества трябва от обединението на множествата AuB да извадим тяхното сечение: A + B - AnB.
Следващата стъпка на алгоритъма е да се намери разликата между броя елементи на множеството U и намерения общ брой елемент на множества A и B.
Търсеното допълнение D = U - (A + B - AnB)

Следващата примерна програма дава решение на задача за действия с множества:
#include <iostream>
using namespace std; 

int main ()
{int A,B,U,D,AnB;
char ose;
  cout<<"Imame wywedeni slednite stojnosti za A,B,U,AnB - estestweni chisla\n";
  cout<<"ot interwala [1..101]. U e obsh broj elementi w dadeno mnovestwo,\n";
  cout<<"A,B sa broj elementi na podmnovestwata na U - A i B, AnB e broj\n";
  cout<<"elementi w sechenieto na A i B. Tyrsim mnovestwo D - dopylnenie \n";
  cout<<"kym mnovestwo U. Systawete programa za izchislqwane na dopylnenieto.\n";
  cout<<"Primer: U=120; A=60, B=50, AnB=13 Izhod D=23.\n";
  do {
    cout<<"Wywedete stojnost za U: ";cin>>U;
    cout<<"Wywedete stojnost za A: ";cin>>A; 
    cout<<"Wywedete stojnost za B: ";cin>>B;
    cout<<"Wywedete stojnost za AnB: ";cin>>AnB;
    D=U-(A+B-AnB);
    cout<<"Broj elementi w dopylnenieto D: "<<D<<endl;
    cout<<"She wywevdate li drugi danni<y/n>: ";cin>>ose;
 } while (ose=='y');
system ("pause");
return 0;
}//kraj na programa elementi w mnovestwo

Начало на страницата за множество

диаметър на множество

Под диаметър на множество ще разбираме най-голямото разстояние между два негови елемента. Нека разгледаме следната примерна задача: В дадено множество са въведени като негови елементи N броя цели числа. Не съществува наредба, т.е.в общия случай въведената редица не е монотонна. Търсим диаметър на това множество с рекурсивна функция.

Алгоритъм: Трябва да се намерят двата елемента имащи минимална и максимална стойност.
Тук се обединяват двата сходни алгоритъма:
търсене на елемент с минимална стойност;
търсене на елемент с максимална стойност.
Като структура за въвеждане всички елементи на това множество ще използваме масив.
Да припомним в началото първият елемент от масива се обявява едновременно за минимална и максимална стойност.
Последователно се обхожда целия масив и се извършва проверка с поредния номер елемент.
Извежда се разликата между намерените две стойности на елементи.
Ще използваме указател псевдоним за двете търсени стойности.

Следващата примерна програма дава решена задача за диаметър на множество с рекурсивна функция:
#include <iostream>
using namespace std;

const int broi=9;//zadawa broj elementi w towa mnovestwo 
int mas[broi] =  {-3,21,37,-45,-71,81,-9,41,-42};

 void minimalen (int n, int &min_e, int &max_e)//rekursiwna funkciq
{if (n>0) 
{  cout<<"Nomer: "<<n<<endl;
    minimalen (n-1,min_e, max_e);
    if (min_e>mas[n]) min_e=mas[n];
    if (max_e<mas[n]) max_e=mas[n];
  cout<<"Obraten hod nomer: "<<n<<" : "<<min_e<<" : "<<max_e<<endl;
} 
else {min_e=max_e=mas[0];}//opredelq 1-wiq element za minimalna stojnost
}//element s minimalna i maksimalna stojnost 

int main () //nachalo na programata
{ int br, min_e,max_e;
cout<<"Imate predwaritelno wywedeni stojnosti w mnovestwo ot 9 chisla w\n";
cout<<"interwala [-99..99]. Da se systawi programa, koqto izpolzwa rekursiwna \n";
cout<<"funkciq i izwevda minimalniq i maksimalniq element ot masiwa.\n";
cout<<"Wywedenite stojnosti sa: "<<endl;
for (br=0;br<broi;br++) {cout<<mas[br]<<"; ";}
cout<<endl;
minimalen (broi-1,min_e,max_e);
cout<<"minimalen element w mnovestwo "<<min_e<<endl;
cout<<"maksimalen element w mnovestwo "<<max_e<<endl;
cout<<"maksimalna razlika: "<<max_e-min_e<<endl;
system("pause");
return 0;
}//kraj na programa diametyr 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
Търсене в сайта: