Множества
В отличие от операций + и -, реализующих аналогичные действия над двумя множествами, процедуры оптимизированы для работы с одиночными элементами множеcтва и поэтому отличаются высокой скоростью выполнения.
В примере 4.1, иллюстрирующем приемы работы с множествами, реализуется алгоритм выделения из первой сотни натуральных чисел всех простых чисел. В его основе лежит прием, известный под названием "решето Эратосфена". В соответствии с этим алгоритмом вначале формируется множество BEGINSET, состоящее из всех целых чисел в диапазоне от 2 до N. В множество PRIMERSET (оно будет содержать искомые простые числа) помещается 1. Затем циклически повторяются следующие действия:
- взять из BEGINSET первое входящее в него число NEXT и поместить его в PRIMERSET;
- удалить из BEGINSET число NEXT и все другие числа, кратные ему, т.е.2*NEXT, 3*NEXT и т.д.
Цикл повторяется до тех пор, пока множество BEGINSET не станет пустым.
Эту программу нельзя использовать для произвольного N, так как в любом множестве не может быть больше 256 элементов.
Пример 4.1.
Program Primer_numbers_detect;
{Выделение всех простых чисел из первых N целых}
const
N = 255; {Количество элементов исходного множества}
type
SetOfNumber = set of 1..N;
var
n1,next,i: Word; {Вспомогательные переменные}
BeginSet, {Исходное множество}
PrimerSet: SetOfNumber; {Множество простых чисел}.
begin
BeginSet: = [2..N]; {Создаем исходное множество}
PrimerSet: = [1]; {Первое простое число}
next: = 2; {Следующее простое число}
while BeginSet <> [] do {Начало основного цикла}
begin
n1: = next; {n1-число,кратное очередному простому (next)}
{Цикл удаления из исходного множества непростых чисел:}
while n1 <= N do
begin
Exclude(BeginSet,nl);
n1: = n1+next {Следующее кратное}
end; {Конец цикла удаления}
Include(PrimerSet,next);
{Получаем следующее простое, которое есть первое невычеркнутое из исходного множества}
repeat
inc(next)
until (next in BeginSet) or (next > N)
end; {Конец основного цикла}
{Выводим результат:}
for i: = 1 to N do
if i in PrimerSet then Write(i:8);
WriteLn
END.
Перед тем как закончить рассмотрение множеств полезно провести небольшой эксперимент. Измените описание типа SETOFNUMBER следующим образом:
type SetOf Number = set of 1.. 1;
И еще раз запустите программу из предыдущего примера. На экран будет выведено:
1 3 5 7
Множества BeginSet и PrimerSet состоят теперь из одного элемента, а программа сумела поместить в них не менее семи! Секрет этого прост: внутреннее устройство множества таково, что каждому его элементу ставится в соответствие один двоичный разряд (один бит); если элемент включен во множество, соответствующий разряд имеет значение 1, в противном случае – 0. Минимальной единицей памяти является один байт, содержащий 8 бит. Компилятор выделил множествам по одному байту, в результате мощность каждого из них стала равна 8 элементов. Максимальная мощность множества – 256 элементов. Для таких множеств компилятор выделяет по 16 смежных байт.
И еще один эксперимент: измените диапазон базового типа на 1.256. Хотя мощность этого типа составляет 256 элементов, при попытке компиляции программы компилятор сообщит:
Error 23: Set base type out of range. (Ошибка 23: Базовый тип множества выходит за допустимые границы.)
Компилятор разрешает использовать в качестве базового типа целочисленный тип-диапазон с минимальной границей 0 и максимальной 255 или любой перечисляемый тип не более чем с 256 элементами (максимальная мощность перечисляемого типа – 5536 элементов).