Понятие множества. Множественный тип данных

СОДЕРЖАНИЕ: 

  1. Понятие множества
  2. Конструктор множества
  3. Описание множеств
  4. Операции над множествами
  5. Пример программы с использованием множества

Понятие множества

Понятие множества в математике является одним из основных и обозначает некоторую неупорядоченную совокупность объектов, которые называются элементами множества. Например, множество простых чисел, множество жильцов одной улицы, множество букв алфавита и т.д. Из приведенных примеров видно, что множества могут содержать подмножества (множество жильцов одной улицы состоит из подмножеств людей, живущих в разных домах на этой улице).

Следует обратить внимание на две основных особенности множеств:

  • во множестве могут содержаться элементы только одного, базового типа (например, множество простых чисел не может содержать еще и буквы);
  • порядок элементов множества не фиксируется.

Например, такая совокупность элементов {1, 2, abc, ?!?} вообще не считается множеством, а совокупности {1, 2, 5, 8} и {8, 1, 5, 2} – эквивалентные множества.

Для представления такого типа данных и для реализации некоторых моментов математического аппарата теории множеств в Паскале существует множественный тип данных (множества).

Множеством называется совокупность однотипных элементов, рассматриваемых как единое целое. В Паскале могут быть только конечные множества. Число элементов исходного множества в Турбо Паскале не может быть больше 256, а порядковые номера элементов (т.е. значения функции Ord) должны находиться в пределах от 0 до 255.

В отличие от элементов массива элементы множества не пронумерованы, не упорядочены. Каждый отдельный элемент множества не идентифицируется, и с ним нельзя выполнить какие-либо действия. Действия могут выполняться только над множеством в целом.

Тип элементов множества называется базовым типом. Базовый тип может быть любой простой тип (стандартный, перечисляемый или ограниченный), за исключением типов Integer и Real, т.к. в этом случае мощность множества будет превышать 256.        

Исходя из особенностей внутреннего представления множеств, можно сделать два основных вывода:

  • в множестве не может быть одинаковых элементов, что согласуется и с нашими математическими знаниями;
  • все операции над множествами выполняются значительно эффективней, чем над другими структурами данных.

 

Конструктор множества

Конкретные значения множества задаются с помощью конструктора множества, представляющего собой список элементов, заключенный в квадратные скобки. Сами элементы могут быть либо константами, либо выражениями базового типа.

Примеры задания множеств с помощью конструктора:

[3, 4, 7, 9, 12] – множество из пяти целых чисел;

[1..100] – множество целых чисел от 1 до 100;

[‘a’, ‘b’, ‘c’] – множество, содержащее три литеры a, b, c;

[‘A’..’Z’, ‘?’, ‘!’] – множество, содержащее все прописные латинские буквы, а также знаки ? и !.

Символы [] обозначают пустое множество, т.е. множество, не содержащее никаких элементов.

Не имеет значения порядок записи элементов множества внутри конструктора. Например, [1, 2, 3] и [3, 2, 1] эквивалентные множества.

Каждый   элемент   во   множестве  учитывается  только  один  раз.   Пример:   множество  [1, 2, 3, 4, 5]  эквивалентно [1..5].

 

Описание множеств

Для задания типа множества используются зарезервированные слова Set и Of, а затем указываются элементы этого множества, как правило, в виде перечисления или диапазона.

 Множества могут быть описаны двумя способами:

  • Type имя_типа = Set Of базовый тип;

Var имя_множества: имя_типа;

  • Var имя_множества: Set Of базовый тип;

Здесь базовый тип — тип элементов, входящих во множество.

Пример 1:

Type

digits = Set Of 1..5;

Var

 s: digits;

 

 

Пример 2:

Type

  elemcolor = (red, yellow, blue);

  color = Set Of elemcolor;

 

Пример 3:

Var A, D: Set Of Byte;

B: Set Of ?a? .. ?z?;

C: Set Of Boolean;

 

Нельзя вводить значения во множественную переменную оператором ввода и выводить оператором вывода. Множественная переменная может получить конкретное значение только в результате выполнения оператора присваивания следующего формата:

< множественная переменная > := < множественное выражение >

 

Пример:

A := [50, 100, 150, 200];

B := [?m?, ?n?, ? k?];

C := [True, False];

D := A;

 

 

Кроме того, выражения могут включать в себя операции над множествами.

Операции над множествами

В Паскале реализованы основные операции теории множеств. Это объединение, пересечение, разность множеств. Во всех таких операциях операнды и результаты есть множественные величины одинакового базового типа.

  • Объединение множеств. Объединением двух множеств A и B называется множество, состоящее из всех элементов, принадлежащих хотя бы одному из множеств A и B. Знак операции объединения в Паскале +.

Пример:          [1, 2, 3, 4] + [3, 4, 5, 6] ? [1, 2, 3, 4, 5, 6]

  • Пересечение множеств. Пересечением двух множеств A и B называется множество, состоящее из всех элементов принадлежащих одновременно множеству A и множеству B. Знак операции пересечения в Паскале *.

Пример:          [1, 2, 3, 4] * [3, 4, 5, 6] ? [3, 4]

  • Разность множеств. Разностью двух множеств A и B называется множество, состоящее из элементов множества A, не принадлежащих множеству B. Знак операции пересечения в Паскале —.

Пример:          [1, 2, 3, 4] — [3, 4, 5, 6] ? [1, 2]

                        [3, 4, 5, 6] — [1, 2, 3, 4] ? [5, 6]

Очевидно, что операции объединения и пересечения – перестановочны, а разность множеств – не перестановочная операция.

  • Операции отношения. Множества можно сравнивать между собой, т.е. для них определены операции отношения. Результатом отношения является логическая величина true или false. Для множеств применимы все операции отношения, за исключением > и <. Ниже в таблице описаны операции отношения над множествами (множества A и B содержат элементы одного типа).
Отношение Результат
True False
A = B Множества A и B совпадают В противном случае
A <> B Множества A и B не совпадают В противном случае
A <= B Все элементы A принадлежат B В противном случае
A >= B Все элементы B принадлежат A В противном случае

 

Примеры:

 

Var M: Set Of Byte;

            M:=[3, 4, 7, 9];

 

Тогда операции отношения дадут следующие результаты:

 

Операция Результат
M=[4, 7, 3, 3, 9] true
M<>[7, 4, 3, 9] false
[3, 4]<=M true
[]<=M true
M>=[1..10] false
M<=[3..9] true

 

  • Операция вхождения. Эта операция устанавливает связь между множеством и скалярной величиной, тип которой совпадает с базовым типом множества. Если x – такая скалярная величина, а M – множество, то операция вхождения записывается так: x In M. Результат – логическая величина true, если значение x входит в множество  M, и false — в противном случае.

Пример для описанного выше множества:  4 In M — true, 5 In M – false.

 

Пример программы с использованием множества

Пусть дана строка символов с точкой в конце строки. Нужно определить число различных букв, входящих в данную строку.

 

1-й вариант:

 

Program Mn;

Var

M: Set Of Char;

Str: String;

c: Char;

i, n: Integer;

Begin

M:=[];  { M – пустое множество}

n:=0;  {переменная, считающая количество различных букв в строке}

WriteLn (?Введите строку?);

ReadLn (Str);  {ввод строки}

For i:=1 To Length (Str) Do M:=M+[Str[i]];  {формирование  множества, содержащего все буквы, входящие в строку}

For c:= ?A? To ?Z? Do  {подсчет количества элементов в множестве}

If (c In M) Then n:=n+1;

WriteLn (?Количество различных элементов в строке равно?, n)

End.

 

 

 

2-й вариант:

 

Program Mn1;

Var

M: Set Of Char;

Str: String;

c: Char;

i, n: Integer;

Begin

M:=[];  { M – пустое множество}

n:=0;  {переменная, считающая количество различных букв в строке}

WriteLn (?Введите строку?);

ReadLn (Str);  {ввод строки}

For i:=1 To Length (Str) Do

If not (Str[i] In M) Then

Begin

M:=M+[Str[i]];  {формирование  множества, содержащего все буквы, входящие в строку}

n:=n+1;

End;

WriteLn (?Количество различных элементов в строке равно?, n)

End.

 

Контрольные вопросы

  1. Что такое множество?
  2. Назовите две основные особенности множеств.
  3. Что называют конструктором множеств?
  4. Как описываются множества в Паскале?
  5. Какие операции можно осуществлять с множествами?