Название: Алгоритмы и программы (Афанасьева Т. В.)

Жанр: Информационные системы и технологии

Просмотров: 1327


6. работа со множествами

 

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

Два множества называются эквивалентными тогда и только тогда,

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

Объявление типа множества имеет вид:

< имя типа > = set of < базовый тип >

Здесь < имя типа > – правильный идентификатор;

set , of – зарезервированные слова (множество, из);

<базовый тип> – базовый тип элементов множества, в качестве которого  может  использоваться  любой  порядковый  тип,  кроме  word, integer, longint.

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

Спецификациями элементов могут быть константы или выражения

базового типа, а также – тип-диапазон того же базового типа.

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

* – пересечение множеств; результат содержит элементы общие для обоих множеств;

+ – объединение множеств; результат содержит элементы первого множества,  дополненные  недостающими  элементами  из  второго множества;

– – разность множеств; результат содержит элементы из первого множества, которые не принадлежат второму множеству;

=  –  проверка эквивалентности; возвращает TRUE, если  оба множества эквивалентны;

<> – проверка неэквивалентности; возвращает TRUE, если оба множества неэквивалентны;

<= – проверка вхождения; возвращает TRUE, если первое множество включено во второе;

>= – проверка вхождения; возвращает TRUE, если второе множество включено в первое;

IN – проверка принадлежности; в этой бинарной операции первый элемент  –  выражение,  а  второй  –  множество  одного  и  того  же  типа;

возвращает     TRUE, если    выражение     имеет  значение,        принадлежащее множеству.

 

Пример           6.1.      Составить      программу,     реализующую нахождение пересечения множеств [5..25], [17..34], [1..20].

program mnog1;

var

a:set of 5..25;   {объявление множеств}

b:set of 17..34; c:set of 1..20; d:set of byte; n:byte;

begin a:=[5..25]; b:=[17..34];

c:=[1..20];        {Задание множеств}

d:=a*b*c;         {Нахождение пересечений множеств}

writeln(' Пересечением является множество:');

for n:=1 to 34 do

if n in d then write(n:3); {Вывод множества}

end.

 

Пример 6.2. Составить программу-определитель, какое из множеств

[C..N], [J..P], [M..Z] содержит наибольшее количество элементов. program mnog2;

var

a,b,c:set of 'A'..'Z';        {объявление множеств а,b,c}

m:char;

ka,kb,kc:integer;           {Количество элементов в множествах}

begin a:=['C'..'N'];

b:=['J'..'P'];       {Создание множеств}

c:=['M'..'Z'];

for m:='C' to 'N' do ka:=ka+1;

for m:='J' to 'P' do kb:=kb+1;{Определение числа элементов в множествах}

for m:='M' to 'Z' do kc:=kc+1;

{Нахождение максимального количества элементов множества.

Вывод результата}

if (ka>=kb) and (ka>=kc) then writeln('Множество [C..N] ')

else

if (kb>=ka) and (kb>=kc) then writeln('Множество [J..P] ')

else

writeln('Множество [M..Z] ');

writeln(' содержит наибольшее количество');

end.

 

Пример  6.3.  Составить  программу-определитель: принадлежит  ли результат вычисления (17*3–25)*2+15 множеству [7..30].

program mnog3;

var

a:set of 7..30; {Oписание множества}

begin

writeln('Результат вычисления ');

writeln('(17*3–25)*2+15 ');

{Проверка на принадлежность множеству}

if (17*3–25)*2+15 in a

then writeln(' принадлежит множеству [7..30].')

else writeln(' не принадлежит множеству [7..30].');

end.

 

Пример 6.4. Составить программу-определитель, какое из множеств

[D..J] , [H..K] , [I..O] входит в множество [F..N]. program mnog1;

var

a,b,c,d:set of 'A'..'Z';     {объявление множеств}

begin a:=['D'..'J'];

b:=['H'..'K'];     {Задание множеств}

c:=['I'..'O'];

d:=['F'..'N'];

if a <= d then write('Множество [D..J] ');

if b <= d then

write('Множество [H..K] '); {Сравнение множеств}

if c <= d then write('Множество [I..O] ');

if (a>=d) and (b>=d) and (c>=d) then write('никакое множество не ');

writeln('входит в ');     {Вывод результата}

writeln('множество [F..N].');

end.

Пример 6.5. Составить программу, реализующую нахождение суммы элементов множества [3..27].

program mnog5;

var

a:set of 3..27;   {объявление множества}

s,n:integer;

begin s:=0;

for n:=3 to 27 do

s:=s+n; {Суммирование элементов} writeln('Сумма элементов множества [3..27] равна ',s,'.'); end.

 

Пример  6.6.  Составить  программу,  реализующую  создание множества с помощью датчика случайных чисел. Удалить из него все элементы кратные 3.

program mnog6;

var

a:set of 1..25;   {объявление множества}

k,n,elem:integer;

begin

writeln(' исходное множество:');

randomize;

for n:=1 to 10 do begin

elem:=random(25);

a:=a+ [elem];    {Создание множества}

write(' ',elem);

if (elem mod 3=0) then

begin    {Удаление из множества} a:=a–[elem]; {элементов кpатных 3} k:=k+1;

end;

end;

writeln;

writeln('            полученное множество:');

for n:=1 to 24 do          {Вывод множества}

if n in a then write(' ',n);

end.

Пример 6.7. Составить программу, реализующую удаление гласных букв из множеств [D..K], [O..T], [V..Z]. Результат записать в виде одного множества.

program mnog7;

var

a,b,c,glas,res:set of 'A'..'Z';       {объявление множеств}

m:char;

begin

a:=['D'..'K']; b:=['O'..'T'];         {Задание множеств}

c:=['V'..'Z']; glas:=['A','E','I','O','U'];

for m:='D' to 'K' do if m in glas then a:=a–[m];

for m:='O' to 'T' do       {Пpовеpка на наличие в }

if m in glas then b:=b–[m];

for m:='V' to 'Z' do       {множествах гласных букв}

if m in glas then b:=b–[m];

res:=a+b+c;      {Суммирование множеств}

for m:='A' to 'Z' do       {Вывод результата}

if m in res then write(' ',m);

end.

 

Пример 6.8. Программа выводит на экран слова, содержащие буквы последней строки входного файла.

program lab7;

var s:char;

b:set of 'А'..'я'; sl,str:string; fin:text; i:integer;

j: 'А'..'я';

pr:boolean;

begin

writeln('Вывести на экран слова, содержащие буквы слов последней');

writeln('строки входного файла INPUT.DAT');

assign(fin,'input.dat');

reset(fin);

while not eof (fin) do begin

readln(fin,str); writeln(str); end;

close(fin);

b:=[ ];   {формирование множества букв последней строки}

for i:=1 to length (str) do begin

s:=str[i];            {выделение буквы}

if not( s in b) then b:=b+[s]; {формирование множества}

end;

writeln ('Множество букв последней строки:');

for j:='А' to 'я' do         if j in b then writeln (j:4);

reset (fin);         {печать множества букв последней строки в выходной файл}

writeln ('Слова, содержащие буквы последней строки:');

while not eof (fin) do begin

readln(fin,str);

i:=1;

while i <= length (str) do begin

begin sl:=' '; pr:=false;

{формирование очередного слова и проверка его букв}

while    not (Str[i] IN [' ',',','–',':','.']) do begin

if str[i] in b then pr:=true; sl:=sl+str[i]; i:=i+1;

end;

if pr then writeln(sl);

repeat   {пропуск пробелов}

i:=i+1;

until(str[i]<>' ');

end; end; end;

close (fin);

end.

Задания для самостоятельного выполнения

Входной  информацией  является  произвольный  текстовый  файл, число строк в котором более 2-х. Словом считается любая последо- вательность подряд идущих символов. Считается, что слова разделяются пробелами. Реализовать поставленную задачу необходимо на основе использования множества.

 

1. Найти   и   вывести   все   гласные   буквы   (без   повторений),   которые встретились в словах и количество слов.

2. Найти  и  вывести  все  шипящие  буквы  (без  повторений),  которые встретились в самом длинном слове.

3. Найти  и  вывести  все  шипящие буквы,  которые  встретились во  всех словах? и количество слов.

4. Найти   и   вывести   все   гласные   буквы   (без   повторений),   которые встречаются в самом коротком слове.

5. Элементами слов могут быть как буквы, так и  цифры. Записать в файл слово, содержащее наибольшее количество цифр.

6. Элементами слов могут быть как буквы, так и цифры. Вывести на экран слово, содержащее наибольшее количество букв.

7. Элементами слов могут быть как буквы, так и  цифры. Вывести на экран слово, содержащее наибольшее количество нечетных цифр.

8. Элементами слов могут быть как буквы, так и  цифры. Вывести на экран слово, содержащее наибольшее количество четных цифр.

9. Элементами слов  могут  быть  как  буквы, так  и  цифры. Вывести все четные цифры (без повторений), которые содержатся во всех словах и количество слов.

10. Элементами слов могут быть как буквы, так и цифры. Вывести все нечетные цифры (без повторения), которые встречаются во всех словах и количество слов.

11. Элементами слов  могут  быть  как  буквы,  так  и  цифры.  Подсчитать количество нечетных цифр, содержащихся в самом длинном слове.

12. Элементами слов могут быть как  буквы, так  и  цифры. Все цифры,

входящие в самое длинное слово, заменить на символ «*».

13. Элементами слов могут быть любые символы. Найти и вывести слово,

содержащее наибольшее количество согласных букв.

14. Найти    и    вывести    слово,    содержащее    наибольшее    количество гласных букв.

15.В слове, в  котором обнаружено   наибольшее   количество шипящих букв, заменить их на символ «*».

16. Вывести все гласные буквы, содержащиеся в слове наибольшей длины,

и вывести число повторений каждой этой буквы.

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

18. Вывести  все  согласные  буквы,  содержащиеся  в  слове  наибольшей длины, и вывести число повторений каждой буквы.

19. Слова могут содержать любые символы языка. Найти и вывести слово, содержащее наибольшее количество символов, отличных от заглавных букв.

20. Слова  могут  содержать  любые  символы  языка.  Найти  и  вывести  в самом длинном слове все символы, отличные от заглавных латинских букв.

21. Слова  могут состоять из букв и цифр. В самом коротком слове каждую входящую в него цифру заменить на символ «&».

22. Слова  могут  состоять  из  букв  и  цифр.  Записать  в  файл  слово,

содержащее наибольшее количество четных цифр.

 

Контрольные вопросы

1. Что называется множеством?

2. Какое множество называется пустым?

3. Как описывается множественный тип?

4. Какие операции допустимы к данным типа множества?

5. Сколько элементов может содержать множество?

6. Значения каких типов может содержать множество?