Множество в математике – это произвольный набор объектов, понимаемый как единое целое. Два множества, отличающиеся только порядком следования элементов, считаются одинаковыми, например:
{A, B, C}, {A, C, B}, {B, C, A}
и т.д., то есть элементы множества не упорядочены.
На вид объектов и их число не накладываются никакие ограничения, но в языке Турбо-Паскаль это понятие существенно уже: в качестве базовых типов допускаются дискретные типы не более чем с 256 различными значениями, то есть типы byte, char, boolean, перечисляемый и диапазон.
Описание типа:
Туре <тип_множество> = SET OF <базовый_тип>
Var <список_переменных>: SET OF <базовый_тип>
В качестве констант в этом типе используется изображение или конструктор множества, который строится из списка элементов, заключенных в квадратные скобки. В качестве элементов могут выступать и диапазоны, например:
[Blue, Yellow, Red] или [1,4..8,12,15].
Существует единственное пустое множество, которое принадлежит всем типам множеств и обозначается как [ ].
Пусть есть описание:
Var A, B, C: Set of 0..9;
D, E: Set of '0'..'9';
F, G: Set of Boolean;
Тогда:
A:=[1, 3, 5];
D:=['3', '6'..'9'];
F:=[5, 7]; {неверная строка – «не то» множество}
При использовании диапазонов, если значение первой константы меньше значения второй константы диапазона, то задается пустое множество. Запись [5..3] эквивалентна [ ].
Операции над множествами – обычные из теории множеств и математической логики. Пусть S1 и S2 – однотипные множества, тогда над ними можно выполнять следующие операции.
1. Объединение множеств.
S1+S2 содержит элементы, которые принадлежат либо S1, либо S2, либо и тому и другому:
A:=[1, 2, 3];
B:=[1, 5, 9];
C:=A+B;
что эквивалентно
C:=[1, 2, 3, 5, 9];
2. Пересечение множеств.
S1*S2 содержит элементы, которые принадлежат как S1, так и S2:
A:=[1, 2, 3];
B:=[1, 5, 9];
C:=A*B;
что эквивалентно
C:=[1];
Или выражение
C:=A*[8];
соответствует пустому множеству:
C:=[ ];
3. Относительное дополнение или разность множеств.
S1-S2 содержит элементы из S1, которые не принадлежат S2:
A:=[1, 2, 3];
B:=[1, 5, 9];
C:=A-B;
что эквивалентно
C:=[2, 3];
Или выражение
C:=A-[3..9];
соответствует:
C:=[1, 2 ];
4. Проверка на равенство, неравенство и включение множеств.
S1=S2 тогда и только тогда, когда S1 и S2 содержат одни и те же элементы. В противном случае истинно выражение S1<>S2. S1<=S2 принимает истинное значение, когда все элементы S1 являются элементами S2 (множество S2 включает в себя множество S1). Пусть
A:=[1..5];
B:=[1..5];
C:=[1..6];
Тогда логические выражения примут значения:
A=B — истинно;
А=С — ложно;
B<>C — истинно;
A<=C — истинно (С включает А).
5. Проверка принадлежности множеству (включение во множество).
Эта логическая операция обозначается служебным словом in. Выражение X in S1 истинно, если элемент Х принадлежит множеству S1 и ложно в противном случае:
2 in A — истинно;
9 in A — ложно.
Этот тип данных используется довольно редко, за исключением операции проверки принадлежности к множеству. Например, нажата ли клавиша «p» в любом регистре и алфавите:
If CH in ['p', 'P', 'з', 'З'] then ... {нажата клавиша «р»}
Пример использования множеств
В качестве примера используется программа вычисления нескольких первых простых чисел методом «решета Эратосфена», выполняемого по следующему алгоритму.
1. Поместим все числа между 2 и n в «решето».
2. Выберем и вынем из «решета» наименьшее из оставшихся в нем чисел.
3. Поместим это число среди «простых» чисел.
4. Переберем и вынем из решета все числа, кратные данному.
5. Если решето не пустое, повторим шаги 2-5.
Program Eratosfen;
Const N=255; { Максимально возможное значение }
Var
R, { исходное решето }
Pr { решето с простыми числами - итог }
: Set of 2..N;
i, { счетчик чисел }
j { очередное простое число }
: integer;
Begin
R:=[2..N];
Pr:=[]; { пока в решете с простыми числами ничего нет}
j:=2; { первое простое число }
{ цикл по шагам 2-5}
Repeat
{ поиск очередного простого числа
(первый раз не выполняется ни разу) }
While not (j in R) do
j:=j+1;
Pr:=Pr+[j]; { включение в итог – шаг 3}
i:=j;
Writeln(j:8);
While i<=N do
Begin
R:=R-[i]; { вынимание из решета – шаг 4}
i:=i+j
end;
Until R=[ ]; { повторяем, если решето не пустое }
end.
Файлы
Любой язык программирования высокого уровня должен содержать средства для организации хранения информации на внешних запоминающих устройствах и доступа к этой информации. Особенность этих средств заключается в существенно разных способах организации работы на различных вычислительных системах. Поэтому обычно в языках высокого уровня описываются только базовые понятия, а подробности работы детализируются в конкретных версиях языка.
В стандартном Паскале под файлом подразумевается заранее не определенное количество компонентов одинакового типа с общим именем. Порядок компонентов определяется самой последовательностью. Это – основное отличие файлов от предыдущих структур данных.
В любой момент времени доступен только один компонент файла, доступ же к другим производится последовательным продвижением по файлу. То, как выбираются компоненты, зависит от организации внешнего устройства, свойств операционной системы, и некоторых других причин, однако считается, что только некоторые компоненты присутствуют в оперативной памяти в определенный момент времени, причем только компонент, на который указывает буферная переменная, доступен непосредственно.
Таким образом, с каждым описанием новой файловой переменной (непосредственно файла) автоматически вводится дополнительная скрытая переменная с таким же типом, как тип компонент, называемая буферной переменной файла или текущим указателем файла.
Описание файловой переменной производится следующим образом.
TYPE <имя> = FILE OF <тип_компонент>
VAR <список_имен>: FILE OF <тип_компонент>
Имя файловой переменной назначается независимо от имен файлов, используемых операционной системой, по правилу образования имен Паскаля. Компоненты могут быть любого типа, кроме файлового, или комбинированного типа, если одним из его полей является файл. Например:
Var Fil: File of real;
Авторский вариант языка содержит минимальный набор допустимых действий с файлами, который лишь частично совпадает с операциями, реализованными в Турбо Паскале. Здесь, в частности, отсутствуют явные операции над буферной переменной (в этом пункте есть несовместимость стандартного и Турбо-Паскаля). Все операции с файлами реализованы в виде процедур и функций, что является общепринятым подходом в большинстве языков программирования.
Все операции с файлами можно условно разбить на 4 группы.
