Лекция: Множества
Наряду с числом множество является фундаментальным математическим понятием. К операциям и отношениям со множествами сводится большинство математических моделей. Паскаль – один из немногих языков, который имеет встроенные средства для работы со множествами. Давайте посмотрим, как «переводятся» на Паскаль некоторые понятия теории множеств.
В математике рассматривают конечные и бесконечные множества, состоящие из произвольных элементов. В Паскале множества всегда конечные, причем состоят не более чем из 256 элементов. Все элементы множества должны быть одного порядкового типа (например, Integer, Word, Longint).
Пусть, например, необходимо задать множества целых чисел:
Обозначения в математике Обозначения в Паскале
{1, 2, 3} [1, 2, 3]
0 []
{1, 2,…N} [1…N]
В Паскале множество может быть задано выражениями, например
[2+x, 8-3].
Внутреннее представление множеств.Все значения множества представляются в памяти последовательностями битов одинаковой длины. За каждое значение базового типа «отвечает» 1 бит. Если множество содержит некоторый элемент, в соответствующем бите хранится 1, если не содержит – хранится 0.
Например:
var x, y: set of 1..10;
Внутреннее представление: x:=[] 0000000000
x: =[2,3,9] 0110000010
y: =[2..7] 0111111000
Операции над множествами сводятся к поразрядным логическим операциям над последовательностями битов. Например, объединение множеств выполняется путем поразрядного логического сложения битов. Объединение множеств x È y
x: 0110000010
y: 0111111000
x È y: 0111111010
Поскольку поразрядные операции входят в набор команд процессора ЭВМ, они выполняются очень быстро.
Множества в Паскале– это наборы однотипных, логически связанных между собой объектов, которые рассматриваются как единое целое. Причем характер связи подразумевается программистом и никак не контролируется Паскалем. Например, множество согласованных букв кириллицы; множество простых чисел от 1 до 100.
Каждый объект в множестве называется элементом множества. Все элементы множества должны принадлежать к одному из скалярных типов. Этот тип называется базовым типом. Базовый тип задается диапазоном или перечислением. Если множество не имеет элементов, оно называется пустым([]).
Для изображения множеств используют квадратные скобки, в которые заключается перечень элементов.
Например: type
color=(white, red, black);
Number=set of 1..31; {явное описание}
Var
col: set of color; {неявное описание}
n1, n2: number;
etter: set of char; {неявное описание}
Попытка присвоить недопустимый символ вызовет прерывание. Контроль диапазонов можно установить опцией компилятора {$R+}.
Операции над множествами.В Паскале разрешены следующие операции над множествами: сравнения (=, < >, > =, < =), Ç (and), È (or), разность множеств (-), включение в множество – in. Рассмотрим их назначение.
"=": два множества равны тогда и только тогда, когда они имеют одинаковые элементы. Порядок следования роли не играет.
1) A: set of 1, 2, 3, 4 B: set of 1, 3, 2, 4 A = B — true
2) A: set of 'a', 'b', 'c' B: set of 'a', 'b' A = B — false
«< >»: множества не равны, если они отличаются по значению хотя бы одного элемента.
В случае 1) A < > B – false;
в случае 2) A < > B – true.
«> =» используется для определения принадлежности множеств. A > = B, если все элементы B содержатся в множестве A.
«<=» – аналогично.
A: =1, 2, 3, 4 B: =2, 3, 4 A >= B true ВÌ А
B <= A true
«in» используется для проверки принадлежности какого-либо значения множеству. Пусть x='a', y='z', B – множество символов 'a'..'n'. Тогда x in B – true, y in B – false.
Обычно операция in используется в условном операторе. Например, вместо:
if(a=1) or (a=5) or (a=7) or (a=11) or (a=15) then…,
можно записать: if a in [1,5,7,11,15] then…,
т. е. «in» позволяет более эффективно производить сложные проверки условий. При этом множество не обязательно предварительно описывать в разделе описаний.
Если необходимо проверить, не принадлежит ли n множеству A, можно записать: Not (n in A) (неверно: n Not in A).
Объединение множеств È: «+». Объединением двух множеств является третье множество, содержащее элементы обоих множеств (выполняется путем поразрядного логического сложения).
Пусть A:=[1,2,3], B:=[4,5], C:=A+B, тогда C=[1, 2, 3, 4, 5].
Пересечение множеств Ç: «*».
Пусть A:=[1,2,3], B:=[1,4,2,5], тогда A*B=[1, 2].
Пусть A:= ['A'..'Z'], B:= ['B'..'Y'], тогда A*B=['B'..'Y'],
т. е. третье множество, которое содержит элементы, входящие одновременно в оба множества.
Разность множеств «-» (\- в математике) – третье множество, которое содержит элементы первого множества, не входящие во второе:
Пусть A := [1,2,3,4], B:= [3,4,1], тогда A-B=[2].
Пусть A := [x1,x2,x3,x4], B:= [x2,x3], тогда A-B=[x1, x4].
Преимущества использования типа set: значительно упрощаются сложные условия в операторе if, увеличивается степень наглядности, экономятся память, время компиляции и выполнения.
Отрицательные стороны: отсутствуют средства ввода-вывода элементов множеств.
П р и м е р ы
1. В считанном с клавиатуры тексте из строчных латинских букв удалить все гласные буквы, а согласные заменить на прописные. Признак конца ввода – точка. Например: pointer — > PNTR.