Что такое множества?
Два множества считаются эквивалентными тогда и только тогда, когда все их элементы одинаковы, причем порядок следования элементов в множестве безразличен. Если все элементы одного множества входят также и в другое, говорят о включении первого множества во второе. Пустое множество включается в любое другое.
Пример определения и задания множеств:
type digitChar = set of '0'..'9'; digit = set of 0. .9; var sl,s2,s3 : digitChar; s4,s5,s6 : digit; begin si := ['1', '2', '3']; s2 := ['3', '2', '1']; s3 := ['2', '3']; s4 := [0..3, 6]; s5 := [4, 5]; s6 := [3..9]; end.
В этом примере множества si и s2 эквивалентны, а множество S3 включено в s 2 , но не эквивалентно ему.
Описание типа множества имеет вид:
<имя типа> = set of <базовый тип>;
Здесь <имя типа> - правильный идентификатор; set, of - зарезервированные слова (множество, из); <базовый тип> - базовый тип элементов множества, в качестве которого может использоваться любой порядковый тип, кроме Word, Integer, Longint, Int64.
Для задания множества используется так называемый конструктор множества: список спецификаций элементов множества, отделенных друг от друга запятыми; список обрамляется квадратными скобками. Спецификациями элементов могут быть константы или выражения базового типа, а также тип-диапазон того же базового типа.
Над множествами определены следующие операции:
* пересечение множеств; результат содержит элементы, общие для обоих множеств; например, s4*s6 содержит [3], s4*s5 -пустое множество (см. выше);
+ объединение множеств; результат содержит элементы первого множества, дополненные недостающими элементами из второго множества:
S4+S5 содержит [0,1,2,3,4,5,6];
S5+S6 содержит [3, 4, 5, 6, 7, 8, 9] ;
разность множеств; результат содержит элементы из первого множества, которые не принадлежат второму:
S6-S5 содержит [3,6,7,8,9];
S4-S5 содержит [0,1, 2, 3, 6] ;
= проверка эквивалентности; возвращает True, если оба множества эквивалентны;
<> проверка неэквивалентности; возвращает True, если оба множества неэквивалентны;
<= проверка вхождения; возвращает True, если первое множество включено во второе;
>= проверка вхождения; возвращает True, если второе множество включено в первое;
in проверка принадлежности; в этой бинарной операции первый элемент - выражение, а второй - множество одного и того же типа; возвращает True, если выражение имеет значение, принадлежащее множеству:
3 in s 6 возвращает True;
2*2 in si возвращает False.
Дополнительно к этим операциям можно использовать две процедуры.
include - включает новый элемент во множество. Обращение к процедуре:
Include(S,I)
Здесь s - множество, состоящее из элементов базового типа TSet Base; I - элемент типа TSetBase, который необходимо включить во множество.
exclude - исключает элемент из множества. Обращение:
Exclude(S,I)
Параметры обращения - такие же, как у процедуры include. В отличие от операций + и -, реализующих аналогичные действия над двумя множествами, процедуры оптимизированы для работы с одиночными элементами множества и поэтому отличаются высокой скоростью выполнения.
Учебная программа PRIMSET
В следующем примере, иллюстрирующем приемы работы с множествами, реализуется алгоритм выделения из первой сотни натуральных чисел всех простых чисел[ Простыми называются целые числа, которые не делятся без остатка на любые другие целые числа, кроме 1 и самого себя. К простым относятся 1, 2, 3, 5, 7, 11, 13 и т. д.. ]. В его основе лежит прием, известный под названием "решето Эратосфена". В соответствии с этим алгоритмом вначале формируется множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до N. В множество primerset (оно будет содержать искомые простые числа) помещается 1. Затем циклически повторяются следующие действия:
взять из BeginSet первое входящее в него число Next и поместить его В PrimerSet;
удалить из BeginSet число Next и все другие числа, кратные ему, Т. е. 2*Next, 3*Next И Т.Д.
Цикл повторяется до тех пор, пока множество BeginSet не станет пустым.
Эту программу нельзя использовать для произвольного N, так как в любом множестве не может быть больше 256 элементов.
procedure TfmExample.bbRunClick(Sender: TObject);
// Выделение всех простых чисел из первых N целых
const
N = 255; // Количество элементов исходного множества
type
SetOfNumber = set of 1..N;
var
n1,Next,i: Word; // Вспомогательные переменные
BeginSet, // Исходное множество
PrimerSet: SetOfNumber; // Множество простых чисел
S : String;
begin
BeginSet := [2..N];
// Создаем исходное множество
PrimerSet:= [1]; // Первое простое число
Next := 2; // Следующее простое число
while BeginSet о [ ] do // Начало основного цикла
begin
nl := Next; //nl-число, кратное очередному простому (Next)
// Цикл удаления из исходного множества непростых чисел:
while nl <= N do
begin
Exclude(BeginSet, nl);
n1 := nl + Next // Следующее кратное
end; // Конец цикла удаления
Include(PrimerSet, next);
// Получаем следующее простое, которое есть первое
// число, не вычеркнутое из исходного множества
repeat
inc(Next)
until (Next in BeginSet) or (Next > N)
end;
// Конец основного цикла
// Выводим результат:
S := '1';
for i := 2 to N do
if i in PrimerSet then
S := S+', '+IntToStr(i);
mmOutput.Lines.Add(S)
end;
Перед тем как закончить рассмотрение множеств, полезно провести небольшой эксперимент. Измените описание типа SetOfNumber следующим образом:
type SetOfNumber = set of 1..1;
и еще раз запустите программу из предыдущего примера. На экран будет выведено 1, 3, 5, 7
Множества BeginSet и PrimerSet состоят теперь из одного элемента, а программа сумела поместить в них не менее семи!
Секрет этого прост: внутреннее устройство множества таково, что каждому его элементу ставится в соответствие один двоичный разряд (один бит); если элемент включен во множество, соответствующий разряд имеет значение 1, в противном случае - 0. В то же время минимальной единицей памяти является один байт, содержащий 8 бит, поэтому компилятор выделил множествам по одному байту, и в результате мощность каждого из них стала равна 8 элементам. Максимальная мощность множества - 256 элементов. Для таких множеств компилятор выделяет по 16 смежных байт.
И еще один эксперимент: измените диапазон базового типа на 1..256. Хотя мощность этого типа составляет 256 элементов, при попытке компиляции программы компилятор сообщит об ошибке: Sets may have at most 256 elements (Множества могут иметь не более 256 элементов) т. к. нумерация элементов множества начинается с нуля независимо от объявленной в программе нижней границы. Компилятор разрешает использовать в качестве базового типа целочисленный тип-диапазон с минимальной границей 0 и максимальной 255 или любой перечисляемый тип не более чем с 256 элементами (максимальная мощность перечисляемого типа - 65536 элементов).