Алгоритмы и их свойства (стр. 20 )

6. Даны названия 15 компьютеров. Для каждого компьютера известны процессор, объем памяти, стоимость и быстродействие. Составить программу, которая вводит данные обо всех компьютерах, определяет, какой компьютер имеет минимальное отношение стоимость / быстродействие и печатает название этого компьютера и его характеристики.

§13. Множественные типы данных (множества)

Множественный тип данных S строится на основе некоторого базового типа BS. Базовый тип BS определяет конечное множество значений множественного типа S.

Пример:

а) базовый тип [1. .9] определяет множество цифр;

б) базовый тип [‘Иван’, ‘Марина’, ‘Олег’, ‘Ольга’] определяет множество, состоящее из 4-х имен;

в) базовый тип [‘А’. .‘Я’] определяет множество прописных русских букв.

Любые подмножества базового множества могут являться значениями переменных множественного типа S. Они образуются перечислением через запятую элементов базового множества или выражений базового типа и заключаются в квадратные скобки.

Причем множество ['D'..'A'] является пустым, так как в перечислении объектов базового типа порядковый номер 'D' больше порядкового номера'A'. Множество, не содержащее элементов, также называется пустым и обозначается []. Элементы множества, в отличие от массива, не упорядочены. Максимальное число элементов множества равно 256.

Множество описывается следующим образом:

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

Примеры:

а) var p1,p2: set of 'A'..'F';

б) var p3,p4: set of 0..125;

Арифметические операции над множествами

1. Объединением двух множеств называется множество элементов, принадлежащих обоим множествам. Обозначается: А+В.

Пример:

['b','f']+['b'..'d']=['b','c','d','f']

2. Пересечением двух множеств называется множество тех элементов, которые принадлежат одновременно двум множествам. Обозначается: А*В.

Пример:

а) [0..4]*[5,6]=[]

б) [KIEW, JALTA]*[MOCKWA, KIEW]=[KIEW].

3. Разностью двух множеств называется множество, содержащее те элементы первого множества, которые не являются элементами второго. Обозначается: А – В.

Пример:

[1,5,9]-[2,4,8,9]=[1,5]

С помощью арифметических операций можно строить различные выражения множественного типа.

Операции отношения над множествами

Для сравнения множеств используются операции отношения =,<>,<=,>=.

Выражение А=В (равенство – порядок неважен) истинно только тогда, когда сравниваемые множества содержат одни и те же элементы. Выражение А<>B (неравенство) истинно только тогда, когда одно из сравниваемых множеств содержит хотя бы один элемент, не входящий в другое множество. Выражение А<=B (включение) истинно только когда, когда все элементы множества А одновременно являются и элементами множества В. Выражение А>=B (включение) истинно только когда, когда все элементы множества В одновременно являются и элементами множества А.

Примеры:

а) ['C'..'E']=['D','E','C'];

б) [7,1,3]<>[7,2,3];

в) [KIEW]<=[MOCKWA, KIEW];

г) ['A'..'E']>=['A','B'];

5. Результат логического типа вырабатывает и специальная операция определения принадлежности элемента некоторому множеству. Эта операция обозначается служебным словом in. Слева от in пишется выражение соответствующего базового типа, а справа - выражение множественного типа, т. е. Х in А .

Пример:

1) выражение 5 IN [3..7] имеет значение true, т. к. 5 является элементом множества [3,4,5,6,7];

2) выражение k+2 IN [0..7]*[4,6,8] при k=1 имеет значение false, т. к. 3 не входит в множество [4,6], полученное в результате пересечения исходных множеств.

Порядок выполнения операций, предназначенных для работы с множествами:

1. *

2. +, -

3. in, =, <>, <=, >=.

Операции равного приоритета определяются порядком их появления в выражении. Для изменения порядка выполнения используются круглые скобки.

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

Пример 1: Подсчитать количество цифр в исходной символьной строке и напечатать все входящие в нее символы, кроме пробелов, знаков операций и знаков препинания.

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

Program mn;

uses crt;

var c:char;

k:integer;

Begin

clrscr;

k:=0;

repeat

read(c); {ввод строки посимвольно}

if not (c in [' ','.',':',',',';','+','-','*','/']) then

begin if c in ['0'..'9'] then k:=k+1;

write(c)

end;

until eoln;

writeln; writeln('число цифр в строке=',k:2)

End.

Примечание: Функция EOLN определяет маркер "конец строки" (нажатие ENTER) для текстового файла.

Результат:

Вводим строку: 12_7*AB_C,/765_4.OR_P:_65;9

127ABC7654ORP659

Число цифр в строке=10

Пример 2: Сформировать множество LB, в которое входят только латинские буквы, встретившиеся во входной строке, и множество знаков препинания PR из входной строки.

Program lat;

uses crt;

var c, i,j:char;

lb:set of 'a'..'z';

pr:set of '!'..'?';

Begin

clrscr;

lb:=[]; pr:=[];

repeat

read(c);

if c in ['a'..'z'] then lb:=lb+[c]

else if c in [':',';','.','!','?']

then pr:=pr+[c]

until eoln;

writeln; writeln('латинские буквы: ');

for i:='a' to 'z' do

if i in lb then write(i:2);

writeln; writeln('знаки препинания: ');

for j:='!' to '?' do

if j in pr then write(j:2)

End.

Результат:

Вводим строку: FYWA.*12 PRLLLLO. ORP A:PR?8

Латинские буквы:

F L O P R W Y

Знаки препинания:

. : ; ?

Вопросы

Что такое множество? Приведите примеры множеств. Какие типы данных используются в качестве базовых при построении множественных типов? Как задается множество в Паскаль? Какие арифметические операции определены над множествами? Примеры. Какие операции отношения определены над множествами? Примеры. Каков приоритет операций над множествами?

Задания

1. Дано описание переменной множественного типа:

var pm:set of(venera, saturn, mars);

Выписать все допустимые значения этой переменной.

2. Будут ли равны множества:

а) [¢A¢..¢D¢] и [¢A¢,¢B¢,¢C¢,¢D¢];

б) [leto, zima] и [zima, leto] ?

3. Какие из приведенных ниже выражений являются неправильными с точки зрения языка Паскаль и почему?

а) [¢A¢,¢B¢,¢C¢,¢K¢] / [¢A¢,¢B¢];

б) [5,6,1,3] >= [1,3,5,6];

в) [куб, шар] + [призма];

г) [уравнение, система] * [неравенство, система];

д) [3.5,7.1,2.0] - [1,2] .

4. Вычислить следующие выражения:

а) [5] <= [1..5];

б) [¢A¢..¢D¢,¢K¢..¢M¢] + [¢D¢..¢K¢];

в) [МОСКВА, ЛЕНИНГРАД, СОЧИ] * [СОЧИ];

г) [7,1,3..6] = [1,7];

д) [¢,¢,¢(¢,¢)¢,¢.¢] - [¢,¢,¢.¢];

е) 15 in [1..10] .

5. Дана программа. На входе ее подается следующий текст: 5A7233111BGE2257CDE. Признаком конца текста является точка. Определить, что будет напечатано в результате обработки этого текста программой ZAF:

Program zaf;

var z: set of 0..9;

i, k: integer;

si: char;

Begin

write(¢==>¢);z:=[];

repeat

read(si); k:=ord(si)-ord(¢0¢);

if k in [0..9] then z:=z+[k]

until k=¢.¢;

if z=[] then writeln(¢в тексте нет цифр¢)

else

begin

write(¢в тексте имеются следующие цифры: ¢);

for i:=1 to 9 do

if i in z then write(i:2);

writeln;

end;

End.

6. Вычислить следующие выражения:

а) [¢A¢,¢B¢,¢C¢]=[¢B¢,¢C¢,¢A¢]

б) [3,4,6]<=[2..8]

в) []>=[1,2]

г) trunc(8.3) in [1..9]

д) succ(¢C¢) in [¢b¢..¢D¢]

е) [2]<>[2,2,2]

ж) 16 in [16]

7. Вычислить выражение: [1..14]*[5,12..60]+[4..7]-[2..16]*[6]

8. Дан текст, содержащий N символов. Распечатать, какие из указанных символов (¢L¢, ¢T¢, ¢Z¢, ¢X¢) входят в данный текст. Составить программу, используя множественный тип.

9. Упростить данные выражения множественного типа:

а) [11..17]*[2]+[7,17..40]*[2..17]-[2..8];

б) (A-B)*A+(A-B)*B;

в) (A+B)*(A-B)*(B-A);

г) A+B-(A-B)-(B-A);

д) A-(A-B).

10. Дана непустая последовательность символов. Требуется построить и напечатать множество, элементами которого являются встречающиеся в последовательности:

а)  цифры от ¢0¢ до ¢9¢;

б)  буквы от¢A¢ до ¢F¢ и от ¢X¢ до ¢Z¢;

в)  буквы от ¢G¢ до ¢N¢ и цифры от ¢0¢ до ¢9¢;

г)  знаки препинания;

д)  буквы от ¢A¢ до ¢Z¢ и цифры от ¢0¢ до ¢5¢;

е)  буквы от ¢T¢ до ¢X¢ и знаки препинания;

ж)  цифры от ¢5¢ до ¢9¢ и знаки арифметических операций;

з)  знаки арифметических операций и знаки препинания;

и)  цифры и знаки арифметических операций;

к)  знаки препинания и буквы от ¢E ¢ до ¢N¢;

л)  знаки операций отношения;

м)  цифры от ¢3¢ до ¢9¢, буквы от ¢A¢ до ¢F¢ и знаки препинания;

н)  знаки арифметических операций и операций отношения;

11. Известен набор продуктов - хлеб, масло, сыр, молоко, имеющихся в ассортименте магазинов. В три магазина доставлены отдельные виды этих продуктов. Требуется построить множества А, В, С, которые содержат соответственно:

·  продукты, имеющиеся одновременно во всех магазинах;