Лабораторная работа №11.
Тема: Обработка множеств.
Цель: Развить навыки обработки одномерных и двумерных массивов. Уметь использовать различные методы описания массивов и сортировки массивов.
Оборудование и материалы: Методическое пособие, ПЭВМ, ручка, карандаш, линейка, ластик, шаблон А4.
Ход работы
Методические рекомендации.
Необходимая информация содержится в лекции № 12.
Решение задач представить в следующем порядке: постановка задачи, построение математической модели, блок-схемы, программный код, тестирование.
Задание для лабораторной работы выбрать согласно варианту по приведённой таблице. Вариант определяется порядковым номером в журнале группы.
Образцы решения типовых задач.
Под множеством в языке Паскаль понимают ограниченный неупорядоченный набор различных элементов одинакового типа, логически связанных друг с другом. Количество элементов, входящих в множество, может изменяться (в пределах от 0 до 255). Множество, не содержащее элементов, называется пустым. Множество имеет имя. Тип элементов, входящих в множество, называется базовым. В качестве базового типа можно использовать любой порядковый тип, кроме Word, Integer, Longint. Множества должны быть объявлены либо в разделе Var, либо в разделах Type и Var, одновременно:
|
|
Var Имя множества: Set of базовый тип;
или
Type Имя типа= Set of базовый тип;
Var Имя множества:Имя типа;
Например:
Type
TM=Set of 1..100;
TS=Set of 'a'..'z';
Var Mch:TM; {Множество целых чисел от 1 до 100}
MSym:TS; {Множество строчных латинских букв}
M: Set of 1..10; {Множество целых чисел от 1 до 10}
Значения переменных множества задаются в разделе операторов с
помощью конструктора множества, который представляет собой список
элементов базового типа, заключенный в квадратные скобки.
Например:
Var M1,M2,M3:set of 1..99;
Begin...
M1:=[]; { Множество пустое}
M2:=[1,3,5,7,9]; { Множество нечетных чисел в первом десятке}
M3:=[2,4,6,8]; { Множество четных чисел в первом десятке}
...
End.
В качестве элементов в изображении множеств допускается использовать константы и выражения, тип которых совместим с базовым типом.
Типизированная константа - множество задается в виде правильного конструктора множества, например:
Type
Type_month=(Jn,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec);
TDays=Set of 1..31;
Tmonth=Set of 1..12;
Tsym=Set of 'A'..'Z';
Tmno=Set of Type_month;
Const
SymMno:Tsym=['A','E','I','O','U']; {подмножество гласных букв}
DaysMno:TDays=[1,8,15,22,29]; {подмножество выходных дней месяца}
Spring_Mes:Tmonth=[3,4,5]; {подмножество весенних месяцев года}
Spring_Month:Tmno=[Mar,Apr,May]; {то же, что и предыдущее}
Над множествами определены следующие операции:
1) * - пересечение множеств: результат содержит элементы, общие для обоих множеств. Например: пусть имеется описание:
|
|
Var S1,S2,S3,S4,S5:Set of 1..10;
Begin
S1:=[1,3,4,6];
S2:=[2,4,5,1];
S3:=S1*S2; - в S3 будет содержаться [1,4].
2) + - объединение множеств: результат содержит элементы первого множества, дополненные недостающими элементами из второго
множества:
S4:=S1+S2; - в S4 будет содержаться [1,3,4,6,2,5].
3) − - разность множеств: результат содержит элементы из первого множества, которые не принадлежат второму:
S5:=S1-S2; - в S5 будет содержаться [3,6].
4) = - проверка эквивалентности (или равенства): возвращает TRUE, если оба множества эквивалентны, т.е. содержат все одинаковые элементы.
5) <> - проверка неэквивалентности (или неравенства): возвращает TRUE, если оба множества неэквивалентны, т.е. содержат неодинаковые элементы.
6) <= - проверка вхождения: возвращает TRUE, если первое множество включено во второе (т.е. все элементы первого множества присутствуют также и во втором).
7) >= - проверка вхождения: возвращает TRUE, если второе множество включено в первое.
8) IN - проверка принадлежности элемента множеству. Эта операция возвращает результат TRUE, если элемент (или выражение), стоящий слева принадлежит множеству, указанному справа.
Дополнительно к этим операциям можно использовать две процедуры:
Include - включает новый элемент во множество: Include(M,elem); где М - множество элементов некоторого базового типа, а elem – элемент того же типа, который необходимо включить в множество М.
Exclude -исключает элемент из множества: Exclude(M,elem). В отличие от операций "+" и "-", реализующих аналогичные действия над двумя множествами, эти процедуры оптимизированы для работы с одиночными элементами множества и поэтому отличаются высокой скоростью выполнения.
Основным достоинством использования множеств является экономия памяти: внутреннее устройство множества таково, что каждому его элементу ставится в соответствие один двоичный разряд (один бит). Если элемент включен во множество, то соотвествующий разряд имеет значение 1, в противном случае - 0. Минимальной единицей памяти является 1 байт (8 бит), поэтому для хранения множества мощностью 256 элементов выделяется память 32 смежных байта.
Рассмотрим работу с множествами на следующем примере.
Из множества целых чисел от 1 до 20 выделить:
1) множество чисел, делящихся на 2 и 3 одновременно;
2) множество чисел, делящихся на 2 или на 3.
Первая задача соответствует нахождению пересечения множеств чисел, одно из которых содержит числа, делящиеся на 2, а другое на 3. Вторая - объединению этих двух множеств.
Обозначим множество чисел, делящихся на 2 через М2; множество чисел, делящихся на 3 через М3; множество чисел, делящихся на 2 и 3 через М2and3; множество чисел, делящихся на 2 или 3 через М2or3.
Текст программы
Type TM=Set of 1..20; {Описание типа множества целых чисел от 1 до 20}
Var M2,M3,M2and3,M2or3:TM; {Описание множеств}
k:1..20; {Описание переменной}
Begin
M2:=[]; M3:=[]; {Пустые множества}
for k:=1 to 20 do
Begin
if k mod 2 = 0 then Include(M2,k); {Включение элемента делящегося на 2 в множество М2}
if k mod 3 = 0 then Include(M3,k); { Включение элемента делящегося на 3 в множество М3}
end;
M2and3:=M2*M3; {Пересечение двух множеств}
M2or3:=M2+M3; {Объединение двух множеств}
write (' На 2 и 3 делятся числа: ');
for k:=1 to 20 do { Цикл для опеределения элементов в множестве}
if k in M2and3 thenwrite (k:3); { вывод элементов делящихся на 6} writeln;
write (' На 2 или 3 делятся числа: ');
for k:=1 to 20 do
if k in M2or3 then write (k:3); readln; {Остановка для просмотра}
End.
Пример 1. Известен набор продуктов - хлеб, масло, сыр, молоко, имеющихся в ассортименте магазинов. В три магазина доставлены отдельные виды этих продуктов. Требуется построить множества A, B, C, которые содержат соответственно:
- продукты, имеющиеся одновременно во всех магазинах;
- продукты, имеющиеся по крайней мере в одном из магазинов;
- продукты, которых нет ни в одном из магазинов.
Program ASMAG;
Const N=3;
|
|
Type
product=(bread,butter,cheese,milk); {задается список объектов (продуктов), определяющий базовый тип PRODUCT}
assort = set of product; {на базовом типе PRODUCT определя-ется множественный тип
ASSORT}
magazin = array [1..N] of assort; {информация о наличии продуктов во всех магазинах задается как массив множеств}
Var
m1: magazin; x: product;
a,b,c, xm1: assort;
i,j,iw,m: integer;
Begin
for i:= 1 to N do {ввод исходной информации}
Begin
xm1:= [];
writeln (' введите номера продуктов',i: '-го магазина =');
repeat {в цикле REPEAT формируется множество XM1,
характеризующее наличие товаров в одном магазине.}
read (iw);
case iw of
1: x:= bread;
2: x:= butter;
3: x:= cheese;
4: x:= milk
end;
xm1:= xm1 + [x];
until eoln;
m1[i]:= xm; {информация о наличии товаров записывается в массив M1}
end;
for i:= 1 to 3 do {формирование множеств A,B,C и их распечатка}
Begin
case i of
1: writeln ('продукты, имеющиеся одновременно во
всех магазинах');
2: writeln ('ассортимент продуктов');
3: writeln ('продукты, которых нет ни в одном магазине')
end;
for x:= bread to milk do
if x IN a the n
case x of
bread: write ('хлеб');
butter: write ('масло');
cheese: write ('сыр');
milk: write ('молоко')
end;
if i = 1 then
a:= b
Else
a:=c;
writeln;
end;
End.