Главная » Free Pascal » Множества Free Pascal

0

Если массив представляет собой упорядоченный набор однотипных данных, то множество — это не упорядоченный набор не повторяющихся объектов любой при- роды. Максимальное количество объектов, из которых может состоять множество, не должно превышать 255. Специфика любого множества заключается в том, что при его описании должен быть перечислен весь список значений, который может входить в состав множества. Способ такого перечисления может быть разным:

type

s16 = set of (0..9,’a’..’f’); var

a1: s16;

bukwa: set of (‘a’, ‘c’, ‘f’, ‘d’, ‘b’, ‘e’); cifra: set of 0..9;

В этом примере объявлен тип с именем s16, описывающий множество, в кото- рое могут входить числа (цифры от 0 до 9) и символы (малые буквы латинского алфавита от ‘a’ до ‘f’). В разделе переменных объявлена переменная с именем a1 типа s16. Пока что она представляет пустое множество, не содержащее ни одного элемента. Но в процессе работы программы в состав a1 может быть включена лю- бая комбинация из неповторяющихся данных, допустимых типом s16:

a1:=[5,1,’b’];

Комбинацию значений элементов множества, заключенную в квадратные скоб- ки, принято называть конструктором множества. Конструктор множества может быть и пустым, например, [].

Переменные bukwa и cifra, допустимые значения которых заданы явно, после объявления тоже пока пусты.

Над элементами конкретного множества определены операции сложения (до- бавления одного или нескольких элементов из допустимого набора), вычитания (удаления из текущего значения множества одного или нескольких элементов) и проверки присутствия в составе множества указанного значения (операция in, вы- дающая результат типа boolean):

a1 := a1 - [5,’b’];    {теперь a1=[1]}

a1 := a1 + [3];        {теперь a1=[1,3]}

if 5 in a1 then …    {это условие не выполнено}

Над двумя множествами A и B определены операции, принятые в математи- ке, — объединение (сумма множеств A+B), пересечение (общая часть множеств A*B) и вычитание (разность A-B, т. е. элементы A, не принадлежащие B). Содержимое двух множеств можно сравнивать, однако из шести возможных операций отноше- ния допустимы лишь четыре — проверка на равенство (if A = B then…), на не- равенство (if A <> B then…), на больше или равно (if A >= B then…), на меньше или равно (if A <= B then…).

Наиболее интересным для математиков примером использования множеств яв-

ляется программа построения таблицы простых чисел методом Эратосфена. Эра- тосфен Киренский (282—202 гг. до н. э.) — известный древнегреческий ученый. Для формирования таблицы простых чисел он взял длинный папирус и написал на нем все числа от 2 до 1000. Затем он с помощью шила проткнул каждое второе число после 2, т. е. исключил все остальные четные числа. Сохранив первое остав- шееся после 2 число 3, он проткнул каждое третье число, т. е. исключил числа, кратные 3. Мы надеемся, что как умный человек, Эратосфен дважды не прокалы- вал ранее проколотые числа (например, 6 кратно и 2, и 3). Затем после 5 было про- колото каждое пятое число и т. д. В конце концов, на папирусе остались простые числа, имеющие только два разных делителя — единицу и само себя. Описанный алгоритм известен в литературе под названием "решето  Эратосфена"  (от  англ. sieve — решето). В листингах 7.1 и 7.2 приводятся две программы — sieve_1 и sieve_2. Одна из них формирует множество простых чисел путем их накапливания, а вторая — путем вычеркивания составных чисел.

   Листинг 7 .1 .  Программа  sieve_1                                              

program sieve_1; const

maxN = 255; var

primes: set of 2..maxN;

i,j: integer; begin

primes:=[2..maxN]; for i:=2 to maxN do

if i in primes then begin

write(i:4);

for j:=1 to (maxN div i) do primes:=primes-[i*j];

end; readln;

end.

Результат работы программы sieve_1 приведен на рис. 7.1.

Рис. 7.1. Результаты работы программы sieve_1

   Листинг 7 .2 .  Программа  sieve_2                                              

program sieve_2; const

N=255;

var

Sieve : set of 2..N = [2..N]; Primes: set of 2..N;

Next: byte=2;

j: word; begin

repeat

while not(Next in Sieve) do Next:=Next+1;

Primes:=Primes+[Next]; j:=Next;

while j<=N do begin

Sieve:=Sieve-[j]; j:=j+Next;

end;

until Sieve=[]; for j:=2 to N do

if j in Primes then write(j:4); readln;

end.

Результаты работы программ sieve_1 и sieve_2 идентичны.

Источник: Кетков, Ю. Л., Свободное программное обеспечение. FREE PASCAL для студентов и школьников, Ю. Л. Кетков, А. Ю. Кетков. — СПб.: БХВ-Петербург, 2011. — 384 с.: ил. + CD-ROM — (ИиИКТ)

По теме:

  • Комментарии