28633

Структурный тип - Множество

Лекция

Информатика, кибернетика и программирование

Понятие о типе Множество в Турбо Паскале. Описание типа Множество и константымножества . Понятие о типе Множество в Турбо Паскале.

Русский

2013-08-20

45.5 KB

11 чел.

Лекция 15: Структурный тип - Множество.

1. Понятие о типе Множество в Турбо Паскале.

2. Описание типа Множество и константы-множества .

3. Обработка множеств.

4. Примеры использования множеств .

1. Понятие о типе Множество в Турбо Паскале.

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

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

Преимуществом типа Множество по сравнению с типом Массив является то, что множество может изменять количество своих элементов при выполнении программы, т.е. оно имеет черты динамической структуры в отличие от статического массива. Однако динамизм множеств лишь относительный: в Паскале количество элементов множества не может быть больше 256. Следовательно, не любой порядковый тип может быть типом элементов множества, а лишь такой, который содержит не более 256 элементов (например, нельзя использовать тип integer, однако можно использовать диапазоны от типа integer).

2. Описание типа Множество и константы-множества.

Формально тип Множество определяется в Паскале как тип, константами (значениями) которого являются все возможные подмножества из элементов базового типа, включая пустое множество. Базовым может быть порядковый тип или его тип-диапазон, содержащий не более 256 элементов, и каждый элемент которого имеет порядковый номер, не более 255. Описание типа Множество имеет форму:

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

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

type primes = set of 1..200; {множество простых чисел до 200}

var  pr1, pr2: primes; { переменные типа primes}

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

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

[2] {множество из одного элемента 2}

[ 0, 2..5] {множество из элементов 0,2,3,4,5}

[1..200] {множество всех чисел базового типа 1..200}

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

const  initset: set of 0..16 = [0,1,2,4,8,16]; const range=[2..100];

3. Обработка множеств.

Над множествами Паскаля определены теоретико-множественные операции и отношения.

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

+  операция объединения множеств, результатом её является множество, содержащее элементы множеств-операндов и только их.

Например:[2] + [2..5] даёт множество [2..5];

*  операция пересечения множеств, результатом её является множество, содержащее только элементы, общие для множеств-операндов (т.е. входящие во все множества-операнды);

Например: [1..200] *[0,2..5] даёт множество [2..5];

-  операция разности множеств, результатом её является множество, содержащее элементы множества-первого операнда и не содержащее элементы множества-второго операнда;

Например: [1..200] - [0,2..5] даёт множество [1, 6..200];

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

Два множества считаются эквивалентными, если они имеют одинаковые элементы (порядок перечисления элементов безразличен).

Множество А включено в множество В, если все элементы из А являются также элементами множества В.

= проверка эквивалентности, даёт true , если оба множества эквиваленты и false - в противном случае. Например: [1..3] =[3,1,2] - даёт true.

<> проверка неэквивалентности, является отрицанием эквивалентности.

Например: [1..3] <> [3,2,1] - даёт false.

<= проверка включения левого операнда в правый, даёт true, если такое включение имеет место и false - в противном случае.

Например: [5] <= [1..5]  - даёт true, а [0] <=[1..5] -  даёт false.

>= проверка включения правого операнда в левый, даёт true, если такое включение имеет место и false -  в противном случае.

Кроме отношений эквивалентности и включения имеется ещё отношение принадлежности элемента множеству. Это отношение имеет структуру:

< выражение базового типа> in  < множество над этим базовым типом >

Данное отношение  дает значение true, если первый операнд является элементом множества - второго-операнда и false -  в противном случае.

Например: 3 in [1..5]  - даёт true, а 0 in [1..5] - дает false.

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

< переменная типа-множество> := < выражение типа-множество>;

Например: pr1:= pr2; {копирование множества pr2  в pr1}

       pr1:= []; {присваивание pr1  пустого множества}

       pr1:= [1..200];{присваивание pr1 множества элементов от 1 до 200}.

Оператор присваивания совместно с операцией объединения или вычитания позволяет включать или исключать элементы из множества:

set1:=set1 + [a]; {включение элемента а в множество set1}

set2:= set2 - [d]; {исключение элемента d из множества set2}

Эти же действия выполняют стандартные процедуры include(set1,a) и exclude(set2,d) соответственно.

4. Примеры использования множеств.

Рассмотрим примеры программ на Турбо Паскале с использованием множеств, иллюстрирующие технику обработки множеств.

program lat_letters;{Определение множества латинских букв в строке}

uses CRT;

var s:string; {исходная строка}

      lat:set of 'A'..'Z'; {множество лат.букв}

      k:char; j:byte;

begin TextBackground(cyan);TextColor(white);ClrScr;

     repeat writeln('Введите строку');readln(s);

     if s='' then writeln('Ошибка: пустая строка');

     until s<>'';lat:=[];for j:=1 to length(s) do if upcase(s[j]) in ['A'..'Z'] then

     lat:=lat+[upcase(s[j])];if lat=[]  then writeln('В строке нет латинских букв') else

begin writeln('Латинские буквы:'); for k:='A' to 'Z'do if k in lat then write(k,' ')  end;

end { lat_letters}.

program sieve; {Решето Эратосфена - генератор простых чисел <= N}

       const N=100;

       uses CRT;

       var next:integer; {Следующее простое число}

             start,prim:set of 1..N; {Исходное множество и множество простых чисел}

   k,j:integer;

       begin TextBackground(cyan);TextColor(white);ClrScr;

                  start:=[2..N];prim:=[1];next:=2;

   {Формирование в prim множества простых чисел до N}

       while start<>[] do begin k:=next;while k<=N do

                     begin start:=start-[k];k:=k+next end; prim:=prim+[next];

                     repeat next:=next+1

                     until (next in start) or (next>N);

                              end; {Вывод чисел из множества prim}  

                    writeln('Простые числа до ',N,':'); for j:=1 to N do 

                    if j in prim then write(j:3,' ');writeln;

       end {sieve}.

Использование множеств в ряде случаев позволяет получать более простые тексты программ, "маскирующие" дополнительные циклы обработки. Например, в программе lat_letters таким "замаскированным циклом" является условие upcase(s[j]) in ['A'..'Z'], которое при отсутствии множеств, потребовало бы для реализации функцию с циклом по типу-диапазону 'A'..'Z'.


 

А также другие работы, которые могут Вас заинтересовать

24006. Гидрография, растительность и рельеф 165 KB
  В этой группе пятнадцать важнейших топографических знаков которые необходимо хорошо знать туристу. Поэтому нет простого топографического знака населенного пункта он складывается из топографических знаков различных местных предметов составляющих то что называется населенным пунктом. То есть это уже знак масштабный рис. Для него существует специальный топографический знак рис.
24007. Способы измерения расстояния 24.5 KB
  способы измерения расстояния. Определение расстояний на местности производится следующими способами: измерение расстояния шагами; измерение расстояния глазомерным способом; определение расстояния по времени движения. Самым распространенным и наиболее точным из этих способов является измерение расстояния шагами. Обычно шагомерное определение расстояний проводится на средних отрезках где требуется большая точность так как при равном хорошо выверенном шаге ошибки в среднем составляют только 24 измеренного расстояния.
24008. Ориентирование на местности. Азимут и компас 59 KB
  Азимут и компас. С помощью Полярно звезды или с помощью специальных намагниченных предметов стрелки компаса человек может независимо от других людей находясь в какой угодно точке поверхности нашей планеты определит сначала направление на север а затем встав к ней лицом по сторонам своего тела найти справа восток сзади юг слева запад. на стороны горизонта без компаса как днем так и ночью как в хорошую так и в плохую погоду. 84 Компас Компас это угломерный прибор который служит для измерения магнитных азимутов на местности не на...
24009. Способы и средства ориентирования 49 KB
  К средствам ориентирования и факторам способствующим или затрудняющим ориентирование в туристском походе относятся: топографическая карта местности или схема маршрута или маршрутная лента или легенда; топографическая ситуация в районе похода; просматриваемость ситуации небесные светила и так называемые местные признаки по которым грубо можно определить где север; протокол движения; специальные действия привязки разведки опрос местных жителей; инструменты компас часы курвиметр и т. Все ориентиры можно разделить на 3 вида:...
24010. Действия в случае потери ориентировки 28.5 KB
  Правда иногда ручей может впадать в болото и теряться но чаще всего ручей впадает в реку. Поэтому путь вниз по реке чаще всего имеющей по берегу тропу практически всегда приводит к людям. Если человек вышел на тропу то направление к жилью можно определить по следующим признакам: по состоянию лесной тропы: при приближении к населенному пункту она расширяется становится более натоптанной на ней чаще встречаются ответвления и места стоянок бытовой мусор;Лпри удалении от жилья картина противоположная; выйдя на лесовозную дорогу надо...
24011. Обеспечение безопасности при проведении туристских походов 18.68 KB
  При необходимости члены МКК дают советы руководителям по планированию маршрута действиям на какихлибо сложных его участках однако техническая и тактическая подготовка участников похода остается вне зоны внимания МКК. Зачастую участники выполняют задания без участия руководителя группы. Здесь причины возникновения аварийных экстремал ных ситуаций можно разделить на три группы: возникающие по вине руководителя группы; возникающие по вине детей участников похода; природные факторы и несчастные случаи в походе. В походах с детьми как нигде...
24012. Опасности в различных видах туризма 18.29 KB
  Признаки лавиноопасности: обильный снегопад перепады температур наличие лавинных концов в нижней части различные валы камни вырванные деревьяМеры предосторожности: переход осуществлять в нижней части; страховка; если участок протяжённый нужно переходить по одному с помощью лавинного шнура обязательно нужен смотритель; желательно проходить утром либо ночью. Меры предосторожности: спланировать переход должна быть тактика перехода выбор места переправы время и способ переправы переправу нужно планировать на утреннее часы. Меры...
24013. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ ЖУРНАЛИСТСКОЙ ДЕЯТЕЛЬНОСТИ 44.83 KB
  19 ВДПЧ: свобода убеждений и выражения их сбора и распространения информации и идей любыми средствами независимо от государственных границ.29 гарантия свободы мысли и слова свобода искать получать передавать и распространять информацию гарантия свободы массовой информации запрет на цензуру. Журналист имеет право: 1 искать запрашивать получать и распространять информацию; 2 посещать государственные органы и организации предприятия и учреждения либо их прессслужбы; 3 быть принятым должностными лицами в связи с запросом...
24014. МЕДИАСОЦИОЛОГИЯ И МЕДИАПСИХОЛОГИЯ 57.93 KB
  Журналист обязан иметь при себе достаточный запас ручек на случай если какаялибо из них подведет в нужный момент и как минимум пару блокнотов: для записи официальных бесед и для фиксации неофициальной информации. Диктофон фиксирует ход беседы при непосредственном контакте с собеседником но не имеет возможности фиксировать мысли журналиста возникающие по ходу беседы поэтому блокнот остается непременным атрибутом журналиста всегда он помогает при переработке поступающей информации. При сборе информации он контактирует с индивидуальным...