68998

Організація множин, операції над множинами

Лекция

Информатика, кибернетика и программирование

Множина - це невпорядкований набір різних об’єктів однакового типу. У мові Паскаль використовують тільки скінченні множини, причому всі елементи множини повинні бути однакового типу, визначеного в Паскалі. Тип елементів множини називається базовим.

Украинкский

2014-09-28

34.5 KB

1 чел.

Лекція № 8

Тема: Організація множин, операції над множинами

План заняття:

  1.  Організація множин
  2.  Операції над множинами

Організація множин

Множина - це невпорядкований набір різних об'єктів однакового типу. У мові Паскаль використовують тільки скінченні множини, причому всі елементи множини повинні бути однакового типу, визначеного в Паскалі. Тип елементів множини називається базовим. Як базовий може бути довільний ординальний тип (тобто будь-який простий, за винятком real). Цілого типу застосовують тільки діапазон, для якого зазначають мінімальне і максимальне значення.

Змінні чи сталі множинного типу набувають значення, які є множиною. Для задання множини використовують так званий конструктор множини, який має вигляд списку елементів множини, взятого в квадратні дужки. Елементами множини можуть бути сталі базового типу або вирази цього ж типу. Множина може не мати елементів, тоді вона є порожньою і її описує конструкція [].

Приклади задання множин: [4, 6, 9,12] - множина, елементами якої є цілі числа; ['i', 'm', 'p', 'q', 'r'] - множина, елементами якої є символи; [m, 10] - множина, що містить значення змінної цілого типу т і цілого числа 10.

Якщо елементи множини утворюють діапазон значень базового типу, то їх можна задавати скорочено, як і елементи діапазонного типу. Наприклад, множину [3, 4, 5, 6, 7] можна записати [3..7]. Частину елементів можна перелічувати, а частину - задавати як діапазон: [3, 4, 5..100].

[n..2*n] — множина цілих чисел від п до виразу 2п.

[пн, вт, чт] - множина елементів деякого перелічуваного типу, який потрібно описати.

Якщо в діапазоні А..С, яким задана множина, А=С, то ця множина містить один елемент, що дорівнює А. Якщо С<А, то множина порожня. Наприклад: [3..1], ['r'..'b'] - порожні множини.

Якщо якийсь елемент повторюється, то вважають, що є тільки один такий елемент. Наприклад: [2, 3, 7, 2, 3] те ж саме, що [2, 3, 7].

З наведених прикладів зрозуміло, що для задання множинного типу треба задати деякий базовий тип. Відповідний множинний тип (змінна) може набувати значень, що є множинами, одержаними довільними комбінаціями базового типу.

Загальний вигляд опису множинного типу такий:

type

<ім'я_типу>=set  of  <ординальний_тип>;

Опишемо тип

type

р=1..3;

b=set  of  p;

var

x:b;

Тоді х може набувати значень, якими є всі множини, що можуть бути складені з цілих чисел 1, 2 і 3. Змінна х може мати такі значення: [ ] - порожня множина, [1], [2], [3], [1,2], [1,3], [2,3] і [1,2,3]. Усі ці множини можуть бути значеннями змінної х множинного типу, заданого як set of p. Інші приклади:

type

day=(pn, vt, sr, ct, pt, sb, nd);

den=set of day;

var

roboch: den;

sezon: set of (lito, osin, zyma, vesna);

logic: set of boolean;

У цьому прикладі тип den описаний явно, як множинний, що має базовим перелічуваний тип day. Решта типів задано неявно в описі змінних sezon і logic. Змінна roboch може набувати значень [], [pn], [vt],..., [pn, vt], [pn, sr],..., [sb, nd], [pn, vt, sr],..., [pn, vt, sr, ct, pt, sb, nd].

Змінна sezon: [ ], [lito],..., [lito, osin, zyma, vesna].

Змінна logic: [ ], [true], [false], [true, false].

Для присвоєння значень змінним множинного типу використовують оператор присвоєння

v:=s,

де v - змінна множинного типу; s - вираз цього типу. Елементи s належать до того ж базового типу. Як вираз s може бути змінна множинного типу або саме значення - стала множинного типу. Наприклад, для описаних вище змінних правильними є оператори присвоєння

roboch:=[vt, ct, pt]; logic:=[true];

Тут як вирази використані сталі.

Операції над множинами

Операції над множинами в мові Паскаль практично збігаються з операціями в теорії множин. Це передусім операції об'єднання, перерізу і різниці множин. Нехай А і В - вирази однакового множинного типу, тобто це множини, елементи яких належать до одного і того ж базового типу. Тоді:

об'єднанням А +В множин А і В є множина, елементи якої належать хоча б до однієї множини А чи В. Наприклад, А = [1, 3, 6, 7], а В - [2, 4, 6, 7], то А+В дорівнює [1, 2, 3, 4, 6, 7];

перерізом А *В множин А і В є множина, елементи якої одночасно належать до множини А і множини В. Для тих же А і В переріз А *В  буде [6, 7];

різницею А-В множин А і В є множина, що складається з елементів множини А, які не належать до множини В. Якщо як множини А і В взяти використані раніше, то А-В дає множину [1,3].

За допомогою операцій з множинами можна будувати вирази множинного типу. Пріоритетність виконання операцій така сама, як і під час обчислення арифметичних виразів: у дужках, '*', '+'  і '-'.


 

А также другие работы, которые могут Вас заинтересовать

83486. Громадянство і підданство 33.42 KB
  У доктрині міжнародного права і національного законодавства деяких держав замість терміна громадянство використовується термін підданство причому в якості цілком рівнозначних. Підданство відрізняється від громадянства насамперед тим що воно: поперше є інститутом монархічної держави і означає політикоправовий зв\'язок підданого з монархом; подруге такий правовий зв\'язок характеризується не взаємним і рівнообов\'язковим як при громадянстві а одностороннім характером: підданий виконує перед монархом тільки обов\'язки а монарх щодо...
83487. Придбання і втрата громадянства 37.17 KB
  Виділяють наступні способи набуття громадянства: філіація; натуралізація укорінення; поновлення в громадянстві реінтеграція; дарування громадянства; оптація; трансферт. Філіація або набуття громадянства за народженням базується на двох принципах: права крові jus snguinis та права ґрунту jus soli. Різновидом натуралізації є спрощений порядок набуття громадянства певними категоріями осіб.
83488. Режим іноземців. Особи без громадянства 35.93 KB
  До іноземців окрім іноземних громадян також відносять осіб без громадянства. Режим правове положення іноземців визначають як сукупність прав та обов’язків іноземців на території даної держави. Режим іноземців встановлюється внутрішнім законодавством держав з врахуванням їх міжнародних зобов’язань.
83489. Біженці, вимушені переселенці. Право притулку 39.38 KB
  В якості біженців не розглядаються особи що винні у скоєнні: злочину проти миру воєнного злочину або злочину проти людяності; важкого злочину аполітичного характеру поза країною що надала притулок; дій що суперечать цілям та принципам ООН. Право притулку – право кожної людини шукати притулок від переслідування в інших державах та користатися цим притулком а також право держави дозволяти в’їзд та проживання на її території особі яка переслідується в іншій державі за політичними мотивами. Територіальний притулок означає що держави...
83490. Покоління прав людини 37.26 KB
  До першого покоління відносяться лише громадянські і політичні права. Тому права першого покоління іменуються негативними оскільки їх реалізація передбачає невтручання держави Початок формування другого покоління прав людини здебільшого пов’язують із прийняттям Веймарської конституції 1919 р. Друге покоління складають соціальні економічні та культурні права. Це покоління позитивних прав оскільки їх реалізація потребує втручання з боку держави та зі лежить від рівня економічного розвитку держави.
83491. Класифікація прав і свобод людини 34.69 KB
  До громадських відносяться наприклад право на життя і особисту недоторканністьправо дотримуватися своєї думки і вільно її висловлювати свобода пересування. До політичних прав перш за все відноситься право брати участь у веденні державних справ обирати і бути обраним на основі загального і рівного виборчого права. Зокрема виділяють: право на працю включаючи право на справедливі і сприятливі умови праці; право на створення профспілок і на проведення страйків; право на соціальне забезпечення право сімї на охорону і допомогу право на...
83492. Принцип поваги прав людини 36.62 KB
  Основу міжнародноправового захисту прав людини складає принцип поваги прав людини і основних свобод. Принцип поваги прав людини і основних свобод отримав визнання з ухваленням Статуту ООН у 1945 р. Генеральна Асамблея ООН прийняла Загальну декларацію прав людини у якій сформульовані основні права людини.
83493. Поняття міжнародно-правових стандартів у сфері прав людини 34.38 KB
  Міжнародноправові стандарти прав людини це узгоджені державами загальнолюдські права і свободи обов\'язкові для держав заходи із забезпечення прав і свобод та охорони їх від посягань а також надання особі юридичної можливості реалізовувати і захищати визнані права і свободи. Можна позначити наступні функції стандартів: визначення переліку прав і свобод що відносяться до категорії основних і обов\'язкових для всіх держав; формулювання головних рис змісту кожного з цих прав кожної з цих свобод які повинні бути втілені у відповідних...
83494. Основні міжнародно-правові акти про права людини 38.45 KB
  Зокрема до таких договорів відносяться: Міжнародна конвенція про ліквідацію всіх форм расової дискримінації 1966 р.; Конвенція про запобігання злочину геноциду та покарання за нього 1948 р.; Конвенція про припинення злочину апартеїду та покарання за нього 1973 р.; Конвенція про рабство 1926 р.