- •Курс «основы алгоритмизации и программирования»
- •Тема: «организация данных в множества»
- •1. Понятие и определение множества в теории множеств.
- •2. Понятие и обозначение множества в Паскале.
- •3. Определение множественного типа.
- •4. Операции над множествами.
- •5. Использование множеств в программах.
- •6. Индивидуальные задания.
- •Контрольные вопросы
- •Тема: «организация данных в множества»
- •- Страница 6 -
3. Определение множественного типа.
Для использования в Паскаль-программах таких структур данных, как множества, в язык введено понятие множественного типа. Значением множественного типа является множество. Как и любой тип в Паскале, множественный тип определяет область допустимых значений, относящихся к этому типу, и операции, применимые к этим значениям. Область допустимых значений множественного типа есть множество-степень базового типа. В общем виде описание множественного типа реализуется следующей конструкцией:
type <имя_типа> = set of <базовый_тип>;
В качестве базового типа, из значений которого создаются конкретные значения множественного типа – множества, может быть использован допустимый стандартный тип, либо тип, ранее определенный пользователем. Например:
type letter = ‘a’..’z’; {базовый тип}
setoflettres = set of letter;
Тип setoflettresвключает в себя все возможные подмножества элементов базового типа – буквы отaдоz, а также пустое множество.
Если базовый тип содержит kзначений, то множественный тип определяет2kподмножеств, относящихся к значениям данного множественного типа, в том числе пустое множество. Например, множественный типset of 1..3, определяет область из 23подмножеств: [ ], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. А множественный типset of boolean, определяет область из 22подмножеств: [ ], [false], [true], [false,true].
Если в программу введен множественный тип, то могут быть объявлены и использованы переменные и типизированные константымножественного типа. Например:
var gllettres: setoflettres;
A, B, C: setoflettres;
begin
. . .
glletters:=[‘a’,’e’,’I’,’o’,’u’];
A:=[‘i’,’j’,’r’,’l’,’m’,’n’];
B:=A;
C:=[ ];
При введении типизированных констант-множеств их начальные значения задаются с помощью конструктора множества:
type ten=set of 0..9;
number=set of ‘0’..’9’;
const index: ten=[0,2,4,6,8];
digit: number=[‘0’..’9’];
begin
. . .
digit:=[‘1’,’3’,’5’,’7’,’9’];
Переменные и типизированные константы множественного типа могут участвовать в операторах присваивания слева и справа от знака присваивания, если они принадлежат к идентичным типам.
4. Операции над множествами.
К переменным и константам множественного типа в Паскале применимы операции «+» - объединение; «*» -пересечение (умножение); «-» -разность.
Объединением (суммой) двух и более множеств называется множество, состоящее из элементов, входящих хотя бы в одно из исходных множеств.Например:
[1, 3, 5] + [3, 7, 9] = [1, 3, 5, 7, 9].
Пересечением (умножением) двух и более множеств называется множество, состоящее из элементов, входящих хотя бы в одно из исходных множеств.Например:
[0, 2, 4, 6] * [2, 4, 8] = [2, 4].
Пересечение множеств может быть пустым:
[1, 3, 5, 7, 9] * [0, 2, 4, 6, 8] = [ ].
Разностью между множеством В и множеством А называется множество элементов из В, не являющихся элементами из А.Например:
[0 .. 9] – [1, 3, 5, 7, 9] = [0, 2, 4, 6, 8].
Над множествами в Паскале определены также следующиеоперации отношения:
-
A = B
тождественность множеств (в математике )
A <> B
нетождественность множеств (в математике )
A <= B
А содержится в В (в математике )
A >= B
А содержит В (в математике )
Например, отношение
-
[0] = [ ]
имеет значение false
[0, 2, 4, 6, 8] = [8, 6, 4, 2, 0]
имеет значение true
[0] <= [0, 2, 4, 6, 8]
имеет значение true
[0, 2, 4, 6, 8] >= [1, 3]
имеет значение false
Операция отношения x in A проверяет принадлежность элемента базового типа x множеству А (в математике). Например, если описано множество
const A: set of 50..53 = [50..53];
то отношение 50 inАимеет значениеtrue, а отношение 50in[51..53] имеет значениеfalse.
Введенные операции над множествами позволяют строить некоторые выражения для получения новых множественных значений. При вычислении значений множественных выражений действует установленное правило приоритета операций:операции объединения и разности множеств относятся к операциям типа сложения и имеют тот же приоритет, что и все остальные операции типа сложения; операция пересечения множеств относится к операциям типа умножения; все операции отношения имеют наименьший приоритет.Например, значение выражения
-
[1, 2, 5, 6, 7] * [2..6] + [3, 9]
равно [2, 3, 5, 6, 9]
([3, 4, 5] + [1, 3, 6, 7]) * [5..7] – [6]
равно [5, 7]
(7 in [1, 3, 5, 7, 9]) and ([7] <= [1, 3, 5, 7, 9])
равно true