Множества. На вооружении флота 100 подводных лодок

Записи

На вооружении флота 100 подводных лодок. Адмиралу часто приходится решать задачи такого типа: 1)перечислить названия лодок, имеющих скорость, превышающую скорость вражеской подводной лодки Шредер; 2)подсчитать, сколько лодок имеют на вооружении больше 10 торпед; и т.д. Чтобы ускорить решение таких задач, адмирал приказал занести в компьютер сведения обо всех лодках, включая вражеские лодки Шредер и Рокстеди, а именно: их названия, скорость и число торпед, находящихся на вооружении.

Отвести место в оперативной памяти под указанную информацию о 102 лодках можно двумя способами: 1)с помощью массивов, 2)с помощью записей.

Рассмотрим программу, использующую первый способ. В каждом массиве будет 102 элемента, причем элементы 101 и 102 отведены под лодки противника.

VAR nazvanie: array [1..102] of String; {Место под 102 названия}
skorost: array [1..102] of Real; {Место под 102 скорости}
torped: array [1..102] of Byte; {Место под 102 количества торпед}
i:Integer;
BEGIN
{Здесь каким-нибудь способом заносим в отведенное место всю информацию,
например, присвоением - nazvanie[1]:='Щука'.... или загрузкой из файла}
{А теперь решим первую из двух задач:}
for i:=1 to 100 do if skorost[i] > skorost [101] then WriteLn(nazvanie[i])
END.

В памяти компьютера информация размещается в том порядке, в котором она встречается в описаниях:

ЯЧЕЙКИ ДЛЯ ИНФОРМАЦИИ	ИНФОРМАЦИЯ
nazvanie[1]	Щука
nazvanie[2]	Дельфин
...........	........
nazvanie[101]	Шредер
nazvanie[102]	Рокстеди
skorost[1]
skorost[2]
...........	........
skorost[101]
skorost[102]
torped[1]
torped[2]
...........	........
torped[101]
torped[102]
i	?

Вы видите, что данные об одной лодке разбросаны по памяти.

Рассмотрим второй способ. Иногда бывает удобно, чтобы данные, касающиеся одной лодки, хранились в памяти рядом, вот так:

ЯЧЕЙКИ ДЛЯ ИНФОРМАЦИИ	ИНФОРМАЦИЯ
lodka[1].nazvanie	Щука
lodka[1].skorost
lodka[1].torped
lodka[2].nazvanie	Дельфин
lodka[2].skorost
lodka[2].torped
..............	.........
vr.nazvanie	Шредер
vr.skorost
vr.torped
prot.nazvanie	Рокстеди
prot.skorost
prot.torped

Выстроенную подобным образом информацию в памяти компьютера часто называют базой данных.

Сами по себе массивы не позволяют хранить информацию в таком порядке, для этого нужно использовать записи. Запись - это набор данных (полей) различных типов, касающийся одного объекта. Например, запись, касающаяся нашей первой лодки, это набор трех полей: название - Щука (тип String), скорость - 26 (тип Real), количество торпед - 6 (тип Byte). Точка отделяет имя поля от обозначения записи, содержащей это поле.

Напомним, что в массиве разрешается хранить данные только одного типа.

Прежде чем отводить место в памяти под всю информацию, объясним Паскалю, из чего состоит одна запись, то есть опишем ее, задав специальный тип записи record и придумав ему имя, скажем, podlodka:

TYPE podlodka = record
nazvanie:String;
skorost:Real;
torped:Byte;
end;
..........

Тип определен, но место в памяти пока не отведено. Здесь нам, хочешь-не хочешь, придется воспользоваться массивом. При помощи VAR отведем место под массив из 100 записей для наших подлодок и отдельное место под две записи для вражеских. Массиву придумаем имя lodka.

VAR lodka:array[1..100] of podlodka;
vr,prot:podlodka; {Записи для двух вражеских лодок}
i:Integer;

..........................

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

Вот программа целиком:

TYPE podlodka = record
nazvanie:String;
skorost:Real;
torped:Byte;
end;
VAR lodka: array [1..100] of podlodka;
vr,prot:podlodka;
i:Integer;

BEGIN {Здесь задаем значения полям всех записей. Конечно, удобнее это делать
при помощи типизированных констант (см.следующую программу) или
файлов данных, но я использую простое присвоение:}
lodka[1].nazvanie:='Щука';
lodka[1].skorost:=26;
........
prot.torped:=22;
{А теперь решаем первую задачу:}
for i:=1 to 100 do if lodka[i].skorost > vr.skorost then WriteLn (lodka[i].nazvanie)
END.

Согласитесь, что при использовании записей текст программы гораздо понятнее.

Теперь запишем нашу программу с использованием типизированных констант, для краткости ограничив наш флот тремя подводными лодками:

TYPE podlodka = record
nazvanie:String;
skorost:Real;
torped:Byte;
end;
CONST lodka: array [1..3] of podlodka =
((nazvanie:'Щука'; skorost:26; torped: 6),
(nazvanie:'Дельфин'; skorost:14; torped:10),
(nazvanie:'Леонардо'; skorost:28; torped:11));
vr: podlodka =
(nazvanie:'Шредер'; skorost:20; torped:15);
prot: podlodka =
(nazvanie:'Рокстеди'; skorost:18; torped:22);
VAR i: Integer;
BEGIN
for i:=1 to 3 do if lodka[i].skorost > vr.skorost then WriteLn(lodka[i].nazvanie);
END.

Здесь вы видите, как правильно придавать начальные значения типизированным константам типа record.

Задание 116: Создайте базу данных о своих родственниках. О каждом родственнике должно быть известно:

· Имя

· Год рождения

· Цвет глаз

Массивы не используйте. Программа должна:

1) Распечатать ваш возраст и цвет глаз

2) Ответить на вопрос – правда ли, что ваш дядя старше тети.

Задание 117: Создайте базу данных о своих однокашниках. О каждом однокашнике должно быть известно:

· Фамилия

· Имя

· Пол

· Год рождения

Обязательно используйте массив не меньше, чем из 10 записей. Программа должна:

1) Вычислить средний возраст ваших однокашников

2) Определить, кого среди них больше – дам или кавалеров

3) Ответить на вопрос – есть ли в вашей базе тезки (это нелегко).

Множеством в Паскале называется набор значений какого-нибудь порядкового типа, подчиняющийся специфическим правилам, о которых мы поговорим дальше. В программе множество записывается в виде списка этих значений в квадратных скобках. Например, [7,5,0,4] или [‘п’, ’ж’, ’л’]. Множество не должно состоять более, чем из 256 элементов и не должно содержать элементов с порядковыми номерами меньше 0 и больше 255.

Если в множестве элемент повторяется, то считается, что он входит туда только один раз. Например, множества [2,5,2] и [2,5] эквивалентны.

Порядок элементов в множестве не играет роли. Множества [2,5] и [5,2] эквивалентны.

В описании тип множества задается словами set of. Например, конструкция

VAR a: set of Byte

говорит о том, что задана переменная, значением которой может быть любое множество из любого числа элементов типа Byte. Так, в некоторый момент процесса выполнения программы значением a может быть множество [210, 3, 92], а через пару секунд - [8, 5, 3, 26, 17].

Конструкция VAR c: set of (april, may, june) говорит о том, что переменная cможет иметь значением любое множество из имен april, may, june. Например, [april, june].

Конструкция VAR d: set of 10..18 говорит о том, что переменная dможет иметь значением любое множество целых чисел из диапазона от 10 до 18.

Над множествами определено несколько операций. Рассмотрим три из них: объединение (+), пересечение (*) и разность (-).

Операция	Результат	Пояснение
[1,4,4,5] +[1,2,3,4]	[1,2,3,4,5]	В результирующее множество входят элементы, имеющиеся хотя бы в одном из исходных множеств
[1,4,4,5] *[1,2,3,4]	[1,4]	В результирующее множество входят только те элементы, которые имеются в каждом из исходных множеств
[1,2,3,4] -[1,3,5]	[2,4]	В результирующее множество входят те элементы “уменьшаемого”, которые не встречаются в “вычитаемом”

Операция [1,2]*[3,4] будет иметь результатом [ ], то есть пустое множество.

Вот операции сравнения множеств:

if a = b then...	Если множества a и b состоят из одинаковых элементов...
if a <> b then...	Если множества a и b отличаются хотя бы одним элементом...
if a <= b then...	Если a является подмножествомb, то есть все элементы a являются элементами b...
if a >= b then...	Если b является подмножеством a, то есть все элементы b являются элементами a...

Операция проверки вхождения элемента E в множество a:

if E in a then...

Например, a:= [1,2,4]; if 2 ina then... {Если 2 входит в множество a....}

К сожалению, Паскаль не желает выводить множества на печать, точно так же, как он не желает печатать перечислимые типы. Поэтому просто так узнать, из каких элементов состоит множество, не удастся. Вот один из обходных путей:

Пусть задано множество a, описанное, как set of Byte. Будем пробовать уменьшать его на все элементы подряд, от 1 до 255, и каждый раз, когда это удается, распечатывать соответствующее число. Вот подходящий фрагмент, в котором мне понадобится “для транзита” еще одно множество b:

for i:=1 to 255 do begin
b:=a-[i];
if a<>b then begin WriteLn(i); a:=b end
end {for}

Вот гораздо более короткий и естественный путь:

for i:=0 to 255 do if i in a then WriteLn(i)

Я думаю, что работа с множествами Паскаля - любопытное и полезное занятие. Например, она нужна математикам, чтобы проверять свои теоремы. Я проиллюстрирую работу с множествами на простеньком примере:

Медиум загадывает шестерку чисел, каждое в диапазоне от 0 до 10 (числа могут и совпадать). Экстрасенс отгадывает их, называя свою шестерку. Есть ли между шестерками совпадающие числа? Если есть, то распечатать их.

Сначала решим задачу традиционными методами, а именно с применением массивов, а не множеств:

CONST razmer = 10; kol = 6;

VAR Medium, Extrasens: array [1..kol] of 0..razmer;
i, j, k:Integer;
BEGIN
{ Формируем случайным образом две шестерки: }
Randomize;

for i:= 1 to kol do begin
Medium[i]:=Random(razmer+1);
Extrasens[i]:=Random(razmer+1)

end {for};
{ Проверяем две шестерки на совпадение: }
k:=0; {Нам придется подсчитывать количество совпадений. k - счетчик}
for i:= 1 to kol do
for j:= 1 to kol do
if Medium[i] = Extrasens[j] then begin
k:=k+1;
WriteLn(Medium[i]) {Распечатываем совпадения}
end {if};
if k=0 then WriteLn(‘Не угадал ни разу‘)
END.

У данной программы есть недостатки. Пусть медиум загадал числа 2 4 1 5 4 8, а экстрасенс назвал 1 4 9 6 1 4. Программа распечатает числа 4 4 1 1 4 4, а достаточно было бы только 1 4. К тому же пришлось организовывать счетчик совпадающих чисел, чтобы иметь возможность ответить, угадано ли хоть одно число.

А теперь применяем множества:

CONST razmer = 10; kol = 6;

VAR Medium, Extrasens, a: set of 0..razmer;
i:Integer;
BEGIN
{ Формируем случайным образом две шестерки: }

Randomize;
Medium:=[ ]; Extrasens:=[ ]; {Начинаем формировать “с нуля”, то есть с пустых множеств}
for i:= 1 to kol do begin
Medium:= Medium + [Random(razmer+1)]; {Наращиваем по одному элементу в множестве медиума}
Extrasens:= Extrasens + [Random(razmer+1)] {Наращиваем по одному элементу в множестве экстрасенса}
end {for}

a:= Medium * Extrasens; {Множество a содержит совпадающие числа. Вот так – одним махом.}
if a=[ ] then WriteLn(‘Не угадал ни разу‘)
else begin
WriteLn(‘Есть совпадения, вот они: ‘);
{ Распечатываем элементы множества a: }
for i:=0 to razmer do if i in a then WriteLn(i);

end {else}
END.

Задание 118: Случайным образом формируется небольшое множество заглавных букв русского алфавита. Определить, входит ли в это множество хотя бы одна из букв М,И,Ф.

Дата добавления: 2014-12-27