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

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

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

Множество - аналог множества в математике.
3. Структурная организация
По структуре - множество есть набор из фиксированного числа однотипных элементов (рис. 20.1).. Для того, чтобы рассматривать дальнейшую работу с множествами имеет смысл представлять внутреннюю структуру множества. Все элементы поименованы значениями возможных элементов множества. Если в текущий момент времени элемент принадлежит множеству, то значение этого элемента во внутренней структуре 1, и значение 0 - если элемент в этот момент времени не принадлежит множеству.



Рис. 20.1. – Структура данного типа множество
О. Определение типа
Для того, чтобы определить тип множество необходимо перечислить все элементы, которые могут входить в множество. Есть ограничение на мощность множества - не более 256 элементов. Элементами множества могут быть только данные простого порядкового типа.

Правило определения типа множество на рис. 20.2. По правилам структурного программирования тип множество всегда определяется в разделе нестандартных типов.



Рис. 20.2. – Определение типа множество
1. Множество значений
Множество значений определяется набором признаков - принадлежат ли возможные элементы множеству или не принадлежат.

Значения множества задаются с помощью конструктора множества, определение которого приведено на рис. 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

1

0

0

0

1

1

1

Рис. 20.4. – Содержимое множества а
2. Множество операций 2.1 Множественные операции
Это бинарные операции. Операнды и результат одного типа множество. Эти операции являются аналогами теоретико-множественных операций:

объединение ;

пересечение ;

разность .

Геометрическая интерпретация этих операций приведена на рис. 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

1

0

1

0

1

1

1







kr

orn

gel

zel

gol

sini

fiol

b

1

0

0

1

0

0

1

Рис. 20.6. – Содержимое множеств а и b
2.1.1. Объединение множеств
Бинарная аддитивная операция со знаком +. Пример выполнения показан на рис. 20.7.




kr

orn

gel

zel

gol

sini

fiol

c:=a+b

1

0

1

1

1

1

1

Рис. 20.7. –Операция объединения множеств

2.1.2. Разность множеств
Бинарная аддитивная операция со знаком – (рис. 20.8).




kr

orn

gel

zel

gol

sini

fiol

c:=a-b

0

0

1

0

1

1

0

Рис. 20.8. –Операция разности множеств

2.1.3. Пересечение множеств
Бинарная мультипликативная операция со знаком * (рис. 20.9).




kr

orn

gel

zel

gol

sini

fiol

c:=a*b

1

0

0

0

0

0

1

Рис. 20.9. –Операция пересечения множеств
2.2 Операции сравнения 2.2.1 Сравнение множеств
Бинарные операции со знаками =|<>|>=|<= , операнды одного и того же множественного типа. Результат логического типа.

a=b ,значение TRUE, если множества полностью совпадают;

a<>b ,значение TRUE, если множества не совпадают;

a>=b ,значение TRUE, если b является подмножеством множества a;

a<=b ,значение TRUE, если a является подмножеством множества b.
2.2.2 Проверка на принадлежность к множеству
Бинарная операция сравнения со знаком IN . Первый операнд – элемент множества, второй операнд множество. Результат типа BOOLEAN - TRUE, если элемент принадлежит множеству, FALSE в противном случае.

Синтаксис операции: <элемент множества> in <множество>

Синтаксическое ограничение: тип первого операнда совпадает с типом компонента второго операнда.
2.3. Операция определения адреса
Унарная операция со знаком @. Операнд переменная множественного типа. Результат - указатель на участок оперативной памяти, в котором располагается переменная.
20.4. Задача обработки множеств Постановка задачи
Было куплено 2 коробки одинаковых цветных карандашей. Какое-то время ими пользовались. Определить карандаши какого цвета имеются в наличии, какого отсутствуют, какого имеются в двух экземплярах.

Каждую из коробок можно представить в виде множеств из цветов возможных карандашей. Тогда нам потребуется вычислить три множества:

множество наличных цветов карандашей (определяется как объединение двух исходных множеств);

множество отсутствующих карандашей (определяется как вычитание из множества всех возможных цветов множества наличных цветов);

множество дублирующих цветов карандашей (определяется как пересечение двух исходных множеств).
Структура программы


Рис. 20.10. - Структурная диаграмма программы

Выделим в поставленной задаче три подзадачи:

ввод с клавиатуры множества (содержимого коробки карандашей);

вывод на экран содержимого множества из карандашей;

вычисление множеств наличных, отсутствующих и дублирующих карандашей.

Структурная диаграмма программы представлена на рис. 20.10
Разработка подпрограммы ввода множества Спецификация
Назначение: ввод с клавиатуры значения множества, элементами которого являются названия цветных карандашей

Имя: read_mn

Вид: процедура

Перечень параметров:

Таблица 20.1. Перечень параметров

Статус

Назначение

Имя

Тип

Вид

Выход

Формируемое множество

n

tkorobka

параметр-переменная

type

{названия возможных цветов карандашей}

tpalitra = (krasn, gelt, zelen, sini, korichn, chern);

tkorobka = set of tpalitra;{тип информационной модели коробки карандашей}

Заголовок: procedure read_mn(var n:tkorobka);
Метод решения
Суть метода решения заключается в том, что к исходному пустому множеству последовательно добавляются возможные наличные элементы (объединение множеств)

n:=

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;
Разработка подпрограммы вывода множества Спецификация
Назначение: вывод на экран значения множества, элементами которого являются названия цветных карандашей

Имя: write_mn

Вид: процедура

Перечень параметров:

Таблица 20.3. Перечень параметров

Статус

Назначение

Имя

Тип

Вид

Вход

Выводимое множество

n

tkorobka

параметр-константа

type

{названия возможных цветов карандашей}

tpalitra = (krasn, gelt, zelen, sini, korichn, chern);

tkorobka = set of tpalitra;{тип информационной модели коробки карандашей}

Заголовок: 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;
Разработка подпрограммы resh Спецификация
1. Назначение: вычисление множеств наличных карандашей, отсутствующих карандашей, дублирующих карандашей (все множества типа tkorobka).

2. Имя: resh

3. Вид: процедура

4. Перечень параметров

Таблица 20.5. Перечень параметров

Статус

Назначение

Имя

Тип

Вид

Вход

Первая коробка

n1

tkorobka

параметр-константа

Вход

Вторая коробка

n2

tkorobka

параметр-константа

Выход

Наличные карандаши

nal

tkorobka

параметр-значение

Выход

Отсутствующие карандаши

otsut

tkorobka

параметр-значение

Выход

Дублирующие карандаши

dubl

tkorobka

параметр-значение
Метод решения
1) nal:=n1n2;

2) otsut:={ krasn, gelt, zelen, sini, korichn, chern } \ nal;

3) dubl:=n1n2.
Текст процедуры
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.