69116

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

Лекция

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

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

Украинкский

2014-09-30

96.5 KB

4 чел.

Лекція 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. Зображення множим в оперативній пам'яті


 

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

63781. Теоретические основы и организационные принципы здравоохранения 24 KB
  Система здравоохранения это совокупность взаимосвязанных мероприятий которые содействуют укреплению здоровья и проводятся на дому в учебных заведениях на рабочих местах в общинах в физическом...
63782. Три органа управления здравоохранением 26.5 KB
  Среди органов управления здравоохранением следует выделять центральные республиканские и местные краевые областные городские районные органы здравоохранения. К центральным органам относятся министерства здравоохранения которые несут ответственность за состояние и развитие медицинской помощи.
63783. Основы законодательства РФ по охране здоровья граждан 44.5 KB
  Основы законодательства РФ по охране здоровья граждан Охрана здоровья граждан это совокупность мер политического экономического правового социального культурного научного медицинского санитарно-гигиенического и противоэпидемического характера...
63784. Закон “О медицинском страховании граждан в Российской Федерации”. Добровольное медицинское страхование 40.5 KB
  Для реализации закона разработаны и утверждены положения о медицинских страховых организациях о порядке выдачи лицензий на право заниматься медицинским страхованием базовая программа обязательного медицинского страхования...
63785. Лицензирование и аккредитация медицинских учреждений 24.5 KB
  Учреждения ЛПУ У ЛПУ появились дополнительные источники финансирования: бюджетные средства средства органов управления здравоохранения если участвуют в целевых и комплексных программах; средства страховых компаний ОМС и ДМС...
63786. Статистический метод 22 KB
  Медицинская статистика подразделяется на два раздела: статистика здоровья населения и статистика здравоохранения. Медицинская статистика используя математические законы позволяет выявлять закономерности в изучаемых явлениях подтверждать...
63787. Статистическое исследование и его этапы 23.5 KB
  Составление плана и программы исследования: формулирование цели и задач исследования в соответствии с рабочей гипотезой; определение и подбор статистической совокупности; определение единицы наблюдения; выбор вида статистического исследования...
63788. Статистическая совокупность, ее свойства 21 KB
  Статистическая совокупность группа относительно однородных элементов единиц наблюдения в конкретных условиях времени и пространства. В зависимости от охвата единиц наблюдения в связи с целью исследования статистическая совокупность может быть генеральной и выборочной.
63789. Распределение признака в статистической совокупности. Альтернативный анализ. Относительный величины 25.5 KB
  Виды относительных величин:1 экстенсивные показатели; 2 интенсивные показатели;3 коэффициенты соотношения; 4 коэффициенты наглядности. Экстенсивные показатели характеризуют структуру изучаемого явления отношение части к целому то есть определяют долю удельный вес процент части в целом принятом за 100. Интенсивные показатели отражают частоту уровень распространенности явления в своей среде. Показатели соотношения характеризуют отношение между двумя разнородными биологически не связанными между собой статистическими совокупностями...