69116

Множини. Поняття множин та множинного типу даних. Оголошення змінних множинного типу. Операції над множинами

Лекция

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

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

Украинкский

2014-09-30

96.5 KB

8 чел.

Лекція 25. Тема: Множини. Поняття множин та множинного типу даних.

                            Оголошення змінних множинного типу. Операції над множинами.

План:

1. Множини

2. Поняття множини та множинного типу даних

3. Оголошення змінних множинного типу

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

5. Зображення множим в оперативній пам'яті

1. Множини

Математичне поняття множини широко використовується в задачах, для яких існує ефективне програмне розв'язання. Так, у багатьох комбінаторних задач серед усіх підмножин деякої множини необхідно знайти ті, які задовольняють певну умову. При розв'язанні задач на графах користуються поняттями множин верши і ребер, а сам граф відображається на площині як множина точок і ліній. У мові Раsсаl означений відповідний тап даних, який буде розглянуто в цьому розділі.

2. Поняття множини та множинного типу даних

Множиною в мові Раsсаl називається скінченний набір однотипних даних. Об'єкти, з яких складається множина, називаються її елементами. Число, що дорівнює кількості елементів множини, називається її потужністю. Від масиву множина відрізняється відсутністю індексації її елементів, а від запису - тим, що елементи множини є однотипними і не позначаються ідентифікаторами.

Найпростішим прикладом множини є неіменована множина-константа, що у квадратних дужках як перелік однотипних елементів. Наприклад, [0.1]- це множина, що складається з двох цілочислових елементів, а['а'..'z']-множина, що містить усі маленькі літери латинського алфавіту — 26 символьних елементів. Максимально допустима потужність множини в мові Pascal становить 256, а мінімально допустима – 0. Множина нульової потужності, тобто множина, що не містить жодного елемента, називається породньою і в математиці позначається символом. У мові Pascal порожня множина позначається як порожній перелік, тобто символами [ ].

Зауважимо, що порядок елементів у переліку є несуттевим і кожний елемент входить до складу множини один раз. Тому, скажімо, множина [1,2,3,1,2,3] еквівалентна множині [1,2,3], а також множинам [1,2,3], [2,3,1], [2,1,3], [3,1,2], і [3,2,1]. Крім констант- множин у Pascal-програмах можна використовувати й змінні множинного типу даних, до розгляду якого ми й перейдемо.

Множинний тип – це структурований тип даних, допустими значеннями якого є деякі множини. Отже, сукупність допустимих значень такого типу даних – це є множина множин, яка не записується в оголошенні типу безпосередньо, але може бути визначена з його оголошення за певним правилом. Це правило легко зрозуміти, коли розглянути синтаксис оголошення множинного типу даних:

type <ім’я типу> = set of <базовий тип> ;

Як бачимо, оголошення множинного типу данних вимагає визначення для нього деякого базового типу. Базовим може бути-будь який перелічуванний тип, крім Integer та LongInt, а значенням множинного типу може стати довільний набір значень базового типу. Таким чином, допустимими значеннями множинного типу даних є всі можливі підмножини множини значень певного базового типу. Наведемо приклади. Припустимо, є таке оголошення множинного типу TypeA:

type TypeA= set of  2..4;

Тоді множина допустимих значень типу TypeA міститиме такі набори цілих чисел: {2,3,4}, {2,3}, {2,4}, {3,4}. {2}, {3},{4}.  Отже, із значень трьохелементного базового типу можна утворити вісім множин. Постає запитання:скільки різних множин можна утворити на основі n-елементного базового типу? З відомих математичних фактів випливає, що  таких множин може бути утворено 2n.

Щойно згадана величина n, яка дорівнює кількості елементів базового типу, не може перевищувати 256, оскільки потужність будь-якої множини в мові Pascal не може бути більшою за це число. Саме тому неприпустимо використовувати такі базові типи, як Integer та LongInt.

3. Оголошення змінних множинного типу

Оголошения змінної типу масиву або типу запису можє бути відокремланим від оголошення відповідного типу або поєднаним із ним. Таку саму ситуацію маємо і із змінною множинного типу даних: існує два різних синтаксиси її оголошення.

А саме:

var <ім’я зміної>: set of <базовий тип>;

та

var <ім’я зміної>:<ім’я множинного типу>;

При оголошенні множинної змінної першим способом неявно оголошується неіменований множинний тип даних, а другий спосіб потребує попереднього оголошення множинного типу в розділі type. Наведемо приклади оголошення костант і змінних множинного типу, означуючи самі типи явно, в розділі type, або неявно, в розділі var:

type

  Digits = set of 0..9;          {тип множини цифр}

  Letters = set of ‘A’..’Z’;   {тип множини латиниці}

  Day = (Sun, Mon, Tue, Wed, Thu, Fri, Sat); {тип множини днів}

  WorkDay = Mon..Fri;                 {тип діапазону}

const

     EvenDigits: Digits = [0, 2, 4, 6, 8];

     Vowels: Letters = [‘A’,’E’,’I’,’O’,’U’,’Y’];

     HexDigits: set of ‘0’..’z’ = [‘0’..’9’,’A’..’F’,’a’..’f’];

var

     symbol: set of char;     {множина символів}

     week: set of  Day;       {множина днів від Sun до Sat}

     WorkWeek: set of  WorkDay; {множина днів від Mon до Fri}

     number: set of byte;        {множина цілих однобайтових чисел}

     insert: set of 0..100;        {множина чисел від 0 до100}

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

У мові Раsсаl визначено аналоги майже всіх основних теоретико-множинних операцій та відношень. Базовим відношенням у теорії множин вважається відношення належності (елемент х належить множині А), що символічно позначається як хA (рис. 8.5, д). Перевірка істинності цього відношення у Раsсаl - програмі здійснюється оператором in. Використовуючи відношення належності, можна означити основні бінарні операції над множинами, якими вважаються операції об'єднання, перетину та різниці. Нагадаємо їх означення.

В результаті об’єднання множин утворюється множина, що складається з елементів, які належать хоча б одній з даних множин (рис. 8.5, а):

                                              AB={x| xA v xB}.

Результатом операції перетину множин є множина, що складається з елементів, які належать кожній з даних множин (рис. 8.5, б):

                                             AB = {x|x A & x B}.

Різниця множин А і В (доповнення А у В) - це операція, в результаті виконання якої утворюється множина, що складається з тих елементів множини А, які не належать множині В (рис. 8.5, в):

А\В={x|x AS & x  B}.

 Крім відношення належності елементів до множини в математиці використовують ще відношення множин, аналогами яких у мові Pascal є визначення для множинного типу данних операції порівння. Основні такі відношення визначають, чи збігаються множини та чи є одна з них підмножиною іншої. Нагадаємо, що множина А є підмножиною множини В (іншими словами, А міститься у В, або В містить А), якщо кожний елемент А є елементом В (рис 8.5, г): А В{xAxB}. Дві множини є рівними, кожна з них є підмножиною іншої: А = В

Зрозуміло, що результат операцій порівняння множин у мові Раsсаl, як і результат застосування оператора in, має логічний тип.

Як уже згадувалося, всі означені в мові Раsсаl операції над даними множинного типу мають відповідники у математиці. У табл. 8.1 перелічено всі такі операції та наведено їх запис як у математичній, так і у Раsса1-символіці.

Таблиця 8.1. Операції над множинами

Математичний запис      Запис на мові Раsсаl       Семантика

A = B                                   A = B                               Множини А і В збігаються

AB                                   A <> B                             Множини А і В не збігаються

AB                                   A >= B                             Множина В є підмножиною множини А

AB                                   A<=B                               Множина А є підмножиною множини В

xA                                     x in A                               Значення х належить множині А

AB                                   A + B                               Об’єднання множини А і В

AB                                   A * B                               Перетин множин А і В

A \ B                                     A – B                               Різниця множин А і В

Операнди наведених у табл. 8.1 операцій мають задовольняти певні обмеження. А саме, операнд х оператора х in А має належати базовому типу множнни А, а операнди решти операцій мають бути множинами з однаковим базовим типом.

Важливі окремі випадки операцій об'єднання та різниці множин реалізовано у вигляді бібліотечних процедур Include та Exclude, що здійснюють включення елемента до множини та вилучення його із множини відповідно. Наведемо прототипи цих процедур.

Include (var S;i):

Exclude(var S;i);

Тут s — це змінна множинного типу; і — елемент, який включають до множини s або видаляють з неї. Тип і повинен бути базовим типом множини s.

Завершуючи розгляд операцій над множинами, зазначимо, що, як і змінним усіх інших типів мови Раsсаl, змінній деякого множинного типу можна присвоювати значения внразів того самого типу. Слід зауважнти, що одноелементна множина може бути утворена і шляхом запису імен цієї змінної базового типу у квадратних дужках. Тому коректним є такє присвоення:

<ім’я змінної тпу множини>:=[<ім’я змінної базового типу>];

Подальші модифікації значень змінної базового типу, використаної у так присвоєнні, не призведуть до модифкації значень відповідної множиннохї змінної. Наприклад, після присвоєнь х:-=1; А: =[x]; х;=2; значення єдиного елемента множини А дорівнюватиме одиниці.

Приклад 8.8 демонструє застосування операції над множинами. У просторі формуються дві множини: множина символів ensemble та множина чисел Digit. Множина ensemble спочатку є порожньою, введені користувачем символи додаються до неї доти, доки не буде введено символу ' п ' При цьому введені знаки питання замінюються знаками оклику. 3 множини Digit яка спочатку містить цілі числа від 1 до 10, введені користувачем елементи вилучаються доти, доки не буде вилучено одиницю.

Приклад 8.8

var ensemble: set of char;

     Digit: set of byte;

     Ch:char;

     number:byte;

begin

   ensemble:=[ ];

   repeat

     writeln(‘Enter symbol. Enter “n” to finish’);

     readln(ch);

     ensemble:=ensemble+[ch];

     if ch=’?’ then ensemble:=ensemble+[‘!’];

  until ‘n’ in ensemble;

  Digit:=[1..10];

  repeat

     writeln (‘Enter number. Enter 1 to finish’);

     readln(number);

     Digit:=Digit-[number];

   Until not(1 in Digit);

end.

У прикладі 8.9 реалізовано операції введення та виведення множини. Значення, що були введені до змінної ch базового типу, додаютъся до множини symbol операцією об’єднання (+). Підприємств час виведення множини symbol переглядаються всі елементи її базового типу, які можуть бути введенні користувачем.Кожен із них перевіряється на належність множині.

Приклад 8.9 .

progrem ex8_3;

var

    symbol:set of char;

    ch:char;

begin

  writeln(‘print elements from set’);

  symbol:=[ ];

  repead

     writeln(‘enter symbol, press “n” to finish’);

     readln(ch);

    symbol:=symbol+[ch];

  until ch=’n’;

  for ch:=’0’ to ‘я‘ do

    if ch in symbol then write(ch, ‘ ‘);

  readln;

end.

5. Зображення множим в оперативній пам'яті

Значеннями однієї змінноі множинного типу можуть бути множини різної потужності, але потужність будь-якої з цих множин не може перевищувати кількість елементів базового типу. Тому обсяг пам'яті, виділеної для зберігання множинної змінної, визначається базовим типом цієї змінної. Кожне значення базового типу зображується одним бітом. Порядок розташування бітів відповідає визначеному у базовому типі порядку (нагадаємо, що базовим типом множини може бути лише порядковий тип даних). Належність елемента до множини позначається одиничним значенням відповідного біту, а відсутність елемента у множині — нульо-вим значенням. Розглянемо приклад.

Приклад 8.10

Нехай у програмі оголошено деякий множинний тип, базовим типом якого є набір 26 символів ‘A’..’Z’. Під час компіляції програми змінній такого множинного типу буде виділено 26 бітів пам’яті. На початковому етапі виконання програми ці біти будуть заповнені нулями, а підприємств час присвоєння змінній деякої множини великих латинських літер нулі у відповідних бітах буде замінено одиницями. Наведемо код демонстраційної програми та побітове зображення утвореноє в цій програмі множини m.

type Letters = set of ‘A’..’Z’;

var m: Letters;

begin

    m:=[‘P’,’A’,’S’,’C’,’A’,’L’];

    for ch:=’A’ to ‘Z’ do

      if ch in m then write(ch, ‘ ‘);

end.

1

0

1

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

0

0

0

0

0

0

0

                Зіставлення бітів і значень елементів базового типу

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

У результаті виведення значень елементів множнни отримаємо набір символів 'А С L Р S'. Цей приклад ілюструє взаємозв'язок особливостей зображення множин в оперативній пам'яті з такими їх властивостями, як відсутність повторень і невпорядкованість елементів.

Зображення множини у вигляді бітового масиву зводить операції об'єднання перетину та різниці двох множин до порозрядних логічних операцій над послідовністю бітів. Наприклад, перетин множин виконується шляхом логічного множення бітів:

var m,n:set of 1..9;

m:=[2,4,5,6,7,8,9];                      010111111

n:=[1,3,5,7,9];                             101010101

m*n=[5,7,9];                               000010101

Значення елементів множин   123456789

Контрольні питання

1. Множини

2. Поняття множини та множинного типу даних

3. Оголошення змінних множинного типу

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

5. Зображення множим в оперативній пам'яті


 

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

46596. Пряме й переносне значення слова. Вияви полісемії в різностильових текстах 21.5 KB
  Пряме й переносне значення слова. Пряме значення слова це дефініція слова яка безпосередньо вказує на його співвідношення з тією чи іншою ознакою об'єктивної дійсності як це історично закріпилося у свідомості мовців. Це первинне значення слова. Переносне значення слова це одне із значень слова яке виникло внаслідок перенесення одних ознак предметів чи явищ на інші.
46597. Синонімія, види синонімів. Роль синонімів у різностильових текстах 21.5 KB
  Синонімія це сукупність синонімів тієї чи іншої мови а також розділ науки про мову у якому вивчаються синоніми як одиниці мови. Синоніми це слова однієї частини мови що мають близьке лексичне значення але відрізняються за формою. Традиційно виділяють загальномовні синоніми зрозумілі для кожного носія мови граний красивий; контекстуальні або авторські синоніми у конкретному тексті. Окремо виділяють абсолютні синоніми слова які мають тотожні значення лелека чорногуз сум смуток століття сторіччя.
46598. Неологізми, архаїзми, історизми в українській літературній мові 21.5 KB
  За вживанням вона поділяється на активну слова що регулярно вживаються в певній сфері діяльності тобто щоденні слова та професіоналізми пасивну застарілі слова та неологізми. Застарілі слова слова що перестали активно вживатися носіями мови. До них відносять архаїзми слова які називають поняття які існують і в наш час пїїт поет спудей студент загально повільно; історизми слова які позначають поняття які зникли комсорг волость хорунжий Існує багато причин чому слова відходять до пасивного вжитку зокрема і...
46599. Синтаксична норма. Порядок слів у реченні 21.5 KB
  Порядок слів у реченні. Розрізняють типи норм: орфоепічні правильна вимова акцентуаційні наголошення слів лексичні слововживання граматичні морфологічні та синтаксичні стилістичні орфографічні правила написання пунктуаційні. Вони передбачають правильне вживання граматичних форм слів узгодження керування прилягання морфологічні та правильне утворення словосполучень і речень синтаксичні. В українській мові вільний порядок слів у реченні тобто немає чітких правил розташування у певному порядку тих чи інших членів речення.
46600. BELARUSIAN CUISINE 21.5 KB
  Belarusian cuisines have influences from its neighboring countries like Russia, Lithuania, Ukrainian and Polfnd among others. A variety of dishes made of potato form an important part of most cuisines in Belarus. Some of the popular potato dishes in Belarusian cuisines include Belarusian Draniki, Belarusian Draniki with Pork, Kolduni, Babka and Belarusian Kartoflyaniki among others
46601. Кодификация советского права 1920-х годов 21.53 KB
  Гражданский кодекс РСФСР был принят четвертой сессией ВЦИК девятого созыва 31 октября 1922 г. Отличительными чертами ГК РСФСР 1922 г. ГК гарантировал всем гражданам РСФСР охрану гражданских прав независимо от пола расы национальности вероисповедания и происхождения но в то же время ограничивал свободу предпринимательской деятельности и частной инициативы если осуществление гражданских прав противоречит их социальнохозяйственному назначению наносит явный ущерб государству. Право на пользование землей для ведения сельского хозяйства при...
46602. Планирование учебно-воспитательной работы по изобразительному искусству 21.55 KB
  Проблемы психического развития личности в онтогенезе факторы движущие силы закономерности. Филогенез развития вида онтогенез развитие индивида.Декарт и ЖанЖак Руссо представители природного биологизаторского направления идея которого состоит в том что наибольшее значение для развития личности имеет наследственность генетические факторы влияние среды минимально.Непосредственными движущими силами психического развития ребенка являются противоречия которые возникают и преодолеваются в процессе обучения и воспитания.
46603. РОССИЙСКАЯ ФЕДЕРАЦИЯ. ЗАКОН ОБ АВТОРСКОМ ПРАВЕ И СМЕЖНЫХ ПРАВАХ 21.55 KB
  Основные понятия Для целей настоящего Закона указанные ниже термины имеют следующее значение: автор физическое лицо творческим трудом которого создано произведение; аудиовизуальное произведение произведение состоящее из зафиксированной серии связанных между собой кадров с сопровождением или без сопровождения их звуком предназначенное для зрительного и слухового в случае сопровождения звуком восприятия с помощью соответствующих технических устройств; аудиовизуальные произведения включают кинематографические произведения и все...
46604. Виды трения. Износ при сухом, граничном, полужидкостном и жидкостном трении. Роль смазки 21.6 KB
  Трение сопротивление возникающее при взаимном перемещении соприкасающихся поверхностей тел. В зависимости от кинематических признаков относительного перемещения тел чаще всего встречаются два вида трения: трение скольжения и трение качения. В зависимости от состояния трущихся поверхностей различают: трение без смазки трение двух твердых тел при отсутствии на поверхности трения введенного смазочного материала всех видов; граничное трение трение двух твердых тел при наличии на поверхности трения слоя жидкости обладающего...