69116

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

Лекция

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

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

Украинкский

2014-09-30

96.5 KB

11 чел.

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


 

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

37803. Ознайомлення з особливостями застосування на мові Асемблера системи команд керування програмою та процесором, вивчення команд умовного розгалуження 81 KB
  Вивчити основні команди керування програмою та процесором, отримати навички та вміння щодо застосування команд умовного розгалуження.
37804. Робота з дисками папками та файлами в середовищі Windows 669.5 KB
  Вивчив призначення програм основного меню при натисканні на клавішу пуск. запустив програму блокнот зафіксував у звіт призначення меню файли. За допомогою правої правої клавіші миші обо через меню Программы війти в програму проводник.
37805. Програмування лінійних та розгалужених алгоритмів 62.52 KB
  Ознайомитися з операторами вводу, виводу і присвоєння, навчитися записувати лінійні алгоритми на мові програмування Pascal; закріпити теоретичні відомості про розгалужені алгоритми, оператори передачі управління, навчитися програмувати розгалуження.
37806. Види модуляцій в сучасних інформаційних системах 8.77 MB
  Мета роботи: Дослідження і вивчення особливості видів модуляції які застосовуються в цифровій техніці ознайомитися з елементами модуляторів і демодуляторів а також із принципами їх роботи. Порядок виконання роботи Ознайомитися з принципами математичного моделювання модуляції які використовуються лабораторною програмою.
37807. Вказівники 2.14 MB
  Мета: навчитися програмувати з використанням вказівників та динамічних змінних, створювати та опрацьовувати черги та стеки.
37808. ОСНОВЫ РАБОТЫ В POWER POINT. Настройка электронной интерактивной презентации 72.5 KB
  Клавиши удаления и копирования текста и объектов Чтобы Нажмите Удалить один символ слева BCKSPCE Удалить одно слово слева CTRLBCKSPCE Удалить один символ справа DELETE Удалить одно слово справа CTRLDELETE Вырезать выделенный объект CTRLX Скопировать выделенный объект CTRLC Вставить вырезанный или скопированный объект CTRLV...
37809. ВЫЧИСЛЕНИЕ ОПРЕДЕЛЕННЫХ ИНТЕГРАЛОВ 248 KB
  4 Формула Симпсона Формула Симпсона записывается так: . Погрешность формулы Симпсона прямо пропорциональна в четвертой степени. На практике как и в случае метода трапеций расчеты ведут на сгущающихся сетках и оценку погрешности формулы Симпсона осуществляют по формуле 5. Критерием завершения процесса вычисления определенного интеграла с заданной точностью методом Симпсона на сгущающихся сетках служит условие .
37810. ОСНОВЫ РАБОТЫ С POWER POINT. Вставка таблицы Word 44.5 KB
  5 Щелкните вне таблицы для возвращения в PowerPoint. Для использования этой разметки нажмите кнопку Разметка слайда на панели инструментов Команды щелкните разметку Таблица затем нажмите кнопку Применить. Изменение таблицы Word 1 Дважды щелкните таблицу. 3 Щелкните вне таблицы для возвращения в PowerPoint и обновления таблицы показываемой в презентации.
37811. Создать калькулятор делающий: суммирование, вычитание, деление, умножение, вычисление степени 14.51 KB
  Вывод: выполняя лабораторную работу, я научилась работать с функциями.