Множества
Множества – это структуры данных, наряду с переменными, массивами и строками.
Понятие множества является одним из основных понятий современной математики.
Под множеством понимается неупорядоченная совокупность неповторяющихся объектов (элементов), обладающих некоторыми одинаковыми свойствами и находящихся в некоторых отношениях между собой и с элементами других множеств: множество учебных заведений, множество студентов в институте и т.д.
Под множеством в Паскале понимается неупорядоченный набор фиксированного количества (не более 255) неповторяющихся однотипных элементов, имеющих общее имя – имя множества.
В отличие от массива – упорядоченной совокупности элементов, в которой каждый элемент однозначно определяется значением своего индекса (индексов), элементы множества таких индексов не имеют. Они размещаются во множестве неупорядоченно, поэтому значение отдельного элемента нельзя прочитать из множества, а можно только установить, входит или нет он в данное множество. Значит, множества используются в тех случаях, когда интерес представляет не конкретное значение отдельного элемента множества, а лишь факт его наличия или отсутствия в данном множестве однотипных элементов.
В Паскале допускаются только множества с заранее определенным числом элементов одного типа, который называется базовым типом множества. Допускаются множества следующих типов:
1. целого (множество целых чисел, не более 255 чисел),
2. логического (множество, состоящее из двух логических констант: TRUE и FALSE),
3. символьного (множество символов таблицы ASCII),
4. перечисляемого,
5. интервального.
Таким образом, в Паскале не определено множество, состоящее из чисел с дробной частью (REAL).
Прежде чем использовать множество в программе, его необходимо описать – назвать его имя и указать базовый тип. Описание множества можно произвести следующими способами:
1. объявлением его имени и типа в разделе описания переменных Var :
Var r : Set Of ‘a ’. . ’c’;
d : Set Of 1 . . 4;
Описано множество r символов алфавита от ‘a’ до ‘c’ и множество d целых чисел 1, 2, 3, 4.
Внимание! Между начальным и конечным значениями интервала ставятся две точки!
2. объявлением типа множества в разделе определения типов Type и его имени – в разделе описания переменных Var :
Type TSymb = Set Of ‘a’ . . ‘c’;
TNumb = Set Of 1 . . 4;
Var r : TSymb;
d : TNumb;
3. заданием множества как типизированной константы:
Constr : Set Of ‘a ’. . ’c’ = [‘a’,’c’];
d : Set Of 1 . . 4 = [2,1,3];
Внимание! Элементы множества перечисляются в квадратных скобках через запятую.
Элементы ножества можно задавать следующими способами:
a)перечислением отдельных его значений:
[‘c’, ‘a’, ‘e’] [76, 102, 5, 12]
b)интервалом базового типа:
[25..45, 3..10] [‘a’..’d’, ‘k’..’n’]
c)выражениями базового типа:
[Ord(109),’s’] [Succ(3), Pred(9), Round(Sin(1.0))]
Множество может принимать значения любых наборов элементов, указанных в его описании. Например, описанное ранее множество r может принимать следующие значения:
[‘a’, ‘b’, ‘c’]
[‘a’, ‘b’]
[‘a’, ‘c’]
[ ‘b’, ‘c’]
[‘a’]
[ ‘b’]
[ ‘c’]
[] пустое множество
а множество d - следующие:
[1, 2, 3, 4]
[1, 2, 3]
[1, 3, 4]
[1, 2, 4]
[2, 3, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
[1]
[2]
[3]
[4]
[]
Таким образом, любое множество может принимать 2n значений, где n – количество элементов в описании множества.
Порядок следования элементов во множестве не устанавливается, поэтому, например, значения множества [‘a’, ‘b’, ‘c’] и [‘b’, ‘c’, ‘a’] эквивалентны.
При работе со множествами в Паскале можно использовать следующие операции:
+ объединение (сумма) множеств,
* пересечение (произведение) множеств,
- разность множеств,
Inвхождение элемента во множество.
Пересечением двух множеств называется множество, состоящее из элементов, одновременно входящих в оба множества-сомножителя:
[3, 4, 5] * [1, 3, 5] = [3]
[3, 4, 5] * [3, 4, 5] = [3, 4, 5]
[2, 1, 0] * [] = []
[2, 9, 8] * [6, 7] = [] пустое множество
[‘a’, ‘b’, ‘c’] * [‘d’, ‘c’, ‘a’] = [‘a’, ‘c’]
Объединением двух множеств называется множество, состоящее из элементов, входящих хотя бы в одно из множеств-слагаемых:
[3, 4, 5] + [1, 3, 5] = [1, 3, 4, 5]
[2, 9, 8] + [] = [2, 9, 8]
[1, 2, 3] + [1, 2, 3] = [1, 2, 3]
[‘a’, ‘b’, ‘c’] + [‘d’, ‘c’, ‘a’] = [‘a’, ’b’, ‘c’, ‘d’]
Разностью двух множеств называется множество, состоящее из элементов множества-уменьшаемого без элементов множества-вычитаемого:
[3, 4, 5] – [1, 3, 5] = [4]
[2, 9, 5] – [3, 7] = [2, 9, 5]
[2, 4] – [5, 4, 2] = []
Эти операции используются для построения выражений, содержащих множества, причем в этих выражениях сначала выполняются операции пересечения, а затем – операции объединения и разности. Порядок выполнения операций может быть изменен с помощью скобок:
([3, 4, 5] + [1, 3, 6, 7]) * [5, 6, 7] – [6] = [5, 7]
Пример: в группе 12 студентов. Заданы множества номеров студентов:
1. множество спортсменов sport = [1, 2, 3, 4, 5]
2. множество отличников otl = [2, 3, 6, 7]
3. множество курящих smok = [7, 8]
Определить:
1. множество спортсменов-отличников:
sport * otl = [1, 2, 3, 4, 5] * [2, 3, 6, 7] = [2, 3]
2. множество спортсменов или отличников:
sport + otl = [1, 2, 3, 4, 5] + [2, 3, 6, 7] = [1, 2, 3, 4, 5, 6, 7] = [1 . . 7]
3. множество курящих спортсменов:
sport * smok = [1, 2, 3, 4, 5] * [7, 8] = [] - пустое множество – спортсмены не курят!
4. множество некурящих отличников:
otl – smok = [2, 3, 6, 7] – [7, 8] = [2, 3, 6]
Для проверки вхождения какой-либо константы или переменной в определенное множество используется операция In , результатом которой является TRUE, если это значение входит во множество, и FALSE – если не входит:
5 In [1, 5, 7] = TRUE
‘b’ In [‘a’, ‘c’, ‘d’] = FALSE
Наряду с этими операциями, над множествами определены и операции сравнения, используемые для сравнения однотипных множеств. Пусть A и B -два однотипных множества, тогда:
A <= B равно TRUE, если все элементы множества A входят во множество B:
[5, 3, 2] <= [1, 2, 3, 4, 5] = True
A >= B равно TRUE, если все элементы множества B входят во множество A:
[‘d’, ‘e’, ‘f’, ‘g’] >= [‘d’, ‘g’] = True
A = B равно TRUE, если элементы этих множеств полностью совпадают:
[1, 2, 3] = [3, 2, 1] = TRUE
A <> B равно TRUE, если эти множества различаются хотя бы одним элементом:
[1, 2, 3] <> [5, 2, 1] = TRUE
Выражения со множествами, построенные с помощью операций *, + и - , могут быть использованы в операторах присваивания вида:
V := S;
где V – переменная-множество,
S – выражение со множествами того же типа.
Внимание! Элементы множеств нельзя вводить и выводить операторами Read и Write, то есть имя множества не должно появляться в списках операторов ввода-вывода.
Дата добавления: 2015-08-08; просмотров: 530;