Учебник: "Алгоритмы и программы (Афанасьева Т. В.)

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

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

Просмотров: 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;

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. Значения каких типов может содержать множество?

Оглавление|

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

Содержание