3.1.Свойства множеств
3.2.Операции над множествами
3.3.Описание записи (RECORD)
3.4.Оператор присоединения
3.5.Запись
с вариантами
Данные
одинакового простого типа (кроме
вещественного) могут объединяться в множество.
В общем виде тип множество описывается:
TYPE
<идентификатор
типа>= SET
OF
<тип
компонент>;
Тип компонент
множества (базовый тип) обычно интервальный
или перечисляемый. Значения переменной
типа множества изображаются перечислением
компонент, разделенных запятыми и
заключенных в квадратные скобки.
Например,
TYPE Interval=
5..10;
MN=Set of Interval;
VAR
PR: MN;
PR
может
принимать значения: [5,6,7,8,9,10], [5], [6],…, [5,6],
[5,7],…, [6,7,8],…, [ ], где [ ] - пустое множество, т.к.
оно не содержит выражения, указывающего
базовый тип. Оно совместимо со всеми типами
множеств.
В языке Турбо Паскаль на множества
накладываются следующие ограничения:
·
Число
элементов множества не должно превышать 256.
·
Элементами
множества могут быть только данные простых
типов (кроме вещественных).
·
Элементы,
входящие в состав множества должны быть
определены заранее.
·
Порядок
элементов множества произвольный.
1)
Если все элементы одного множества
совпадают с элементами другого множества,
то они (множества) считаются равными.
Множества [1..5] и [1,2,3,4,5] равны.
2)
Если все элементы одного множества
являются членами другого множества, то 1
множество включено во 2 множество.
[‘C’,’E’] включено в множество [‘A’..’Z’].
3)
Если нижнее граничное значение больше,
чем верхнее граничное значение, то
множество является пустым.
[5..1] – пустое множество, т.е.
эквивалентно [ ].
Переменным
типа множество присваивают результат
выражений над множествами с помощью
обычного знака присваивания.
3.2. Операции над множествами.
1)
* -
пересечение множеств (произведение).
Пусть
X=[1,2,3,4,7,9],
а Y=[1,2,3,10,5],
тогда при выполнении оператора
Z:
= X
* Y;
множество Z
содержит элементы, которые принадлежат как
множеству X,
так и множеству Y,
т.е. Z=[1,2,3].
2)
+ -
объединение множеств (сумма).
Пусть
X=[1,2,3,4,7,9],
а Y=[1,2,3,10,5],
тогда при выполнении оператора
Z:=
X
+ Y;
множество Z
содержит элементы, которые принадлежат
либо множеству X,
либо множеству Y,
т.е. Z=[1,2,3,4,5,7,9,10].
3)
- -
разность множеств или относительное
дополнение.
Пусть
X=[1,2,3,4,7,9],
а Y=[1,2,3,10,5],
тогда при выполнении оператора
Z:
= X
- Y;
множество Z
содержит элементы X,
которые не принадлежат множеству Y,
т.е. Z=[4,7,9].
4)
= -
проверка на равенство.
Если
все элементы множества X
являются элементами множества Y,
то результатом выполнения операции будет TRUE,
в противном случае – FALSE.
Пусть X=[1,2,3,4,7,9],
а Y=[1,2,3,10,5],
тогда при выполнении оператора
F:
= X
= Y;
F=
false.
5)
<> -
проверка на неравенство.
Если
какие-то элементы множества X
не являются элементами множества Y
или наоборот, то результатом выполнения
операции будет TRUE,
в противном случае – FALSE.
Пусть X=[1,2,3,4,7,9],
а Y=[1,2,3,10,5],
тогда при выполнении оператора
F:=X<>Y;
F=
true.
6)
>= -
проверка на включение.
Если
все элементы множества Y
являются элементами множества X,
то результатом выполнения операции будет TRUE,
в противном случае – FALSE.
Пусть X=[1,2,3,4,7,9],
а Y=[1,2,3],
тогда при выполнении оператора
F:
= X
>= Y;
F=
true.
7)
<= -
проверка на включение.
Если
все элементы множества X
являются элементами множества Y,
то результатом выполнения операции будет TRUE,
в противном случае – FALSE.
Пусть X=[1,2,3],
а Y=[1,2,3,10,5],
тогда при выполнении оператора
F:
= X
< = Y;
F=
true.
8)
IN
- проверка
принадлежности отдельного элемента
множеству.
Слева
от знака операции записывается выражение
того же типа, что и базовый, а справа –
множество. Если левый операнд является
элементом множества Y,
то результатом выполнения операции будет TRUE,
в противном случае – FALSE.
Пусть A=5,
а Y=[1,2,3,10,5],
тогда при выполнении оператора
F:
= A
IN
Y;
F=
true.
Отношения
> и < для множеств не определены.
Рассмотрим
некоторые примеры, в которых используются
операции над множествами.
Вводится
строка символов. Требуется составить
программу, распознающую является ли
введенная строка идентификатором.
var
sim:char;
fl:boolean;
s:string[127];
i,l:byte;
begin
readln(s);
l:=length(s);
sim:=s[1];
if not(sim in ['a'..'z']) then fl:=false else fl:=true;
i:=2;
while(i<=l) and fl do
begin
sim:=s[i];
if not (sim in ['a'..'z','0'..'9','_']) then fl:=false
else i:=i+1
end;
if fl then writeln('идентификатор')
else writeln('нет')
end.
Базовым
типом множества в данной программе
является тип CHAR.
Поэтому для
выполнения операции проверки
принадлежности элемента множеству в правой
части также требуется тип CHAR.
Для выделения символа из строки
используется индексирование, т.к. выделение
символа с помощью функции COPY
дает результат
типа STRING,
что недопустимо для множеств.
В
следующем примере требуется вывести на
экран все простые числа из интервала от 2 до
255.
USES CRT;
CONST N=255;
VAR
ISX, REZ: SET OF 2..N;
I,J: INTEGER;
BEGIN
CLRSCR;
REZ:=[];
ISX:=[2..N];
I:=2;
REPEAT
WHILE NOT(I IN ISX) DO
I:=SUCC(I);
REZ:=REZ+[I];
J:=I;
WHILE J<=N DO
BEGIN
ISX:=ISX-[J];
J:=J+I
END;
UNTIL ISX=[];
WRITELN;
FOR I:=1 TO 255 DO
IF I IN REZ THEN
READKEY
END.
В
основу программы положен алгоритм,
известный под названием «решето Эратосфена»,
т.е. метод отсеивания составных чисел, при
котором последовательно вычеркиваются
числа, делящиеся на 2, 3, 5 и т.д.; первое число,
остающееся после каждого этапа, является
простым и добавляется к результату.
Исходное множество в начале программы
содержит все натуральные числа от 2 до 255.
Результат также является множеством, к
которому последовательно добавляются
элементы. Условием окончания работы
является пустое множество, получившееся
вместо исходного.
В следующем примере вводится строка символов. Разделителями будем считать символы «;?,. <>”’». Назовем словом любую последовательность символов, ограниченную с одной или с двух сторон разделителями. Требуется удалить слова, состоящие не более, чем из 2 различных символов. Если таких слов нет, то выдать сообщение.
program
delwd;
uses crt;
const r:set of char= ['
',';',',','<','"','''','>','?','.'];
Var s,c:string;
i,ns:byte;
f:boolean;
begin
clrscr;
write('s='); readln(s);
i:=1; F:=TRUE;
while i<=length(s) do
begin
if
not(s[i] in r) then
begin
ns:=i;
c:=’’;
while (i<=length(s)) and not(s[i] in r) do
begin
if pos(s[i],c)=0 then c:=c+s[i];
inc(i);
end;
if length(c)<=2 then
begin
delete (s,ns,i-ns);
f:=false;
i:=ns-1
end;
end;
i:=i+1
end;
if f then writeln('no')
else writeln(s);
readkey
end.
Во
вспомогательную строку С выбираются
различные буквы во время прохода по слову.
Если длина этой строки оказывается меньше
или равна 2, слово нужно удалять. После
удаления необходимо скорректировать
позицию, на которой остановилась
переменная основного цикла на проход по
строке.
В следующем примере вводится строка символов. Требуется определить, содержит ли данная строка цифры и выдать сообщение об этом. Распечатать имеющиеся в строке цифры.
program
digit;
USes crt;
Var
cf:set of 0..9;
s:string;
i,k:byte;
begin
clrscr;
write('s='); readln(s);
cf:=[];
i:=1;
while i<=length(s) do
begin
k:=ord(s[i])-ord('0');
if k in [0..9] then cf:=cf+[k];
i:=i+1
end;
if cf=[] then writeln('no')
else begin
for i:=0 to 9 do
if i in cf then write(i:3)
writeln
end;
readkey
ENd.
Так
как цифры имеет последовательные коды,
значение самой цифры можно определить,
вычитая из кода цифры код цифры 0, что и
выполняется в программе. Цифры,
обнаруженные в строке, записываются во
множество, которое затем выводится на экран.
3.3. Описание записи (RECORD).
В
общем виде описание типа для записи можно
представить:
TYPE
<идентификатор
типа>= RECORD
<идентификатор
11>[,<
идентификатор 12>,…]:
<тип 1>;
<
идентификатор 21>[,< идентификатор 22>,…]:
<тип 2>;
.
. .
END;
Например,
TYPE
TA= RECORD
P1 : REAL;
P2 : CHAR;
P3 : BYTE
END;
VAR A: ARRAY[1..10] OF TA;
Здесь
описан одномерный массив, каждый элемент
которого представляет собой
запись, имеющую структуру типа TA.
Запись
может объявляться и непосредственно в
разделе описания переменных.
VAR
C : RECORD
P1 : REAL;
P2 : CHAR;
P3 : BYTE
END;
Рассмотрим
пример. Дан массив записей со следующей
структурой:
-
шифр группы;
-
номер зачетной книжки;
-
код дисциплины;
-
оценка.
Требуется определить средний балл студентов группы ДС101. При вводе массива последняя запись имеет шифр группы «99999».
Program srball;
type
zap=record
shg:string[5];
nzk:integer;
kd:1..100;
oc:2..5
end;
var
mas:array[1..100] of zap;
k,n,i:byte;
sum:real;
begin
i:=0;
repeat
inc(i);
readln
(mas[i].shg, mas[i].nzk, mas[i].kd, mas[i].oc)
until mas[i].shg='99999';
n:=i; sum:=0; k:=0;
for i:=1 to n do
if mas[i].shg='ds101' then
begin
sum:=sum+mas[i].oc;
inc(k)
end;
if k<>0 then sum:=sum/k;
writeln
('Средний
балл в группе ДС-101=',sum)
End.
При обращении к компонентам записи
используются составные имена. Для
сокращения имен и повышения удобства
работы с записями применяется оператор
присоединения WITH.
WITH <идентификатор
переменной типа RECORD>
DO
< оператор >;
Тогда
в операторе при ссылке на компоненты записи
имя переменной можно опускать. При
использовании оператора присоединения
фрагмент рассмотренной ранее программы
будет выглядеть:
.
. .
i:=0;
repeat
inc(i);
WITH MAS[I] DO
readln(shg,nzk,kd,oc)
until mas[i].shg='99999';
n:=i; sum:=0; k:=0;
for i:=1 to n do
WITH MAS[I] DO
if shg='ds101' then
begin
sum:=sum+oc;
inc(k)
end;
.
. .
Возможны
вложенные описания записи и вложенные
конструкции WITH.
Рассмотрим
пример вложенных описаний. Пусть запись о
студентах содержит следующие поля:
-
номер по порядку;
-
фио (содержит в свою очередь поля –
фамилия, имя, отчество),
-
номер зачетной книжки;
-
дата рождения (содержит поля –год,
месяц, день).
Программа
ввода и подсчета введенных записей для
записей такой структуры может выглядеть
uses
crt;
type
zap=record
npp:byte;
fio:record
F,i,o:string[15];
end;
nzk:word;
dtr:record
g:1970..2000;
m:string[3];
d:1..31
end;
end;
var
a:zap;
k,n:byte;
Begin
clrscr;
k:=0;
with a do
with fio do
with dtr do
repeat
inc(k);
writeln('ввод
');
readln(npp);
readln(f);
readln(i);
readln(o);
readln(nzk);
readln(g);
readln(m);
readln(d);
until d=99;
writeln(k);
readkey
End.
Состав и структура записи могут
динамически меняться в зависимости от
значения какого-либо из своих полей,
называемого полем-признаком. В
общем виде описание записи с вариантами
выглядит так:
TYPE
<идентификатор
типа >= RECORD
<идентификатор
поля 1>:<тип 1>;
<идентификатор
поля 2>:<тип 2>;
. . .
CASE
<селектор>:<тип
селектора> OF
<метка
варианта 1>:(<поле
варианта 11>:<тип 11>
[;<поле
варианта 12>:<тип 12>;<поле
варианта 13>:<тип 13>;. . .]);
<метка
варианта 2>:(<поле
варианта 21>:<тип 21>
[;<поле
варианта 22>:<тип 22>;<поле
варианта 23>:<тип 23>;. . .]);
<метка
варианта k>:(<поле
варианта k1>:<тип
k1>
[;<поле
варианта k2>:<тип
k2>;<поле варианта k3>:<тип k3>;.
. .]);
. . .
<метка
варианта m>:( )
END;
В
этом описании вариантная часть
записывается после постоянной части, к
которой относятся поля 1, 2 . . . , и может быть
только одна в записи. Метки варианта должны
иметь такой же тип, как у селектора. Если
какой-либо метке варианта не соответствуют
поля, то записываются пустые круглые скобки,
как у метки варианта m.
Пусть требуется описать запись
следующей структуры. В каждой записи
имеются поля, содержащие табельный номер и
фамилию. В зависимости от того, кому
принадлежит запись, состав остальных полей
может быть разным:
-
для
студентов поля: номер группы и
специальность;
-
для
преподавателей: институт, кафедра, стаж
работы;
-
для
сотрудников дополнительных полей нет.
Описание
соответствующей записи структуры:
type
tz=record
tn:byte;
fio:string;
case n:char of
‘p’: ( in:byte; kaf:string; st:byte );
‘s’: ( ng:byte; sp:integer );
‘a’: ( )
end;
var
Z:tz;