Множественный тип данных. Представление множеств. Операции над множествами.

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

Множественный тип описывается с помощью служебных слов Set of, например: Множественный тип описывается с помощью служебных слов Set of, например: type M= Set of B; type M= Set of B; Здесь М – множественный тип; В – базовый тип. Здесь М – множественный тип; В – базовый тип. Пример описания переменной множественного типа: Пример описания переменной множественного типа: type M= Set of 'A'..'D'; type M= Set of 'A'..'D'; var MS: M; var MS: M;

Принадлежность переменных к множественному типу может быть определена прямо в разделе описания переменных: var C: Set of 0..7; Константы множественного типа записываются в виде заключенной в квадратные скобки последовательности элементов или интервалов базового типа, разделенных запятыми, например: ['A', 'C'] [0, 2, 7] [3, 7, ]. Константа вида [ ] означает пустое подмножество.

Множество включает в себя набор элементов базового типа, все подмножества данного множества, а также пустое подмножество. Если базовый тип, на котором строится множество, имеет К элементов, то число подмножеств, входящих в это множество, равно 2 в степени К. Пусть имеется переменная Р интервального типа: var P: 1..3; Эта переменная может принимать три различных значения – либо 1, либо 2, либо 3. Переменная Т множественного типа var T: Set of 1..3; может принимать восемь различных значений: [ ] [1,2] [1] [1,3] [2] [2,3] [3] [1,2,3] Порядок перечисления элементов базового типа в константах безразличен. Значение переменной множественного типа может быть задано конструкцией вида [T], где T – переменная базового типа.

К переменным и константам множественного типа применимы операции присваивания (:=), объединения (+), пересечения (*) и вычитания (-): ['A','B'] + ['A','D'] даст ['A','B','D'] ['A'] * ['A','B','C'] даст ['A'] ['A','B','C'] - ['A','B'] даст ['C']. Результат выполнения этих операций есть величина множественного типа.

К множественным величинам применимы операции: тождественность (=), не тождественность (<>), содержится в ( =). Результат выполнения этих операций имеет логический тип, например: ['A','B'] = ['A','C'] даст FALSE ['A','B'] <> ['A','C'] даст TRUE ['B'] <= ['B','C'] даст TRUE ['C','D'] >= ['A'] даст FALSE.

Кроме этих операций для работы с величинами множественного типа в языке Паскаль используется операция in, проверяющая принадлежность элемента базового типа, стоящего слева от знака операции, множеству, стоящему справа от знака операции. Результат выполнения этой операции – булевский. Операция проверки принадлежности элемента множеству часто используется вместо операций отношения, например: A in ['A', 'B'] даст TRUE, 2 in [1, 3, 6] даст FALSE.

При использовании в программах данных множественного типа выполнение операций происходит над битовыми строками данных. Каждому значению множественного типа в памяти ЭВМ соответствует один двоичный разряд. Например, множество ['A','B','C','D'] представлено в памяти ЭВМ битовой строкой Подмножества этого множества представлены строками: ['A','B','D'] ['B','C'] ['D']

Величины множественного типа не могут быть элементами списка ввода – вывода. В каждой конкретной реализации транслятора с языка Паскаль количество элементов базового типа, на котором строится множество, ограничено. В Турбо Паскале количество базовых элементов не должно превышать 256. Инициализация величин множественного типа производится с помощью типизированных констант: const seLit: Set of 'A'..'D'= [];

Проиллюстрируем применение данных множественного типа на примере. Пример. Составить программу, которая вырабатывает и выводит на экран дисплея наборы случайных чисел для игры в "Спортлото 5 из 36". Для заполнения каждой карточки спортлото необходимо получить набор из пяти псевдослучайных чисел. К этим числам предъявляются два требования: – числа должны находиться в диапазоне 1…36; – числа не должны повторяться.

Program Lotto; Var nb, k: Set of 1..36; kol, l, i, n: Integer; Begin Randomize; WriteLn('ВВЕДИ kol'); ReadLn(kol); nb:=[1..36]; for i:=1 to kol do begin k:=[]; for l:=1 to 5 do begin repeat n:=Random(36) until (n in nb) and not (n in k); k:=k+[n]; Write(n:4) end; WriteLn end End.