Введение.

ЧАСТЬ 1

МНОЖЕСТВА

 

Цель работы:

- освоить понятия множества;

- изучить правила работы с рекурсией;

- приобрести навыки составления, отладки и тестирования рекурсивных программ.

 

Введение.

В математике множество определяется через входящие в него объекты, называемые элементами множества. Если объект х является элементом множества Х, то говорят, что х принадлежит Х, и обозначается, как х Î Х. Понятие множества является фундаментальным понятием в математике. Элементами множеств могут быть объекты любой природы. Однако при работе с ними необходимо иметь в виду, что элементы множества не упорядочены, и каждый из элементов может включаться в него только один раз.

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

1) перечисление всех входящих в данное множество Х элементов х_i; например
X={ х_i | i=1..5};

2) задание характеристических или ограничительных признаков Р элементов х данного множества X={x| P(x)}.

Множество Z , все элементы которого являются элементами множества Х, называется подмножеством множества Х и обозначается символом включения ZÌ X.

Множества Z и X равны Z=X тогда и только тогда, когда они содержат одни и те же элементы. Если множество Z, являющееся подмножеством Х, может иметь в своем составе все элементы множества Х, т.е. возможно равенство Z=X, то такое включение обозначается так: ZÌ X.

Количество элементов конечного множества называется мощностью множества, и обозначается так |X|.

Булеаном (или множеством-степенью) называется множество всех подмножеств первоначального множества, включая пустое множество {}.

Например, у множества А={a₁, a₂, a₃} булеан:

В(А)={ {}, {a₁}, {a₂}, {a₃}, {a₁, a₂}, { a₁, a₃}, { a₂,a₃}, { a₁, a₂, a₃}}.

Причем |A| = 3, а |B(A)| = 2³ = 8, т.е. мощность булеана конечного множества А равна |B(A)|=2^|A|.

Понятие множества в языке Паскаль значительно “беднее” математического. Здесь под множеством понимается конечная совокупность элементов, принадлежащих некоторому базовому типу данных. В качестве базовых типов используются такие простые типы как символьный, байтовый, перечисляемый и диапазонный. Например, тип integer не может быть базовым для множества, а его поддиапазон [0..255] - может, так как существует ограничение на число элементов. Для версии языка Turbo Pasсal число элементов не должно превышать 256. Такие ограничения связаны с формой представления множества в языке. Для переменных типа множества в памяти отводится по 1 биту на каждое возможное значение базового типа. Если множество содержит какой-то элемент, то связанный с ним бит имеет значение 1, если нет – 0. Обработка битовых строк производится в компьютере очень быстро – и это одно из существенных преимуществ множественного типа данных.

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