Елементи в множество, Декартово произведение
елементи в множество
Декартово произведение на множества
допълнение на множество
обединение на множества
разлика на множества
сечение на множества
задачи с множества
диаметър на множество
множество - представяне, видове
Понятията „множество“, „елемент на множество“ и „принадлежност към множество“ понякога се приемат за първични, интуитивно ясни и не се дефинират. Ще перифразираме определението на Г.Кантор - "множество това са много елементи възприемани като едно цяло". Това в пълния смисъл на думата не е логическо определение за понятието множество, а само пояснение, т.к. да се даде определение за нещо означава да се ползват предварително дефинирани понятия - рекурсивна дефиниция.В математиката с множеството се представя съвкупност от обекти, наричани още елементи, които имат еднакви, определящи множеството качества. Множествата се отбелязват с главни букви от латинската азбука, а принадлежащите им елементи с малки букви. Начинът на подреждане (наредбата) на елементите както и броят на срещанията на определен елемент са без особено значение, т.е. с „{а, 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));. В противен случай ще се започва с едни и същи числа.
Условието на задачата налага проверка дали новото случайно число не е вече записано като елемент на множеството.
Следващата примерна програма илюстрира решение на задача за въвеждане на различни по стойност елементи в множество:
Начало на страницата за множество
Декартово произведение на множества
Произведение на две множества се нарича Декартово произведение на името на френския математик Рене Декарт. Нека са дадени две множества с техните елементи: множество A {Габрово, Севлиево, Дряново, Трявна} и множество B{Ловеч, Троян} Тогава тяхното Декартово произведение ще включва следните множества:{Габрово, Ловеч}, {Габрово, Троян},{Севлиево, Ловеч}, {Севлиево, Троян}, {Дряново, Ловеч}, {Дряново, Троян},{Трявна, Ловеч}, {Трявна, Троян}
Да разгледаме следната задача:
Дадени са два списъка с имена, съдържащи елементи на две отделни множества. Няма повтарящи се елементи в кое да е от тези множества. Трябва да се изведе съответното Декартово произведение на тези множества.
Описаният алгоритъм включва: въвеждане на брой и стойност за елементи в двете множества, както и формирането на тяхното Декартово произведение. Елементите на всяко множество се съхраняват в отделен масив. В решението на тази задача е използван вложен цикъл за получаване на всички възможни подмножества с по два елемента. Броят елементи във всяко от двете множества не е непременно равен - ще ги означим съответно с m, n. Броят елементи в създаденото Декартово произведение на двете множества е m*n.
Следващата примерна програма дава решение на задача за Декартово произведение на две множества:
Начало на страницата за множество
задачи с множества
Да разгледаме следната примерна задача: Випуск в едно училище има 120 ученика, от които 60 са активни спортисти, 50 харесват точните науки и с лекота си решават задачите, 13 са едновременно спортисти и математици. Колко от учениците не се занимават нито със спорт, нито с точни науки?Имаме множество с U елемента, включващо две множества A, B, както и тяхното сечение AnB. Търсим допълнението към това множество.
Алгоритъмът включва следните стъпки:
Сечението на двете множества AnB включва едновременно елементи и от двете множества. За да получим броя елементи в двете множества трябва от обединението на множествата AuB да извадим тяхното сечение: A + B - AnB.
Следващата стъпка на алгоритъма е да се намери разликата между броя елементи на множеството U и намерения общ брой елемент на множества A и B.
Търсеното допълнение D = U - (A + B - AnB)
Следващата примерна програма дава решение на задача за действия с множества:
Начало на страницата за множество
диаметър на множество
Под диаметър на множество ще разбираме най-голямото разстояние между два негови елемента. Нека разгледаме следната примерна задача: В дадено множество са въведени като негови елементи N броя цели числа. Не съществува наредба, т.е.в общия случай въведената редица не е монотонна. Търсим диаметър на това множество с рекурсивна функция.
Алгоритъм: Трябва да се намерят двата елемента имащи минимална и максимална стойност.Тук се обединяват двата сходни алгоритъма:
търсене на елемент с минимална стойност;
търсене на елемент с максимална стойност.
Като структура за въвеждане всички елементи на това множество ще използваме масив.
Да припомним в началото първият елемент от масива се обявява едновременно за минимална и максимална стойност.
Последователно се обхожда целия масив и се извършва проверка с поредния номер елемент.
Извежда се разликата между намерените две стойности на елементи.
Ще използваме указател псевдоним за двете търсени стойности.
Следващата примерна програма дава решена задача за диаметър на множество с рекурсивна функция:
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.