Классификация: нестандартный, структурированный (сложный) тип.

Тип множество

Классификация: нестандартный, структурированный (сложный) тип.

Имя определяет программист.

Множество - аналог множества в математике.

Структурная организация

По структуре - множество есть набор из фиксированного числа однотипных элементов (рис. 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.