|
Множества
Множества - это наборы
однотипных логически связанных друг с другом объектов.
Характер связей между объектами лишь подразумевается
программистом и никак не контролируется Турбо Паскалем.
Количество элементов, входящих в множество, может меняться
в пределах от 0 до 256 (множество, не содержащее элементов,
называется пустым). Именно непостоянством количества
своих элементов множества отличаются от массивов и записей.
Два множества считаются эквивалентными тогда и только
тогда, когда все их элементы одинаковы, причем порядок
следования элементов в множестве безразличен. Если все
элементы одного множества входят также и в другое, говорят
о включении первого множества во второе. Пустое множество
включается в любое другое.
Пример определения и задания множеств:
type
digitChar= set of '0'..'9';
digit = set of 0. .9;
var
sl,s2,s3 :digitChar;
s4,s5,s6 :digit;
begin
.....
s1:=['1','2','3'];
s2:=['3','2','1'];
s3:=['2','3'];
s4:=[0..3,6];
s5:=[4,5];
s6:=[3..9];
.....
end.
В этом примере множества S1 и S2 эквивалентны, а множество
S3 включено в S2 , но не эквивалентно ему.
Описание типа множества имеет вид:
<имя типа> = SET OF <баз.тип>
Здесь <имя типа> - правильный идентификатор;
SET, OF - зарезервированные слова (множество, из);
<баз.тип> - базовый тип элементов множества,
в качестве которого может
использоваться любой порядковый тип, кроме WORD, INTEGER,
LONGINT.
Для задания множества используется так называемый конструктор
множества: список спецификаций элементов множества,
отделяемых друг от друга запятыми; список обрамляется
квадратными скобками (см. предыдущий пример). Спецификациями
элементов могут быть константы или выражения базового
типа, а также - тип-диапазон того же базового типа.
Над множествами определены следующие операции:
* пересечение множеств; результат содержит элементы,
общие для обоих множеств; например, 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 s6 возвращает TRUE;
2*2 in s1 возвращает FALSE.
Дополнительно к этим операциям можно использовать две
процедуры. INCLUDE - включает новый элемент во множество.
Обращение к процедуре:
INCLUDE (S,I)
Здесь S - множество, состоящее из элементов базового
типа TSetBase;
I - элемент типа TSetBase, который необходимо включить
во множество.
EXCLUDE - исключает элемент из множества. Обращение:
EXCLUDE(S,I)
Параметры обращения - такие же, как у процедуры INCLUDE.
В отличие от операций + и -, реализующих аналогичные
действия над двумя множествами, процедуры оптимизированы
для работы с одиночными элементами множе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 элементов).
|
