4786

Множества в программировании на языке Pascal

Лекция

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

Множества. Множественный тип. Конструктор множества. Операции и отношения. Применения множеств в программировании. Задачи и упражнения. Еще одним сложным стандартным типом данных, определенным в языкеPasca...

Русский

2012-11-27

47 KB

15 чел.

Множества.

1.Множественный тип.

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

3.Операции и отношения.

4.Применения множеств в программировании.

5.Задачи и упражнения.

 1. Множественный тип.

Еще одним сложным стандартным типом данных, определенным в языке Pascal, является множественный тип. Значением множественного типа данных является множество, состоящее из однотипных элементов. Тип элемента множества называется базовым типом. Базовым типом может быть скалярный или ограниченный тип. Таким образом, множество значений множественного типа - это множество всех подмножеств базового типа, включая и пустое множество. Если базовый тип содержит N элементов, соответствующий множественный тип будет содержать 2N элементов.

Характерное отличие множественного типа - определение на нем наиболее распространенных теоретико-множественных операций и отношений. Это делает множественный тип похожим на простые типы данных. Множественные типы описываются в разделе типов следующим образом :

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

  Множественный

  тип

 

Например,

а) Type Beta = Set of 100..200;

б) Type Glas = Set of char ; {Vowel}

в) Type Color = (red, orange, yellow, green, light_blue, blue, violet); 

Paint = Set of Color;

г) Type TwoDigNum = Set of 10..99;

Var A, B: Beta;

llet, flet: Glas;

last, first: Paint;

  Sinit: TwoDigNum;

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

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

  конструктор

 Элемент

 конструктора

 

 

Например:

[ ] - пустое множество

[2, 5 ..7] - множество {2, 5, 6, 7}

['A'..'Z', 'O'..'9'] - множество, состоящее из всех прописных латинских букв и цифр

[i + j .. i + 2*j] - множество, состоящее из всех целых чисел между i + j и i + 2j

Отметим, что если в выражении [v1..v2] v1 > v2, множество [v1 .. v2] - пустое.

3. Операции и отношения.

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

А + В - объединение А В

А * В - пересечение А В

А - В - разность А \ В

Между А и В определены также отношения порядка и равенства

А = В,   А <> В,  А < В, А <= В,  А > В,   А >= В;

Отношения порядка интерпретируются как теоретико-множественные включения.

Если А - множество и х - элемент базового типа, то определено отношение принадлежности  х  in  A - x принадлежит A ( x A ).

Каждое из отношений, описанных выше, по-существу является операцией, результат которой имеет тип Boolean. Таким образом, если Init - переменная типа Boolean, возможно присваивание Init := A < B. Возможны такие сравнения ( А = В ) = ( С = D ).

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

А := А * [1 .. 10] + B ;  B := (А + B)*['A' .. 'Z'] ;

4. Применения множеств в программировании.

При реализации языка размеры множеств всегда ограничены константой, зависящей от реализации. Обычно эта константа кратна длине машинного слова. Это происходит потому, что множества реализованы в виде логических (двоичных) векторов следующим образом: каждой координате двоичного вектора однозначно соответствует один из элементов базового типа. Если элемент a принадлежит представляемому множеству A, то значение координаты вектора, соответствующее a, равно 1. В противном случае значение соответствующей координаты равно 0.

Например, если множество A описано как Set of 0..15, то его представляет 16-ти мерный двоичный вектор, координаты которого перенумерованы от 0 до 15, и i-той координате соответствует элемент i базового типа.

Базовый тип :  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15

Двоичный вектор :  0  0  1  1  0  1  0  1  0  0  0  1    0   1   0    0

Представленное множество : A = [2, 3, 5, 7, 11, 13]

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

For X := 'A' to 'Z' do

    If (X ='A') or (X ='E') or  (X ='I') or (X ='O') or (X='U')

        then Statement1

        else Statement2

лучше написать

 For X := 'A' to 'Z' do

   If X in ['A','E','I','O','U']

                then Statement1

                else Statement2

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

В системе Turbo-Pascal максимальное количество элементов в множестве равно 256. Таким образом, в качестве базового типа можно выбрать, например, Char или отрезок 0..255. В заключение раздела приведем пример программы, использующей множественные типы данных.

Пример. Построить множество всех простых чисел из отрезка 2..n  (n 255).

Метод, с помощью которого мы это сделаем, известен как "Решето Эратосфена". Суть этого метода в следующем: Пусть Prime - строимое множество простых чисел и Grating - множество, называемое решетом. Алгоритм начинает работу с Prime = []; Grating = [2..n].

 Шаг основного цикла:

 а. Наименьший элемент Grating поместить в Prime;

 б. Удалить из Grating все числа, кратные этому элементу;

 Алгоритм заканчивает работу при Grating = []

Program EratosfenGrating;

   Const n = 255;

      Var Grating, Prime: set of 2 .. n ;

             i, Min : integer ;

 Begin

   Grating := [2 .. n] ; Prime := [] ; Min := 2;  {инициализация}

   While Grating <> [] do begin    {основной цикл}

      While not(Min in Grating) do   {поиск наименьшего элемента в решете}

         Min := Min + 1;

         Prime := Prime + [Min] ;    {пополнение множества простых чисел}

         For i := 1 to n div Min do    {исключение кратных из решета}

           Grating := Grating - [i*Min];

    end;

    Writeln('Primes: ');     {вывод множества простых чисел}

     For i := 1 to n do  

        If i in Prime then write(i, ', ')

End.

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

5. Задачи и упражнения.

1. Записать с помощью конструктора множество X, составленное из латинских букв a, b, c, d, i, j, k, x, y, z.

2. Записать с помощью конструктора множество из трех основных цветов множественного типа Paint.

3. Записать с помощью конструктора множество целых решений квадратного неравенства x^2 +p*x + q < 0 в предположении, что корни соответствующего квадратного уравнения лежат в интервале [0; 255]

4. Записать с помощью конструктора множество простых чисел-близнецов из интервала 1..30.


Имя типа

=

 Set

of  

 Базовый тип

 Элемент конструктора

  [

  ]

 ,

 ..

Выражение

Выражение

Выражение


 

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

32640. Бизнес- план инвестиционного проекта: содержание, назначение 51 KB
  Бизнес план инвестиционного проекта: содержание назначение Бизнес план Бизнесплан это подробный четко структурированный и тщательно подготовленный документ описывающий цели и задачи которые необходимо решить предприятию компании способы достижения поставленных целей и техникоэкономические показатели предприятия и или проекта в результате их достижения. Содержание бизнесплана Вводная часть резюме проекта Вводная часть как правило пишется уже после того как составлен весь план. в ней содержатся основные положения всего...
32641. Принципы и процессы планирования проекта. Уровни планирования 62.5 KB
  Принципы и процессы планирования проекта. Принципы и процессы планирования Сущность планирования состоит в задании целей и способов их достижения на основе формирования комплекса работ мероприятий действий которые должны быть выполнены применении методов и средств реализации этих работ увязки ресурсов необходимых для их выполнения согласовании действий организаций участников проекта. Основная цель планирования состоит в построении модели реализации проекта. Она необходима для координации деятельности участников проекта с ее помощью...
32642. Формирование статей затрат проекта. Калькуляция расходов, сметы, бюджет проекта 27.5 KB
  Формирование статей затрат проекта. Калькуляция расходов сметы бюджет проекта. Бюджет проекта предназначен для планирования расхода средств проекта по временным периодам год квартал месяц в течение всего времени его осуществления. Обычно расход средств проекта первого года планируется более подробно показывается поквартальное и помесячное распределение денежных средств.
32643. Управление качеством в проекте 40 KB
  Управление качеством в проекте. Управление качеством Одной из ключевых функций управления проектом наряду с такими как управление стоимостью и временем является управление качеством проекта. Качество это целостная совокупность характеристик объекта относящихся к его способности удовлетворять установленные или предполагаемые потребности. Понятие качество следует отличать от понятия градация сорт класс.
32644. Проектные риски и их основные виды 39.5 KB
  Вероятность рисков это вероятность того что в результате принятия решения произойдут потери для предприятия то есть вероятность нежелательного исхода. Проектные риски это совокупность рисков угрожающих реализации инвестиционного проекта или способных снизить его эффективность коммерческую экономическую бюджетную социальную и т. Виды инвестиционных рисков многообразны. В отдельных источниках также выделяют такие риски как: риск связанный с отраслью производства вложение в производство товаров народ ного потребления в среднем...
32645. Методы анализа и прогнозирования риска и неопределенности в проекте 274.5 KB
  Анализ рисков процедуры выявления факторов рисков и оценки их значимости по сути анализ вероятности того что произойдут определенные нежелательные события и отрицательно повлияют на достижение целей проекта. Анализ рисков включает оценку рисков и методы снижения рисков или уменьшения связанных с ним неблагоприятных последствий. Назначение анализа рисков дать потенциальным партнерам необходимые данные для принятия ре шений о целесообразности участия в проекте и выработки мер по защите от воз можных финансовых потерь. Анализ рисков можно...
32646. Методы снижения риска в проекте 465.5 KB
  Принципы выбора метода снижения риска Нельзя рисковать больше чем это может позволить собственный капитал; Надо думать о последствиях риска; Нельзя рисковать многим ради малого. Кр = У С где Кр коэффициент риска У максимально возможная сумма убытка; С объем собственных ресурсов с учетом точно известных поступлений средств. Методы снижения риска Распределение риска между участниками сделки долевое финансирование проектов Гарантии Лимитирование установление предельных сумм сделок кредита Резервные фонды Залог Модель управления...
32647. Контрактная работа над проектом 37 KB
  Контрактная стадия проекта открывает фазу реализации проекта и следует сразу за фазой предынвестиционных исследований за принятием решения о вложении инвестиций в проект. На этой стадии определяются все участники проекта контракторы отношения которых с заказчиком формализуются в контрактах. Определение потребности в ресурсах работах и услугах необходимых для реализации проекта. Определение потенциальных участников проекта контракторов и анализ их возможностей.
32648. Организация и проведение подрядных торгов для заключения контрактов по проектам 35 KB
  Организация и проведение подрядных торгов для заключения контрактов по проектам. Объект торгов производственный или непроизводственный объект к которому относится предмет торгов. Предмет торгов конкретные виды работ и услуг по которым проводятся торги. В качестве предмета торгов могут выступать подряды на: строительство реконструкцию и капитальный ремонт предприятий зданий сооружений производственного и непроизводственного назначения в том числе на условиях под ключ; выполнение комплексов строительных и монтажных работ и их...