Множество

1.

Лекция
Множество
1

2.

Df:
Множество
это совокупность
объектов данных одного
и того же порядкового
типа называемого
базовым.
2

3.

Свойства структуры данных МНОЖЕСТВО:
1.
2.
3.
4.
Линейная
Фиксированного размера
Без доступа к элементам
Однородная
3

4.

Константы множественного типа
Задание множественного типа
Например:
[ ] - пустое множество;
[1, 3, 5, 7, 9] - множество нечетных чисел в диапазоне от 1 до 9;
[‘A’..’Z’] - множество заглавных латинских букв;
[1..1, 5..1] - множество содержит два элемента, где 1..1 - содержит один
элемент =0; 5..1 - содержит один элемент = пустому множеству;
[1, 2, 3, 2 .. 5, 6, 4, 3] [1, 2, 3, 4, 5, 6] [1..6 ] - множество состоящее из 6
элементов в диапазоне от 1 до 6
set
of
базовый
тип
;
4

5.

Пример:
Пусть задано следующее описание
множества:
set of 1 . . 3;
Вопрос:
Какие значения может принимать
переменная множественного типа?
Ответ:
[ ], [1], [1, 2], [1,3], [2,3], [2], [3], [1, 2, 3]
5

6.

Операции над множеством
• in - проверяет вхождение элемента во множество
значение базового
типа
in
множественный
тип
Например:
1 in [1. .10] - результат true
11 in [1. .10] - результат false
6

7.

•для множественных типов определены все операции отношения
запись на
Паскале
математическая
запись
значение true
значение false
А=В
А=В
множества совпадают
в противном случаи
A<>B
А В
множества не совпадают
в противном случаи
A<=B
А В (А содержится в В)
все элементы А содержатся в В
в противном случаи
A>=B
А В
все элементы В содержатся в А
в противном случаи
Например: Пусть заданы множества
chars1:=[‘a’, ‘x’, ‘e’];
chars2:=[ ‘x’];
chars3:=[‘a’. . ‘z’];
Определите истинность высказывания:
chars1 < > chars2;
chars1 >= chars2;
chars1 <= chars3;
‘a’ in chars2;
not (‘q’ in chars2);
7

8.

•для множественных типов определены операции:
• объединения;
• пересечения;
• разность
Объединение - возвращает в качестве результата все элементы операнда.
Например: d:=[2 . . 5] + [4 . . 6] d= [ 2 . . 6]
2, 3
4, 5, 6
8

9.

Пересечение - возвращает в качестве результата только общие для заданных
операндов элементы.
Например: d:=[2 . . 5] * [4 . . 6] d= [4, 5]
2, 3
6
Разность - возвращает те элементы, которые входят в первый операнд, но не
входят во второй.
Например: d:=[2 . . 5] - [4 . . 6] d= [2, 3]
2, 3
d:=[4 . . 6] - [2 . . 5]
4, 5
2, 3
6
4, 5
d= [6]
6
9

10.

Задача: Найти и напечатать в порядке убывания все
простые числа в диапазоне от [2 . . 201].
Модуль описания данных
Unit op;
Interface;
const n=201;
type
mno=set of byte;
Implementation
End.
10

11.

Основная программа
Uses op, obr;
var sim_num : mno;
begin
form(sim_num);
print(sim_num);
end.
11

12.

Модуль обработки данных
Unit obr;
Interface
Uses op;
Procedure poisk(numm : mno; var p1 : 2 .. n);
Procedure iskl (var numm : mno; p1, k1 : 2 .. n);
Procedure form(var sim_numm : mno);
Procedure print(sim_numm : mno);
Implementation
Procedure poisk(numm : mno; var p1 : 2 .. n);
begin
while not (p1 in numm) do inc(p1);
End;
Procedure iskl (var numm : mno; p1, k1 : 2 .. n);
begin
while k1< n do begin
numm:= numm -[k1];
inc (k1, p1);
end;
End;
12

13.

Procedure form(var sim_numm : mno);
var p, k : 2 .. n;
numm : mno;
begin
p:=2;
numm := [2..n];
sim_numm := [ ];
repeat
poisk(numm, p);
sim_numm : = sim_numm +[p];
k:=p;
iskl (numm, p, k);
until numm = [ ];
End;
13

14.

Procedure print(sim_numm : mno);
Var k : 2..n;
begin
for k:= n downto 2 do
if k in sim_numm then writen (k, ‘ ‘);
End;
End.
14

15.

Операция добавления или удаления
элемента во множество
процедура добавления (погружения)
include (mn; element);
процедура удаления
exelude (mn; element);
где
mn – множество базового типа;
element - элемент базового типа.
15

16.

Особенности использования
множества
служит для отслеживания элементов, что
означает - сохранение информации о
наличии или отсутствии элемента во
множестве;
не может содержать более 256 различных
значений;
не
может
содержать
повторяющиеся
элементы;
отрицательные числа не могут быть
элементами множества
16