Классификация: нестандартный, структурированный (сложный) тип.
Тип множество
Классификация: нестандартный, структурированный (сложный) тип.
Имя определяет программист.
Множество - аналог множества в математике.
Структурная организация
По структуре - множество есть набор из фиксированного числа однотипных элементов (рис. 20.1).. Для того, чтобы рассматривать дальнейшую работу с множествами имеет смысл представлять внутреннюю структуру множества. Все элементы поименованы значениями возможных элементов множества. Если в текущий момент времени элемент принадлежит множеству, то значение этого элемента во внутренней структуре 1, и значение 0 - если элемент в этот момент времени не принадлежит множеству.
Рис. 20.1. –Структура данного типа множество
О. Определение типа
Для того, чтобы определить тип множество необходимо перечислить все элементы, которые могут входить в множество. Есть ограничение на мощность множества - не более 256 элементов. Элементами множества могут быть только данные простого порядкового типа.
Правило определения типа множество на рис. 20.2. По правилам структурного программирования тип множество всегда определяется в разделе нестандартных типов.
Рис. 20.2. –Определение типа множество
Множество значений
Множество значений определяется набором признаков - принадлежат ли возможные элементы множеству или не принадлежат.
Значения множества задаются с помощью конструктора множества, определение которого приведено на рис. 20.3.
Рис. 20.3. –Конструктор множества
Пример определения значений множества:
type raduga=(kr,orn,gel,zel,gol,sini,fiol);
sveta = set of raduga;
var a : cveta;
begin
a:=[kr,gol..fiol]
end.
После выполнения действий программы содержимое множества а будет таким:
| kr | orn | gel | zel | gol | sini | fiol |
Рис. 20.4. –Содержимое множества а
Множество операций
Множественные операции
Это бинарные операции. Операнды и результат одного типа множество. Эти операции являются аналогами теоретико-множественных операций:
- объединение 
;
- пересечение 
;
- разность 
.
Геометрическая интерпретация этих операций приведена на рис. 20.5.
Рис. 20.5. –Операции над множествами
Рассмотрим эти операции на примере:
type raduga=(kr,orn,gel,zel,gol,sini,fiol);
sveta = set of raduga;
var a,b,c: cveta;
a:=[kr,gol..fiol,gel];
b:=[fiol,kr,zel];
После выполнения операторов присваивания имеем:
| kr | orn | gel | zel | gol | sini | fiol | |
| a |
| kr | orn | gel | zel | gol | sini | fiol | |
| b |
Рис. 20.6. –Содержимое множеств а и b
Объединение множеств
Бинарная аддитивная операция со знаком +. Пример выполнения показан на рис. 20.7.
| kr | orn | gel | zel | gol | sini | fiol | |
| c:=a+b |
Рис. 20.7. –Операция объединения множеств
Разность множеств
Бинарная аддитивная операция со знаком – (рис. 20.8).
| kr | orn | gel | zel | gol | sini | fiol | |
| c:=a-b |
Рис. 20.8. –Операция разности множеств
Пересечение множеств
Бинарная мультипликативная операция со знаком * (рис. 20.9).
| kr | orn | gel | zel | gol | sini | fiol | |
| c:=a*b |
Рис. 20.9. –Операция пересечения множеств
Операции сравнения
Сравнение множеств
Бинарные операции со знаками =|<>|>=|<= , операнды одного и того же множественного типа. Результат логического типа.
a=b ,значение TRUE, если множества полностью совпадают;
a<>b ,значение TRUE, если множества не совпадают;
a>=b ,значение TRUE, если b является подмножеством множества a;
a<=b ,значение TRUE, если a является подмножеством множества b.
Задача обработки множеств
Постановка задачи
Было куплено 2 коробки одинаковых цветных карандашей. Какое-то время ими пользовались. Определить карандаши какого цвета имеются в наличии, какого отсутствуют, какого имеются в двух экземплярах.
Каждую из коробок можно представить в виде множеств из цветов возможных карандашей. Тогда нам потребуется вычислить три множества:
- множество наличных цветов карандашей (определяется как объединение двух исходных множеств);
- множество отсутствующих карандашей (определяется как вычитание из множества всех возможных цветов множества наличных цветов);
- множество дублирующих цветов карандашей (определяется как пересечение двух исходных множеств).
Структура программы
Рис. 20.10. - Структурная диаграмма программы
Выделим в поставленной задаче три подзадачи:
- ввод с клавиатуры множества (содержимого коробки карандашей);
- вывод на экран содержимого множества из карандашей;
- вычисление множеств наличных, отсутствующих и дублирующих карандашей.
Структурная диаграмма программы представлена на рис. 20.10
Спецификация
1. Назначение: ввод с клавиатуры значения множества, элементами которого являются названия цветных карандашей
2. Имя: read_mn
3. Вид: процедура
4. Перечень параметров:
Таблица 20.1. Перечень параметров
| Статус | Назначение | Имя | Тип | Вид |
| Выход | Формируемое множество | n | tkorobka | параметр-переменная |
type
{названия возможных цветов карандашей}
tpalitra = (krasn, gelt, zelen, sini, korichn, chern);
tkorobka = set of tpalitra;{тип информационной модели коробки карандашей}
5. Заголовок: procedure read_mn(var n:tkorobka);
Метод решения
Суть метода решения заключается в том, что к исходному пустому множеству последовательно добавляются возможные наличные элементы (объединение множеств)
1. n:= Æ
2. " i Î { krasn, gelt, zelen, sini, korichn, chern }:если otvet='включить i в множество'Þn:=nÈ{i}
Информационная модель
Таблица 20.2. Информационная модель
| Назначение | Имя | Тип |
| Очередной цвет | i | tpalitra |
| Ответ пользователя (да - включать/нет – не включать элемент) | otvet | char |
type tpalitra = (krasn, gelt, zelen, sini, korichn, chern);
В алгоритме используется глобальная константа – массив с названиями цветов карандашей
const colors:array[tpalitra]of string=('красный', 'желтый', 'зеленый', 'синий',
'коричневый', 'черный');
Программная модель
procedure read_mn(var n:tkorobka);
var i:tpalitra;
otvet:char;
begin
n:=[];{коробка пуста - пустое множество}
{перебор возможных цветов}
for i:=krasn to chern do
begin
writeln('Есть ',colors[i],' карандаш? Ответьте: д/н');
readln(otvet);
if (otvet='Д')or(otvet='д')or(upcase(otvet)='L') then
begin
n:=n+[i];{добавление элемента в множество}
writeln(colors[i],' карандаш находится в коробке')
end
else writeln(colors[i],' карандаш отсутствует в коробке')
end
end;
Спецификация
1. Назначение: вывод на экран значения множества, элементами которого являются названия цветных карандашей
2. Имя: write_mn
3. Вид: процедура
4. Перечень параметров:
Таблица 20.3. Перечень параметров
| Статус | Назначение | Имя | Тип | Вид |
| Вход | Выводимое множество | n | tkorobka | параметр-константа |
type
{названия возможных цветов карандашей}
tpalitra = (krasn, gelt, zelen, sini, korichn, chern);
tkorobka = set of tpalitra;{тип информационной модели коробки карандашей}
5. Заголовок: procedure write_mn(const n:tkorobka);
Метод решения
1. Обнулить счетчик выведенных элементов k:= 0
2. " i Î { krasn, gelt, zelen, sini, korichn, chern }:если i Î n Þ вывод (i)
k:=k+1
3. Если k=0 Þ вывод ('множество пусто')
Информационная модель
Таблица 20.4. Информационная модель
| Назначение | Имя | Тип |
| Очередной цвет | i | tpalitra |
| Количество выведенных значений | k | integer |
type tpalitra = (krasn, gelt, zelen, sini, korichn, chern);
В алгоритме используется глобальная константа – массив с названиями цветов карандашей const colors:array[tpalitra]of string=('красный','желтый','зеленый','синий',
'коричневый','черный');
Программная модель
procedure write_mn(const n:tkorobka);
var k:integer;
i:tpalitra;
begin
k:=0;
for i:=krasn to chern do
if i in n then
begin
if k<>0 then write(', ');
k:=k+1;
write(colors[i])
end;
if k=0 then writeln('нет карандашей')
else if k=1 then writeln(' карандаш')
else writeln(' карандаши')
end;
Спецификация
1. Назначение: вычисление множеств наличных карандашей, отсутствующих карандашей, дублирующих карандашей (все множества типа tkorobka).
2. Имя: resh
3. Вид: процедура
4. Перечень параметров
Таблица 20.5. Перечень параметров
| Статус | Назначение | Имя | Тип | Вид |
| Вход | Первая коробка | n1 | tkorobka | параметр-константа |
| Вход | Вторая коробка | n2 | tkorobka | параметр-константа |
| Выход | Наличные карандаши | nal | tkorobka | параметр-значение |
| Выход | Отсутствующие карандаши | otsut | tkorobka | параметр-значение |
| Выход | Дублирующие карандаши | dubl | tkorobka | параметр-значение |
Метод решения
1) nal:=n1 
n2;
2) otsut:={ krasn, gelt, zelen, sini, korichn, chern } \ nal;
3) dubl:=n1 
n2.
Текст процедуры
procedure resh(const n1,n2:tkorobka;var nal, otsut, dubl :tkorobka);
begin
{имеющиеся карандаши}
nal:=n1+n2; {объединение двух множеств - коробок}
{отсутствующие карандаши}
otsut:=[krasn..chern]-nal;
{вычитание из множества возможных цветов множества наличных цветов}
{дублирующие карандаши}
dubl:=n1*n2
end;
Разработка программы
Метод решения
1) read_mn(n1);
2) read_mn(n2);
3) resh(n1,n2,nal,otsut,dubl);
4) write_mn(nal);
5) write_mn(otsut);
6) write_mn(dubl).
Информационная модель
Таблица 20.6. Информационная модель
| Статус | Назначение | Имя | Тип |
| Вход | Первая коробка | n1 | tkorobka |
| Вход | Вторая коробка | n2 | tkorobka |
| Выход | Наличные карандаши | nal | tkorobka |
| Выход | Отсутствующие карандаши | otsut | tkorobka |
| Выход | Дублирующие карандаши | dubl | tkorobka |
Текст программы
program color_pencil;
type
{названия возможных цветов карандашей}
tpalitra = (krasn, gelt, zelen, sini, korichn, chern);
tkorobka = set of tpalitra;{тип информационной модели коробки карандашей}
const
{массив с символьными названиями цветов карандашей}
colors:array[tpalitra]of string=('красный','желтый','зеленый','синий','коричневый','черный');
procedure read_mn(var n:tkorobka);
var i:tpalitra;
otvet:char;
begin
n:=[];{коробка пуста - пустое множество}
{перебор возможных цветов}
for i:=krasn to chern do
begin
writeln('Есть ',colors[i],' карандаш? Ответьте: д/н');
readln(otvet);
if (otvet='Д')or(otvet='д')or(upcase(otvet)='L') then
begin
n:=n+[i];{добавление элемента в мнжество}
writeln(colors[i],' карандаш находится в коробке')
end
else writeln(colors[i],' карандаш отсутствует в коробке')
end
end;
procedure write_mn(const n:tkorobka);
var k:integer;
i:tpalitra;
begin
k:=0;
for i:=krasn to chern do
if i in n then
begin
if k<>0 then write(', ');
k:=k+1;
write(colors[i])
end;
if k=0 then writeln('нет карандашей')
else if k=1 then writeln(' карандаш')
else writeln(' карандаши')
end;
procedure resh(const n1,n2:tkorobka;var nal, otsut, dubl :tkorobka);
begin
{имеющиеся карандаши}
nal:=n1+n2; {объединение двух множеств - коробок}
{отсутствующие карандаши}
otsut:=[krasn..chern]-nal;
{вычитание из множества возможных цветов множества наличных цветов}
{дублирующие карандаши}
dubl:=n1*n2
end;
var n1,n2 : tkorobka; {коробки с карандашами}
nal,otsut,dubl:tkorobka; {результаты вычислений: наличие, отсутствие, дубль}
begin
writeln('заполнение первой коробки');
read_mn(n1);
writeln('заполнение второй коробки');
read_mn(n2);
resh(n1,n2,nal,otsut,dubl);
writeln('Имеющиеся:');
write_mn(nal);
writeln('Отсутствующие:');
write_mn(otsut);
writeln('Дублирующие:');
write_mn(dubl)
end.
Тип множество
Классификация: нестандартный, структурированный (сложный) тип.
Имя определяет программист.
Множество - аналог множества в математике.
Структурная организация
По структуре - множество есть набор из фиксированного числа однотипных элементов (рис. 20.1).. Для того, чтобы рассматривать дальнейшую работу с множествами имеет смысл представлять внутреннюю структуру множества. Все элементы поименованы значениями возможных элементов множества. Если в текущий момент времени элемент принадлежит множеству, то значение этого элемента во внутренней структуре 1, и значение 0 - если элемент в этот момент времени не принадлежит множеству.
Рис. 20.1. –Структура данного типа множество
О. Определение типа
Для того, чтобы определить тип множество необходимо перечислить все элементы, которые могут входить в множество. Есть ограничение на мощность множества - не более 256 элементов. Элементами множества могут быть только данные простого порядкового типа.
Правило определения типа множество на рис. 20.2. По правилам структурного программирования тип множество всегда определяется в разделе нестандартных типов.
Рис. 20.2. –Определение типа множество
Множество значений
Множество значений определяется набором признаков - принадлежат ли возможные элементы множеству или не принадлежат.
Значения множества задаются с помощью конструктора множества, определение которого приведено на рис. 20.3.
Рис. 20.3. –Конструктор множества
Пример определения значений множества:
type raduga=(kr,orn,gel,zel,gol,sini,fiol);
sveta = set of raduga;
var a : cveta;
begin
a:=[kr,gol..fiol]
end.
После выполнения действий программы содержимое множества а будет таким:
| kr | orn | gel | zel | gol | sini | fiol |
Рис. 20.4. –Содержимое множества а
Множество операций
Множественные операции
Это бинарные операции. Операнды и результат одного типа множество. Эти операции являются аналогами теоретико-множественных операций:
- объединение ;
- пересечение ;
- разность .
Геометрическая интерпретация этих операций приведена на рис. 20.5.
Рис. 20.5. –Операции над множествами
Рассмотрим эти операции на примере:
type raduga=(kr,orn,gel,zel,gol,sini,fiol);
sveta = set of raduga;
var a,b,c: cveta;
a:=[kr,gol..fiol,gel];
b:=[fiol,kr,zel];
После выполнения операторов присваивания имеем:
| kr | orn | gel | zel | gol | sini | fiol | |
| a |
| kr | orn | gel | zel | gol | sini | fiol | |
| b |
Рис. 20.6. –Содержимое множеств а и b
Объединение множеств
Бинарная аддитивная операция со знаком +. Пример выполнения показан на рис. 20.7.
| kr | orn | gel | zel | gol | sini | fiol | |
| c:=a+b |
Рис. 20.7. –Операция объединения множеств
Разность множеств
Бинарная аддитивная операция со знаком – (рис. 20.8).
| kr | orn | gel | zel | gol | sini | fiol | |
| c:=a-b |
Рис. 20.8. –Операция разности множеств
Пересечение множеств
Бинарная мультипликативная операция со знаком * (рис. 20.9).
| kr | orn | gel | zel | gol | sini | fiol | |
| c:=a*b |
Рис. 20.9. –Операция пересечения множеств
Операции сравнения
Сравнение множеств
Бинарные операции со знаками =|<>|>=|<= , операнды одного и того же множественного типа. Результат логического типа.
a=b ,значение TRUE, если множества полностью совпадают;
a<>b ,значение TRUE, если множества не совпадают;
a>=b ,значение TRUE, если b является подмножеством множества a;
a<=b ,значение TRUE, если a является подмножеством множества b.