МНОЖЕСТВА
Множества – это наборы однотипных логически связанных друг с другом объектов. Характер связей между объектами лишь подразумевается программистом и никак не контролируется Турбо Паскаль. Количество элементов, входящих в множество, может меняться в пределах от 0 до 255 (множество не содержащее элементов называется пустым).
Именно непостоянством количества своих элементов множества отличаются от массивов и записей.
Два множества считаются эквивалентными тогда, и только тогда, когда все их элементы одинаковы, причем порядок следования элементов множества безразличен. Если все элементы одного множества входят также и в другое, говорят о включении первого множества во второе. Пустое множество включается в любое другое.
Пример:
Определение и задание множеств:
type
digitChar=set of '0'…'9';
digit=set of 0…9;
var
s1, s2, s3: digit Char;
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];
S4*S5 содержит [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 – множество, I – элемент);
EXCLUDE – исключает элемент из множества
(Exclude(S,I), где S – множество, I – элемент).
В отличие от операций «+» и «-», реализующих аналогичные действия над двумя множествами, процедуры оптимизированы для работы с одиночными элементами множества и поэтому отличаются высокой скоростью быстродействия.
Пример:
Разработать программу выделения из первой сотни натуральных чисел всех простых чисел.
В основе программы лежит прием, известный под названием «решето Эратосфена». Суть программы состоит в следующем. Сначала формируется множество BEGINSET, состоящее из всех целых чисел в диапазоне от 2 до N. в множество PRIMERSET (оно будет содержать искомые простые числа) помещается 1. Затем циклически повторяются следующие действия.
- взять из BEGINSET первое входящее в него число NEXT и поместить его в PRIMERSET;
- удалить из BEGINSET число NEXT и все другие числа, кратные ему, т.е. 2*NEXT, 3*NEXT и т.д.
Цикл повторяется до тех пор, пока множество BEGINSET не станет пустым.
Эту программу нельзя использовать для произвольного N, т.к. в любом множестве не может быть больше 256 элементов.
Program PrimerNumberDetect;
{Выделение всех простых чисел из первых N целых}
Const
N=255; {Количество элементов исходного множества}
Type
SetOfNumber =set of 1…N;
Var
N1, next, i: word;{Вспомогательные переменные}
BeginSet;{Исходное множество}
Primer Set: SetOfNumber;{Множество простых чисел}
Begin
BeginSet:= [2…N];{Создаем исходное множество}
Primer Set:= [1];{Первое простое число}
Next:= 2;{Следующее простое число}
While Begin Set < >[]do
begin
n1:=next; {n1-число, кратное очередному простому (next)}
{Цикл удаления из исходного множества непростых чисел}
while n1<=N do
begin
Exlude(beginSet, n1);
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.
10. ТИПИЗИРОВАННЫЕ КОНСТАНТЫ
В Турбо Паскаль допускается использование типизированных констант. Они задаются в разделе объявления констант следующим образом:
<идентификатор>: <тип> = <значение>
Здесь<идентификатор> – идентификатор константы,
<тип> – тип константы,
<значение> – значение константы.
Типизированным константам можно присваивать другие значения в ходе выполнения программы, поэтому фактически они представляют собой переменные с начальными значениями. Типизированная константа приобретает указанное в ее объявлении значение, то есть инициируется только один раз – к моменту начала программы. При повторном входе в блок (процедуру или функцию), в котором она объявлена, инициализации типизированной константы не производится и она сохраняет то значение, которое имела к моменту выхода из блока.
Типизированные константы могут быть любого типа, кроме файлов. Нельзя также объявить типизированную константу-запись, если хотя бы одно из ее полей является полем файлового типа.
Поскольку типизированная константа фактически не отличается от переменной, ее нельзя использовать в качестве значения при объявлении других констант или границ диапазона.