В языках программирования существуют средства, позволяющие описывают множества. В этом контексте, множества — это структуры, включающие в себя однотипные элементы; при этом последние никак не упорядочены внутри этой структуры. Это наборы однотипных логически связанных друг с другом объектов. Характер связей между объектами лишь подразумевается программистом и никак не контролируется программой-обработчиком. Количество элементов, входящих в множество, может меняться в пределах от 0 до 256 (множество, не содержащее элементов, называется пустым). Именно непостоянством количества своих элементов множества отличаются от массивов и записей. Описание типа множества, в языке программирования Pascal, выполняется в соответствии с синтаксисом:
<имя типа>=set o f<базовый тип>
<базовый тип> является типом элементов множества и может представлять собой любой порядковый тип, кроме word, integer, longint. Это ограничение связано с тем, что количество элементов множества не должно превышать 256. Для константного задания значения множества используются квадратные скобки, внутри которых перечисляются в произвольном порядке значения отдельных элементов или диапазон значений нескольких элементов множества.
Например:
type
Tset=set of 1...10;
...
var
Vset: Tset;
...
begin
Vset:=[3,5...7,10]
...
IN проверка принадлежности; в этой бинарной операции первый элемент — выражение, а второй — множество одного и того же типа; возвращает TRUE , если выражение имеет значение, принадлежащее множеству:
3 in Vset возвращает TRUE;
2*2 in Vset возвращает FALSE.
Дополнительно к этим операциям можно использовать две процедуры.
INCLUDE — включает новый элемент во множество. Обращение к процедуре:
INCLUDE (S,I)
Здесь S — множество, I — элемент который необходимо включить во множество.
EXCLUDE — исключает элемент из множества. Обращение: EXCLUDE(S,I)
Например:
…
type
TVowels = set of Char;
var
Vowels: TVowels;
…
begin
Vowels := ['A','E','I','O','U'];
Writeln('Введите английскую гласную букву');
Readln(x);
if x in Vowels then writeln('Гласная') else writeln('Неправильный ввод');
end.
Примеры программ
Пусть Х- множество {1, 2, 3, 4}, а Y- множество {х: х = y+z; y,z X}. Определить в явном виде (списком) множество Y.
Составим программу решающую данную задачу:
рrogram spisok;
type
Un=set of 1..255; {определяем универсум}
var
A,Y:Un;
i,j,k: Integer;
begin
A:=[1,2,3,4];
for i:=1 to 255 do
If i in A then
For j:=1 to 255 do
If (j in A) and (j<>I) then
Begin
k:=i+j;
INCLUDE (Y,k); {включаем найденный элемент}
end;
for i:=1 to 255 do
If i in Y then writeln(i); {выводим на экран найденной множество в виде списка}
end.
Задать различными способами множество М всех чисел, являющихся степенями двойки: 2, 4, 8, 16,…, не превышающих 255?
Составим программу решающую данную задачу.
Program spisok2;
type
Un=set of 1..255;
var
M:Un;
x: Integer;
begin
x:=2;
while x<=255 do
Include (M,x);
x:=x*2;
end while;
for x:=1 to 255 do
If x in M then writeln(x);
end.
В современных языках программирования задать множество возможно и другими способами, например, такими как массив и строка.
Описание типа массива задается следующим образом:
<имя типа> = ARRAY [ <сп.инд.типов> ] OF <тип>
Здесь <имя типа> — правильный идентификатор;
ARRAY, OF — зарезервированные слова (массив, из);
<сп.инд.типов> — список из одного или нескольких индексных типов, разделенных запятыми; квадратные скобки, обрамляющие список, — требование синтаксиса;
<тип> — любой тип языка программирования.
В качестве индексных типов в Турбо Паскале можно использовать любые порядковые типы, кроме LONGINT и типов-диапазонов с базовым типом LONGINT.
Например:
var
а : array[1. .2,1. .2] of Byte;
begin
a [1,1]:=1;
a [2,1]:=2;
a [l, 2]:=3;
a [2,2]:=4;
end.
Тип STRING (строка) в Турбо Паскале широко используется для обработки текстов. Он во многом похож на одномерный массив символов ARRAY[O..N] OF CHAR, однако, в отличие от последнего, количество символов в строке-переменной может меняться от 0 до N, где N — максимальное количество символов в строке. Значение N определяется объявлением типа STRING [N] и может быть любой константой порядкового типа, но не больше 255. Турбо Паскаль разрешает не указывать N, в этом случае длина строки принимается максимально возможной, а именно N=255 .
Строка в Турбо Паскале трактуется как цепочка символов. К любому символу в строке можно обратиться точно так же, как к элементу одномерного массива ARRAY [0..N] OF CHAR, например:
var
st : String;
begin
.....
if st[5] = 'A' then...
end.
Самый первый байт в строке имеет индекс 0 и содержит текущую длину строки, первый значащий символ строки занимает второй байт и имеет индекс 1.
Создать программу, генерирующую множество простых чисел.
При работе с данным упражнением следует воспользоваться алгоритмом «решето Эратосфена» нахождения простых чисел, не превышающих заданное натуральное число. Основная идея алгоритма заключается в «просеивании» исходного множества, включающего в себя все натуральные числа, не превышающие заданное. В результате такого «просеивания» из исходного множества удаляются все имеющиеся в нем составные числа: сначала — кратные 2, затем — кратные 3 и т.д., на i-том шаге алгоритма из множества удаляются числа, кратные числу j, не удаленному ранее и следующему за простым k, кратность которому была признаком удаления чисел на (i-1)-ом шаге алгоритма.
Принцип алгоритма:
· Сформируем множество BEGINSET состоящее из всех целых чисел в диапазоне от 2 до n.
· В множество PRIMERSET (оно будет содержать искомые простые числа) помещается 1.
· Цикл до тех пор пока множество BEGINSET не станет пустым:
1. Взять из BEGINSET первое входящее в него число NEXT и поместить его в PRIMERSET;
2. Удалить из BEGINSET число NEXT и все другие числа кратные ему.
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.