Перечисляемый и диапазонный типы

1 2 3 4 5 6 7

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

Определяется записью:

type T=(w₁, w₂,…, w_n);

где Т – идентификатор типа; w_i – константа идентификатора.

Например,

type color = (red, orange, yellow, green, blue, violet);

space = (x, y, z);

day = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);

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

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

weekday, dayoff: day;

traffic_light: color;

К этим переменным можно применить операторы присваивания, например,

weekday:= monday;

traffic_light:= red;

Важно, чтобы слева и справа в операторе присваивания стояли величины одного типа.

Значения типа, заданного перечислением, упорядочены. Упорядоченность определяется той последовательностью, в которой перечислены константные идентификаторы: первое значение в списке имеет номер нуль и т.д.

Для величин перечисляемого типа определены функции:

Sucс (w_i) = w_i+1,

Pred (w_i) = w_i-1,

Ord (w₁) = 0,

Ord (w_i) = Ord (Pred(w_i)+1) = Ord (Sucс (w_i)-1).

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

type color1=(red, blue, orange);

color2=(green, red, yellow);

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

Переменные и константы перечисляемого типа используются в таких конструкциях языка, как операторы цикла с параметром, условном операторе. Они делают программу наглядной и хорошо читаемой.

Однако они не могут быть введены и выведены с помощью write, read.

Тип диапазон (или ограниченный тип) представляет собой интервал значений порядкового типа. Он задается указанием диапазона: минимального и максимального значений. Например,

type workday = Monday..Friday;

char2 = ‘A’..’Z’;

Диапазон можно задавать для любого простого типа за исключением вещественного.

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

Наиболее часто отрезки типов используются в таких конструкциях языка, как оператор case, объявлении массива и др.

Функции Low(x) и High(x) дают минимальные и максимальные значения для порядковых, в том числе и диапазонных типов. Аргументом могут быть как переменные данного типа, так и имя типа.

3. Множественный тип данных.

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

type

<имя типа множества> =set of <имя базового типа>;

Например,

type Symbol = set of Char;

var Digits, Letter, Sing: Symbol;

таким образом, переменные Digits, Letter, Sing представляют различные группы символов.

На базе перечисляемого типа PrimaryColor (основной цвет) можно определить тип множества Color (цвет), т.е. множество, содержащее различные комбинации основных цветов. Можно считать, что этот тип множества задает смешивание цветов.

type PrimaryColor = (red, green, blue);

Color = set of PrimaryColor;

var alfa, beta: Color;

S: PrimaryColor;

Множества представляют собой неупорядоченный набор элементов.

Для того чтобы задать переменной какое-либо значение используется структура, называемая конструктором множества. В ней, в отличие от традиционной математической нотации множества {…}, элементы множества заключаются в квадратные скобки […]. Каждый элемент в скобках записывается через запятую или определяется через диапазон.

Приведем несколько примеров операторов присваивания для описанных выше переменных:

Digits:= [‘0’..’9’];

alfa:= [red, blue];

beta:= [ ];

Lettters:= [‘a..c’, x, y, z];

Запись [ ] означает пустое множество.

Множества можно использовать как константы, например:

Const YesNo = [‘Y’, ‘y’, ‘N’, ‘n’];

DigitLetters: set of char = [‘a’..’z’, ‘A’..’Z’, ‘0’..’9’].

Операции над множествами в программировании – это обычные операции теории множеств. Для иллюстрации этих операций используются диаграммы Эйлера-Венна, изображающие множества в виде областей на плоскости. Пусть А, В, С – множественные числа.

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

С = АÈВ = {c| cÎA или cÎB}

В языке Паскаль объединение множеств записывается как операция сложения (+).

Например,

A:= [1, 2, 3]; B:=[4..6]; C:=A+B;

В результате значение переменной С будет множество [1..6].

Имеется стандартная операция Include (Var S: set of T; Element: Т);

2. Пересечением множеств А и В называется новое множество С, состоящее из тех и только тех элементов, которые принадлежат и А, и В.

В теории множеств

С = АÇВ = {c| cÎA и cÎB}

В программировании операция пересечения множеств обозначается знаком умножения (*).

Например,

A:= [red, yellow, blue]; B:=[yellow, green]; C:=A*B;

В результате переменная С примет значение [yellow].

3. Разностью двух множеств А и В называется множество С, содержащее только те элементы А, которые не являются элементами В.

В теории множеств:

С = А\В = {c| cÎA и cÏB}

В языке Паскаль эта операция обозначается знаком вычитания (-).

Например,

A:= [х1, х2, х3, х4]; B:=[х4, х1]; C:=A-B;

Значение переменной С равно [х2, х3].

В библиотечном модуле System имеется функция Exlude (var S: set of T; Element: T);

4.Сравнение. Два множества А и В считаются равными, если они состоят из одних и тех же элементов. Порядок следования элементов сравниваемых множеств значения не имеет. Результатом выражений с применением операций (=; <>) будут являться значения true или false.

5.Проверка включения. Одно множество считается входящим в другое, если все его элементы содержатся во втором. Логические операции проверки включения одного множества в другое записываются через операции больше или равно.

Например,

A:= [‘z’, ‘x’, ‘c’]; B:= [‘c’, ‘x’]; C:= A>= B;

Логическая переменная С равна значению true.

6. Проверка принадлежности. Логическая операция проверки принадлежности элемента множеству обозначается служебным словом in. Использование ее в условных операторах позволяет эффективно проводить сложные проверки. Например, если необходимо проверить, является ли символьная переменная alfa буквой, обозначающей гласный звук, то вместо громоздкого условия:

if (alfa='a') or (alfa='e') or (alfa='i') or (alfa='o') or (alfa='u') or (alfa='y') then …

можно записать кратко

if alfa in [‘a’, ‘e’, ‘i’, ‘o’, ‘u’, ‘y’] then …

4. Экспериментальный раздел занятия.

1. Дано натуральное число п. Составить программу вывода цифр, не входящих в десятичную запись числа п (в порядке возрастания).

type

Mn = set of 0.. 9;

var s: Mn; n: Longint; k: byte;

begin

writeln('Введите число '); readln(n);

s: = [ 0.. 9 ];

while n <> 0 do begin

s:= s - [n mod 10]; { Исключаем цифру }

n:= n div 10

end;

for k:= 0 to 9 do

if (k in s)

then write(k:2);

writeln; readln

end.

2. "Решето Эратосфена". Найти простые числа в интервале от 2 до n.

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

const n = 1000; {Интервал чисел, в котором находятся простые числа.}

var k: integer;

function Prime(m: integer): boolean;

var i: integer;

begin i:= 2;

while (i <= m div 2) and (m mod i <> 0) do Inc(i);

Prime:= (i > m div 2)

end;

Begin

for k:= 2 to n do

if Prime(k)

then write(k, ' ');

readln

End.

Применим для решения этой задачи идею Эратосфена и используем множественный тип данных. Суть метода состоит в следующем: создается множество из чисел заданного интервала, и все они поначалу считаются простыми. Затем "вычеркиваем" те из них, которые не удовлетворяют требованию простоты. А именно, начиная с числа 2, осуществляется следующая процедура:

1. Берется первое не вычеркнутое число (оно, очевидно, простое), и удаляются все числа, кратные ему.

2. Вышеописанная процедура повторяется до тех пор, пока не будет достигнут конец интервала. После такого "просеивания" в исходном множестве останутся только простые числа.

Приведем два варианта программы:

сonst n = 255; { первый вариант}

type mn = set of 0..n;

var sim: mn;

i, j: integer;

begin

prim:= [2..n]; j:= 2;

while j <= n div 2 do begin

if (j in prim)

then bеgin {Поиск очередного простого числа.}

i:= j + j;

while (i <= n) do begin

prim:= prim - [i]; Inc(i, j)

end { Вычеркивание }

end;

Inc(j)

end;

for i:= 2 to n do

if (i in prim)

then write(i:4); {Вывод оставшихся после вычеркивания чисел, они простые)

readln

end.

сonst n = 255; { второй вариант }

var prim: set of 2..n;

k,m:integer;

begin

prim:=[2..n];

for k:=2 to n do

if k in prim

then

begin write(k,' ');

for m:=1 to (n div k) do

prim:=prim-[k*m]

end;

readln

end.

Поиск простых чисел из интервала большего, чем 2..255, упирается в ограничение множественного типа данных — не более 256 значений базового типа. Это ограничение можно обойти, вводя массив, элементами которого являются множества. Разработайте самостоятельно такую подпрограмму. Поэкспериментируйте с директивой {$R+}

3. Рассмотрим, как можно с помощью множественного типа данных решить задачу заказа посадочных мест в самолете. Согласно правилам номера мест могут быть выбраны на плане размещения мест и затем ведены в компьютер. Если они окажутся свободными, то занимаются. Если же не все выбранные места свободны, то должен быть выдан список свободных мест из числа выбранных и предложен список возможных альтернативных мест. Затем у пассажира запрашивается новый выбор. Такой процесс диалога пассажир-компьютер продолжается до тех пор, пока весь самолет не будет заполнен.

Разработаем следующую программу

const n=7; { множества: заказ мест}

type SetOfPlace=set of 1..n;

var oder,place:SetOfPlace; k,m:integer;

procedure PicturePlace(AccessiblePlase:SetOfPlace);

var k:integer;

begin

for k:=1 to n do

if k in AccessiblePlase then write(k:4); writeln

end;

begin place:=[1..n]; k:=0; oder:=[ ];

repeat