Структурированные типы - Программирование от RIN.RU

Множества

Множества - это наборы однотипных логически связанных друг с другом объектов. Характер связей между объектами лишь подразумевается программистом и никак не контролируется Object Pascal. Количество элементов, входящих в множество, может меняться в пределах от 0 до 256 (множество, не содержащее элементов, называется пустым). Именно непостоянством количества своих элементов множества отличаются от массивов и записей.

Два множества считаются эквивалентными тогда и только тогда, когда все их элементы одинаковы, причем порядок следования элементов в множестве безразличен. Если все элементы одного множества входят также и в другое, говорят о включении первого множества во второе. Пустое множество включается в любое другое.

Пример определения и задания множеств:

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.

Для задания множества используется так называемый конструктор множества: список спецификаций элементов множества, отделенных друг от друга запятыми; список обрамляется квадратными скобками. Спецификациями элементов могут быть константы или выражения базового типа, а также тип-диапазон того же базового типа.

Над множествами определены следующие операции:

Дополнительно к этим операциям можно использовать две процедуры.

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 не станет пустым.

Эту программу нельзя использовать для произвольного 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 элементов).