Множества в Паскале и в математике. Сходства и различия между ними.

⇐ ПредыдущаяСтр 10 из 23Следующая ⇒

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

В Паскале элементы множества должны принадлежать одному и тому же базовому типу.

Количество элементов: в математике не ограничено; в Паскале число элементов множества < = 256. При этом номера этих элементов могут быть от 0 до 255 (только положительными).Поэтому базовым типом множества на Паскале может быть только такой тип, число возможных значений которого укладывается в диапазон (0-255): символьный, перечисляемый, булевский, тип-диапазон, byte.

Порядок элементов не имеет значения ни в математике, ни в Паскале.

Так, на Паскале множество:

Это одно и то же множество

[1, 2, 3]

[3, 2, 1]

[2, 1, 3]

Объявление множества на Паскале

В общем виде объявление множества на Паскале имеет следующий вид:

var

s: set of базовый тип;

диапазон; byte; char, boolean; перечисление

S - переменная типа множества (или множественная переменная).

множественный тип

Указание базового типа автоматически задает совокупность возможных значений множественной переменной. В эту совокупность входят все возможные неповторяющиеся наборы (комбинации) значений базового типа, в том числе и наборы из одного элемента, включая пустое множество (оно автоматически входит в любое множество). Эти наборы и составляют возможные значения определенного множественного типа.

Возможные значения переменной S (реальным (текущим) значением будет то, которое будет присвоено явно)

ПРИМЕР.

var

s: set of 1..3;

[ ], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]

Примечания:

1. Значение переменной-множества представляет собой один конкретный набор из множества возможных наборов неповторяющихся значений базового типа [1, 2, 3].

2. В каждый конкретный момент времени переменная-множество может принимать только один из возможных наборов значений.

3. Объявление переменной множественного типа не вызывает автоматического присваивания ей значения. Под нее только выделяется память.

Хранится переменная типа множества в памяти очень компактно - в виде битовых строк. В этих строках хранятся не значения базового типа, а информация о наличии или отсутствии их (значений) в множестве: каждому отдельному значению базового типа соответствует отдельный разряд (бит). Единица в этом разряде соответствует ситуации наличия данного значения базового типав данный момент в значении переменной типа множество. Ноль означает, что данное значение базового типа в данный момент в множестве отсутствует. Пустое множество хранится в виде нулевой (состоящей из нулей) битовой строки.

Благодаря такому представлению множеств (в виде битовых строк или кодов), операции с множествами выполняются в машине очень быстро – это достоинство.

При работе с множествами есть недостаток : значение переменных множественного типа нельзя вводить и выводить в процедурах (ввода - вывода). Тем не менее значение элемента множества можно наблюдать в окне отладчика.

Присваивание значений множествам. Конструктор множества

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

Конструктор множества

Begin

s: = [1, 3];

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

ПРИМЕР.

Одно и то же

S: = [1, 2, 3, 4, 5];

Это сокращенная запись следующего списка букв латинского алфавита: 'a', 'b', 'c', 'd', 'e', …..'z', 'A', 'B', 'C', 'D', 'E', …….., 'Z' s: = ['a'.. 'Z']; - неправильная запись

s: = [1..5];

var

s: set of char;

begin

s: = ['a'..'z', 'A'..'Z']; S: = ‘a’..’z’; -- неправильно (нет квадратных скобок)

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

Над множествами возможны три операции. Все операции двухместные.

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

Var

a, b: set of char;

c: set of char;

a, b, c - множественные переменные. Set of char - множественный тип.

А В

В данном случае a и b принадлежат к одному и тому же множественному типу, а с - к другому, хотя переменные имеют формально один и тот же тип.

Таблица операций над множествами.

А В

Операция

Математика

Паскаль

Пересечение

a Ç b

a * b

А В

Объединение

A È b

a + b

Разность

a \ b

a - b

Определение 1. Пересечение множеств - новое множество, состоящее из элементов, принадлежащих одновременно множествам A и B.

Определение 2. Объединение множеств - новое множество, в которое входят элементы или из элементов множества А или из элементов множества В или из элементов, принадлежащих тому и другому одновременно.

Определение 3. Разность множеств - новое множество, в которое входят элементы уменьшаемого множества (A), не входящие в число элементов вычитаемого множества (B).

Примечание. Если при выполнении операции объединения (А + В) включаемые в А из В элементы уже присутствуют в множестве А и, если при выполнении операции разности (А - В) вычитаемые из А элементы отсутствуют в множестве А, то сообщения об ошибке не будет. Операции просто не будут выполняться.

Последние две операции используются для выполнения следующих действий:

1). (А+В) используются для включения в множество отдельных элементов.

2). (А-В) используется для исключения отдельных элементов из множества.

Var

s: set of [‘a’..’z’];

begin Пустое множество

s: = [];

Ошибка: а не является ни конструктором, ни переменной множественного типа.

s: = s+'a';

s: = s+['a']; //- верно, включает элемент 'a' в множество s ≡ include(s, ‘a’).

s: = s-['a']; //- верно, исключает элемент 'a' из множества s ≡ exclude(s, ‘a’).

Для ввода значения множества и вывода содержимого множества нельзя использовать операторы read и write.

ПРИМЕР. Рассмотрим программу, которая заполняет множество поэлементно.

Примечание. Пусть признаком завершения ввода является '.' (точка) во входном потоке:

1) Цикл с постусловием

var

s: set of char; {множество}

c: char; {символ, вводимый с клавиатуры}

Подготовка цикла

begin

s: = [];

c: = #0;

repeat

read (c);

if (c < > ’.’) then s: = s+[c];

until (c=’.’);

end.

2) Цикл с предусловием

var

s: set of char; {множество}

c: char; {символ, вводимый с клавиатуры}

Подготовка цикла

begin

s: = [];

c: = #0;

Здесь проверяется предыдущее,

а не текущее значение с

while c < > '.' do

begin

Вставка

read (c);

s: = s+[c]; надо вставить

end;

s: = s - ['.'];

end.

В данной программе не хватает одной строчки. Последним действием в цикле будет включение в число символов множества разделителя ('.'). Эту точку'.' из множества надо исключить (смотри вставку).

ПРИМЕР. Сформировать множество четных чисел в диапазоне от 1 до 100.

Схема решения:

1. Сначала надо сформировать множество чисел от 1 до 100, которое включает все четные и нечетные числа.

2. Исключить все нечетные числа.

Const

n = 100;

var

s: set of 1.. n;

k: 1.. n;

begin

В множество s включается совокупность чисел от 1 до 100

{начальное заполнение}

s: = [1.. n];

{исключение нечетных чисел}

for k: = 1 to n do {odd - возвращает " истина", если число - нечетное}

if odd(k) then

s: = s - [k];

end.

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

Можно сравнивать множества только совместимых типов (как и в п.4).

	Математика	Паскаль
	A = B	A = B
	A < > B	A < > B
	A Ê B	A > = B
	A Í B	A < = B
	x ' A	x in A

Все операции возвращают логический результат. Для каждой операции правила формулируются следующим образом:

1. Равенство: (true) только тогда, когда 2 множества имеют одинаковый набор символов.

2. Неравенство: (true) когда набор символов различный.

3. A Ê B возвращает true, если все элементы множества В входят в множество А.

4. A Í B возвращает true, если все элементы множества А входят в множество В.

5. x ' A возвращает true, если х - (элемент базового типа множества А) имеется в множестве А.

Применение множеств.

1-й Случай: Множества используют для того, чтобы исключить большое количество последовательных проверок.

ПРИМЕР. При вводе символа с клавиатуры надо определить, является ли текущий символ символом английского алфавита. Без использования множеств это можно сделать тремя путями:

3 путь: case c of ‘a’..’z’, ; A’..’Z’: < с - буква> …………

1 путь.

26 проверок

. Var

c: char;

begin

if (c = 'a') or (c = 'b') or... or (c = 'z') or (c = 'A') or... or (c = 'Z')

then < с - буква> ...

2 путь

Var

c: char;

begin

if (c > = 'a') and (c < = 'z') or (c > = 'A') and (c < = 'Z')

then < с - буква> ...

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

if c in ['a'.. 'z', 'A'.. 'Z'] then < с - буква> ...

2-й случай: Множества используются для формирования неповторяющегося набора элементов.

ПРИМЕР. Заполнить массив из 5 элементов пятью случайными неповторяющимися числами из некоторого диапазона. Без использования множеств это можно сделать следующим образом:

Var

s: array [1..5] of byte; {массив для случайных чисел}

i: byte; {случайное число}

j: byte; {количество сформированных случайных чисел}

k: byte; {параметр цикла}

exist: boolean; {сл. число уже есть в массиве}

begin

{Начальное заполнение}

fillchar (s, 5, 0);

j: = 0;

{инициализация датчика случайных чисел}

randomize;

На "? " нужно поставить число, которое должно быть верхней границей диапазона случайных чисел.

{цикл, пока не заполним}

repeat

i: = random (? );

exist: = false;

{проверка вхождения в набор}

for k: = 1 to 5 do

begin

if (s [k] = i) and (i < > 0)

then exist: = true;

end;

{смотрим результаты анализа}

if (exist = false) and (i < > 0)

then begin

inc (j); что будет, если это убрать? (см. ниже)

s[j]: = i;

end;

until j = 5;

end.

Замечание: Random(10) возвращает целое число в диапазоне 0 < = x < 10

Если все оставить как есть, то ноль также будет включен в число элементов формируемого массива. Для его исключения необходимо добавить проверку: (i < > 0).

проверка – случайное число уже входит в набор

С использованием множеств та же задача решается следующим образом (более кратко):

Var

a: array[1..5] of integer;

s: set of byte;

i: byte; {случайное число }

j: byte; {количество сформированных случайных чисел}

begin

{Начальное заполнение}

s: = [ ];

j: = 0;

fillchar(a, 5*2, 0);

{инициализация датчика случайных чисел}

randomize;

{цикл, пока не заполним}

repeat

i: = random (? );

if (not (i in s)) and (i < > 0) {Проверка вхождения в набор}

then

begin

s: = s + [i];

inc (j);

a[j]: =i;

end;

until j = 5;

end.

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

Примечание. Как и в предыдущем случае, используется процедура inc:

inc (j); ® j: = j +1.

Использование этой процедуры влияет на ситуацию выхода из цикла.

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

Идея этого способа состоит в следующем:

- вводится вспомогательная переменная, которая в цикле принимает все возможные значения базового типа множества;

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

Var

s: set of 1.. 100;

k: 1.. 100; {вспомогательная переменная}

begin

{формирование множества}

...

{цикл по вспомогательной переменной}

for k: = 1 to 100 do

if k in s then

writeln (k, ' входит в s');

end.

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

⇐ Предыдущая 5 6 7 8 91011 12 13 14 Следующая ⇒