Множество - структурированный тип данных

1.

Множества
Множество - это структурированный тип данных

2.

Множеством (SET) называется совокупность
однотипных элементов, рассматриваемых как единое
целое.
Каждый объект в множестве называется
элементом множества.
Элементы множества не пронумерованы и не
упорядочены. Множество должно состоять из
порядковых элементов, и их число не должно
превышать 255.
Действия могут выполняться только над
множеством в целом. С отдельным элементом множества
нельзя производить какие-либо действия.
Тип элементов множества называется базовым типом.
В качестве базовых типов могут использоваться любой тип за
исключением Real (символьный, байтовый, перечислимые типы)

3.

Конструктор множества
Значения множества задаются с помощью конструктора множества
Пример задания множеств с помощью конструктора:
[ 3, 4, 7, 9, 12] – множество из пяти целых чисел;
[ 1 . . 100 ] –множество целых чисел от 1 до 100;
[ ‘a’, ‘b’, ‘c’ ] – множество из трех символов a, b, c;
[ ‘ a ’ . . ‘ z ’ , ‘ ? ’ , ‘ ! ‘ ] – множество из всех
строчных
латинских букв, а также знаков ? и !.
Символ [] обозначает пустое множество, не содержащее
никаких элементов.

4.

Не имеет значения порядок записи элементов множества
внутри конструктора.
Например,
[ 1, 2, 3 ]и [ 3, 2, 1 ] – эквивалентные множества.
Каждый элемент множества учитывается только 1 раз.
Например,
[ 1, 2, 3, 4, 2, 3, 4, 5] и [1..5] эквивалентны.

5.

Пример описания переменных множественного типа:
Var <идентификатор> : Set Of <базовый тип>
Например:
A, D : Set Of Byte ;
B : Set Of ‘a’ . . ‘z’ ;
C : Set Of Boolean ;
Set (с англ. набор, множество, совокупность, ряд )

6.

Множественная переменная получает значение в результате
выполнения оператора присваивания следующего формата:
<множественная переменная> : = <множественное выражение>
Например:
А := [ 50, 100, 150, 200] ;
B := [ ‘ m ’, ‘ n ’, ‘ k ’] ;
C := [ True, False] ;
D := A;
Т.е. нельзя вводить значение в множественную переменную
оператором ввода и выводить оператором вывода.

7.

Операции над множествами
Пересечение: Те и только те элементы, которые принадлежат
одновременно А и В
Объединение: Те и только те элементы, которые принадлежат хотя
бы одному из множеств А и В
Разность:
Те и только те элементы множества А, которые НЕ
принадлежат В

8.

Пересечением двух множеств А и В называется множество,
состоящее из элементов , одновременно входящих и в множество А, и в
множество В.
Пример:
[ 1, 2, 3, 4] * [ 3, 4, 5, 6]
[ 3, 4 ]
Объединением двух множеств А и В называется множество,
состоящее из элементов , входящих хотя бы в одно из множеств А или В
Пример:
[ 1, 2, 3, 4] + [ 3, 4, 5, 6]
[ 1, 2, 3, 4, 5, 6]
Разностью двух множеств А и В называется множество, состоящее из
элементов множеств А, не входящих в множество В.
Пример:
[ 1, 2, 3, 4] - [ 3, 4, 5, 6]
[ 1, 2]

9.

Операции отношения над множествами
РЕЗУЛЬТАТ
Отношение
True
False
А=В
Мн. А и В совпадают
В противном случае
А<>B
Мн. А и В не совпадают
То же
A<=B
Все элементы А принадлежат В
A>=B
Все элементы В принадлежат А
»
»
Результат – логическая величина True или False

10.

Операции вхождения устанавливает связь между
множеством и величиной, тип которой совпадает с
базовым типом множества
Операция вхождения записывается в виде:
X In M
где М – множество;
Х - величина данного типа.

11.

Задача
Опишите множество М[1..25]. Сделайте его пустым. Заполните множество
целыми числами с клавиатуры 10 элементами.
program Vvod_Mno;
var
M : set of 1..25;
X, I : integer; { I – порядковый номер
элемента множества, Х – элемент
множества}
begin
M := []; {M - пустое множество}
for I:= 1 to 10 do
begin
Write('Введите ',I,' -й элемент множества ');
Readln(X);
M:= M+[X];
end;
Writeln (M);
end.
Ответ:
Введите 1 -й элемент множества 3
Введите 2 -й элемент множества 3
Введите 3 -й элемент множества 2
Введите 4 -й элемент множества 4
Введите 5 -й элемент множества 5
Полученное множество {5,4,3,2}

12.

program Mn;
var
d1, d2, d3, d : set
of 0..9;
begin
d1 := [2,4,6,8];
d2 := [0..3,5];
d3 := [1,3,5,7,9];
d := d1 + d2;
writeln(d);
d := d + d3;
writeln(d);
d := d - d2;
writeln(d);
d := d * d1;
writeln(d);
end.
Задача
Даны множества :
d1 - заполнено четными числами 2, 4, 6, 8;
d2 – заполнено числами 0, 1,2,3,5;
d3 – заполнено нечетными числами 1, 3, 5, 7, 9
После этого над множествами выполнены
операции объединения, разности и
пересечения
Ответ:
[8,6,5,4,3,2,1,0]
[9,8,7,6,5,4,3,2,1,0]
[6,4,9,8,7]
[6,4,8]

13.

Задача
Требуется написать программу, которая в зависимости
от числа (количества лет)добавляет правильное
окончание. (10 лет; 21 год; 32 года)
Алгоритм решения задачи:
Слово "год" добавляется ко всем числам, последняя (или
единственная) цифра которых равна 1.
"Года" для оканчивающихся на 2, 3, 4. Во всех остальных
случаях используется слово "лет".
Числа 11, 12, 13, 14 (или имеющие такой остаток от
деления на 100) имеют "окончание" лет.
Для того, чтобы определить, на какую цифру
заканчивается число, надо найти остаток от его деления
на 10.

14.

Задача
Program Mn_1;
var let, let11, god, goda: set of byte;
age, n: byte;
begin
let := [0,5,6,7,8,9];
let11 := [11,12,13,14];
god := [1]; //goda := [2,3,4];
write('Введите количество лет: ');
readln(age);
if (age in let11) or (age mod 100 in let11) then {переменная age имеет
вхождение во множество let11 или …..}
writeln(age, ' лет')
else begin
n := age mod 10;
if n in let then
writeln(age, ' лет')
else
if n in god then
writeln(age, ' год')
else
writeln(age, ' года ')
end; readln; end.

15.

Задача Mn_1. Дана символьная строка. Определите в ней количество знаков
препинания (. - , * : ! ?).
Program Mn_1;
var S: String;
i, k: Byte;
begin
readln (S);
k:=0;
for i:= 1 to Length (S) do
if S[i] in ['.', '-', ',', ';',':','!','?'] {если S [i] элемент строки имеет
вхождение во множество…}
then k := k+1;
writeln ('Число знаков препинания равно ', k,'.');
end.
Ответ:
Море - это солнце, счастье, здоровье! Правда?
Число знаков препинания равно 5.

16.

Задача
Дана строка. Сохранить в ней только первые вхождения символов,
удалив все остальные.
program Mn_;
var m : set of char;
s : string;
i : byte;
begin
write('Введите строку: ');
readln(s);
m :=[]; {множество пустое}
i := 1;
while i <= length(s) do
if s[i] in m then delete(s, i, 1)
else
begin
m:=m+[s[i]];
i := i + 1
end;
writeln(s);
end.
Ответ. Введите строку:
Основы алгоритмизации и
программирования
Основы алгритмзцпя