Структурированный тип данных - множество

Определение множеств

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

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

Пример определения и задания множеств:

 

type

DigitChar = set of '0'..'9';

Digit = set of 0..9;

var

s1,s2,s3: DigitChar;

s4,s5,s6: Digit;

...

s1:=['1','2','3'];

s2:=['3','2','1'];

s1:=['2','3'];

s1:=[0..3,6];

s1:=[4,5];

s1:=[3..9];

...

 

В этом примере множества s1 и s2 эквивалентны, а множество s3 включено в s2, но не эквивалентно ему.

Описание типа множество имеет вид

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

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

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

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

Для задания множества используется так называемый конструктор множества: список спецификаций элементов множества, отделяемых друг от друга запятыми; список обрамляется квадратными скобками. Спецификациями элементов могут быть константы или выражения базового типа, а также – тип-диапазон того же базового типа.

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

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

* – пересечение множеств; результат содержит элементы, общие для обоих множеств. Например, s4*s6 содержит [3], s4*s5 – пустое множество.

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

s4+s5 содержит [0,1,2,3,4,5,6];

s5+s6 содержит [3,4,5,6,7,8,9];

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

s6-s5 содержит [3,6,7,8,9];

s4-s5 содержит [0,1,2,3,6];

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

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

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

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

in – проверка принадлежности; в этой бинарной операции первый элемент – выражение, а второй – множество того же типа; возвращает true, если выражение имеет значение, принадлежащее множеству:

3 in s6 возвращает true;

2*2 in s1 возвращает false;

Пример

В следующем примере реализуется алгоритм выделения из первой сотни натуральных чисел всех простых. В его основе (также как и в примере из лабораторной работы №3) лежит прием, известный под названием «решето Эратосфена». Сравните программы, приведенные здесь и в лабораторной работе №3.

 

{ Выделение всех простых чисел из первых N целых }

const

N = 100; {Количество элементов исходного множества}

type

SetOfNumber = set of 1..N:

var

n1,next,i: word; {Вспомогательные переменные}

BeginSet, {Исходное множество}

PrimerSet: SetOfNumber; {Множество простых чисел} BEGIN

BeginSet:= [2..N]; {Создать исходное множество}

PrimerSet:= [1]; {Первое простое число}

Next:= 2; {Следующее простое число}

while BeginSet <> [] do {Начало основного цикла}

begin

n1:= next; {n1-число,кратное очередному

простому (next)}

while n1 <- N do {Цикл удаления из исходного

множества непростых чисел:}

begin

BeginSet:= BeginSet-[n1];

n1:=n1+next; {Следующее кратное}

end; {Конец цикла удаления}

PrimerSet:= PrimerSet+[next];

repeat {Получить следующее простое, которое есть

первое невычеркнутое из исходного множества}

inc(next)

until (next In BeginSet) or (next > N)

end; {Конец основного цикла)

 

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

for i:= 1 to N do

if I in PrimerSet then write(i:8);

writeln;

END.

Процедуры и функции

Описание подпрограммы

Описание подпрограммы состоит из заголовка и тела подпрограммы.

Заголовок процедуры имеет вид:

 

PROCEDURE <имя> [(<сп.ф. п. >)];

 

Заголовок функции:

 

FUNCTION <имя> [(<.сп.ф.п.>)]: <тип>:

 

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

<сп.ф.п-> - список формальных параметров,

<тип> - тип возвращаемого функцией результата.

Полный формат описания процедуры:

Procedure <Имя процедуры> (<Имя форм. параметра 1>:<Тип1>;

< Имя форм. параметра 2>:<Тип2>);

<Раздел описаний>

Begin

<Тело процедуры>

End;

 

Раздел описаний может иметь такие же подразделы, как и раздел описаний основной программы (описание процедур и функций - в том числе). Однако все описанные здесь объекты "видимы" лишь в этой процедуре. Они здесь локальны также, как и имена формальных параметров. Объекты, описанные ранее в разделе описаний основной программы и не переопределенные в процедуре, называются глобальными для этой подпрограммы и доступны для использования.

Формат описания функции:

Function <Имя функции> (<Имя форм. параметра 1>:<Тип>;

< Имя форм. параметра 2>:<Тип>?): <Тип результата>;

<Раздел описаний>

Begin

<Тело функции>

End;

 

В теле функции обязательно должна быть хотя бы команда присвоения такого вида:

 

<Имя функции>:=<Выражение>;

 

Указанное выражение должно приводить к значению того же типа, что и тип результата функции, описанный выше.

Сразу за заголовком подпрограммы может следовать одна из стан­дартных директив ASSEMBLER, EXTERNAL. FAR, FORWARD, INLINE, INTERRUPT, NEAR. Эти директивы уточняют действия компилятора и распространяются на всю подпрограмму и только на нее, т.е. если за подпрограммой следует другая подпрограмма, стандартная директива, указанная за заголовком первой, не распространяется на вторую.

Например, директива FORWARD используется при опережающем описании для сообщения компилятору, что описание подпрограммы следует где-то дальше по тексту программы (но в пределах текущего программного модуля).

Вызов процедуры представляет в программе самостоятельную инструкцию:

 

<Имя процедуры>(<Фактический параметр 1>, <Фактический параметр 2>,…);

 

Типы фактических параметров должны быть такими же, что и у соответствующих им формальных.

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

Параметры

Список формальных параметров необязателен и может отсутство­вать. Если же он есть, то в нем должны быть перечислены имена формаль­ных параметров и их тип, например:

 

Procedure SB (a: real; b: Integer: с: char);

 

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

 

Function F (а: real; b: real): real;

 

можно написать проще:

 

Function F (a, b: real): real;

 

Операторы тела подпрограммы рассматривают список формальных параметров как своеобразное расширение раздела описаний: все перемен­ные из этого списка могут использоваться в любых выражениях внутри подпрограммы. Таким способом осуществляется настройка алгоритма подпрограммы на конкретную задачу.

Любой из формальных параметров подпрограммы может быть либо параметром-значением, либо параметром-переменной. В предыдущем примере параметры А и В определены как параметры-значения. Если параметры определяются как параметры-переменные, перед ними необходимо ставить зарезервированное слово VAR, например:

 

Function Power (var a: real; b: real): real;

 

Здесь параметр А – параметр-переменная, а В – параметр-значение.

Определение формального параметра тем или иным способом существенно только для вызывающей программы: если формальный параметр объявлен как параметр-переменная, то при вызове подпрограммы ему должен соответствовать фактический параметр в виде переменной нуж­ного типа; если формальный параметр объявлен как параметр-значение, то при вызове ему может соответствовать произвольное выражение. Контроль за неукоснительным соблюдением этого правила осуществляется компилятором Турбо Паскаля.

Для того чтобы понять, в каких случаях использовать параметры-значения, а в каких - параметры-переменные, рассмотрим, как осуществляется замена формальных параметров на фактические в момент обращения к подпрограмме.

Если параметр определен как параметр-значение, то перед вызовом подпрограммы это значение вычисляется, полученный результат копируется во временную память и передается подпрограмме. Важно учесть, что даже если в качестве фактического параметра указано простейшее выражение в виде переменной или константы, все равно подпрограмме будет передана лишь копия переменной (константы). Если же параметр определен как параметр-переменная, то при вызове подпрограммы передается сама переменная, а не ее копия. Любые возможные изменения в подпрограмме параметра-значения никак не воспринимаются вызывающей программой, так как в этом случае изменяется копия фактического параметра, в то время как изменение параметра-переменной приводит к измене­нию самого фактического параметра в вызывающей программе.

Представленный ниже пример поясняет изложенное. В программе задаются два целых числа 5 и 7, эти числа передаются процедуре INC2, в которой они удваиваются. Один из параметров передается как параметр-переменная, другой - как параметр-значение. Значения параметров до и после вызова процедуры, а также результат их удвоения выводятся на экран.

const

а: integer = 5;

b: integer = 7;

PROCEDURE lnc2 (var с: Integer; b: Integer);

begin {Inc2}

с:= с + с;

b:= b + b;

writeln(' удвоенные:', c:5, b:5);

end; {Inc2}

BEGIN {main}

writeln(' исходные:'. a:5, b:5);

lnc2(a,b);

writeln(' результат:', a:5, b:5);

END. {main}

 

В результате прогона программы будет выведено:

 

Исходные: 5 7 удвоенные 10 14 результат 10 7

 

Как видно из примера, удвоение второго формального параметра в процедуре INC2 не вызвало изменения фактической переменной В, так как этот параметр описан в заголовке процедуры как параметр-значение. Этот пример может служить еще и иллюстрацией механизма "закрывания" глобальной переменной одноименной локальной: хотя переменная В объявлена как глобальная (она описана в вызывающей программе перед описанием процедуры), в теле процедуры ее «закрыла» локальная пере­менная В, объявленная как параметр-значение.

Итак, параметры-переменные используются как средство связи ал­горитма, реализованного в подпрограмме, с «внешним миром»: с помощью этих параметров подпрограмма может передавать результаты своей работы вызывающей программе. Разумеется, в распоряжении программиста всегда есть и другой способ передачи результатов - через глобальные переменные. Однако злоупотребление глобальными связями делает про­грамму, как правило, запутанной, трудной в понимании и сложной в отладке. В соответствии с требованиями хорошего стиля программирования рекомендуется там, где это возможно, использовать передачу результатов через фактические параметры-переменные.

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

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

Примеры

Определение максимума из трех чисел:

 

Program Fn;

Var

A,B,C:Real;

Function Max(A,B:Real):Real;

{Описываем функцию Max с формальными}

Begin {параметрами A и B, которая принимает }

If A>B Then

Max:=A {значение максимального из них }

Else

Max:=B

{Здесь A и B - локальные переменные }

End;

Begin

Writeln('Введите три числа');

Readln(A,B,C);

Writeln('Максимальным из всех является ', Max(Max(A,B),C))

End.

 

Упорядочивание трёх чисел в порядке неубывания:

 

Program Pr;

Var

S1,S2,S3:Integer;

Procedure Swap(Var A,B: Integer);

{Процедура Swap с параметрами-переменными}

Var C: Integer; {C - независимая локальная переменная}

Begin

C:=A; A:=B; B:=C {Меняем местами содержимое A и B}

End;

Begin

Writeln('Введите три числа');

Readln(S1,S2,S3);

If S1>S2 Then Swap(S1,S2);

If S2>S3 Then Swap(S2,S3);

If S1>S2 Then Swap(S1,S2);

Writeln('Числа в порядке неубывания:V',S1,S2,S3)

End.

 

Рассмотрим следующий пример. В языке Турбо Паскаль нет операции возведения в степень, однако с помощью встроенных функций LN(X) и ЕХР(Х) нетрудно реализовать новую функцию с именем, например, POWER, осуществляющую возведение любого вещественного числа в любую вещественную степень. В следующем примере вводится пара чисел X и У и выводится на экран дисплея результат возведения Х сначала в степень +У, а затем - в степень - У. Для выхода из программы нужно ввести Ctrl-Z и «Ввод».

 

var

х,у: real;

FUNCTION Power(a,b: real): real;

begin {Power}

if a > 0 then Power:= exp(b * In(a))

else

If a < 0 then

Power:= exp(b * ln(abs(a))) eIse

if b=0 then Power:= 1 else Power:= 0

end {Power};

 

BEGIN {main}

repeat

readln(x,y);

wrlteln(power(x,y):12:10, power (x, -у):15:10)

until EOF;

END. {main}

 

Для вызова функции POWER мы просто указали ее в качестве параметра при обращении к встроенной процедуре WRITELN. Параметры Х и У в момент обращения к функции - это фактические параметры. Они подставляются вместо формальных параметров А и В в заголовке функции и затем над ними осуществляются нужные действия. Полученный резуль­тат присваивается идентификатору функции - именно он и будет возвра­щен как значение функции при выходе из нее. В программе функция POWER вызывается дважды - сначала с параметрами Х и Y, а затем Х и ‑У, поэтому будут получены два разных результата.

Механизм замены формальных параметров на фактические позволяет нужным образом настроить алгоритм, реализованный в подпрограмме. Турбо Паскаль следит за тем, чтобы количество и тип формальных параметров строго соответствовали количеству и типам фактических параметров в момент обращения к подпрограмме. Смысл используемых фактических параметров зависит от того, в каком порядке они перечислены при вызове подпрограммы. В примере первый по порядку фактический параметр будет возводиться в степень, задаваемую вторым параметром, а не наоборот. Пользователь должен сам следить за правильным порядком перечисления фактических параметров при обращении к подпрограмме.