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  

 Базовый тип

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

  [

  ]

 ,

 ..

Выражение

Выражение

Выражение


 

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

32359. Общие понятия о характере. Структура характера. Типология характера 13.96 KB
  Структура характера. Типология характера. В структуре личности характера занимает центральное место объединяя все другие свойства и особенности поведения: Влияет на познавательные процессы На эмоциональную жизнь На мотивацию и волю Определяет индивидуальность и своеобразие личности Характер человека сплав врожденных свойств высшей нервной деятельности с приобретенными в течении жизни индивидуальными чертами. Структура характера: Черты выражающие направленность личности устойчивые потребности установки интересы склонности идеалы цели...
32360. Групповая и совместная деятельность. Факторы эффективности групповой и совместной деятельности 15.38 KB
  Факторы эффективности групповой и совместной деятельности. Совместимость способность членов группы к совместной деятельности. Виды совместимости: Психофизиологическая определенное сходство характеристик людей и на этой основе согласованность их эмоциональных и поведенческих реакций синхронизация темпа совместной деятельности. Критерии оценки: Результаты деятельности.
32361. Психологическая готовность ребенка к школе. Методы диагностики психологической готовности к обучению в школе 13.85 KB
  Психологическая готовность ребенка к школьному обучению необходимый и достаточный уровень психического развития ребенка для освоения школьной учебной программы в условиях обучения в коллективе сверстников. Структура компоненты: Психоматорная готовность сбалансированность процессов возбуждения и торможения которая позволяет ребенку более длительное время сосредотачивать свое внимание способствует формированию произвольных форм поведения и познавательных процессов; развитие мелких мышц руки и зрительно моторных координаций что создает...
32362. Метод тестов 19.05 KB
  Тесты отличаются от других методов исследования тем что предполагают четкую процедуру сбора и обработки первичных данных а также своеобразную их последующему интерпретацию. Стал широко использоваться в психологии после публикации в 1980 работы Кетелла Умственные тесты и измерения которая была посвящена результатам тестирования студентов США. Виды тестов: По особенностям тестовых значений: вербальные невербальные По форме проведения: групповые индивидуальные В зависимости о наличия или отсутствия временных ограничений: скорости...
32363. Развитие супружеских отношений. Психологические аспекты отношений в браке. Динамика сексуальных отношений в браке 16.21 KB
  Модели семьи: Родительская модель индивид обучается супружескому поведению на основе идентификации родителей своего пола на основании поведения родителей противоположного пола строиться представление о том как должен вести себя партнер. В супружестве каждый из партнеров пытается приспособить свои реальные отношения с эталонными. Гармоничные отношения становятся возможными только в том случае если партнер своей внутренней программой напоминает родителей противоположного пола. В этом случае происходит перенос связей существовавших в...
32364. Психологические основы воспитания. Организация воспитания с учетом специфики различных категорий детей 13.68 KB
  Психология воспитания научает внутренние механизмы становления и развития личности в целом а также отдельные ее свойства. Воспитание социальное целенаправленное создание условий материальных духовных организованных для развития человека это целенаправленная деятельность призванная формировать у детей систему качеств личности взглядов и убеждений. Цели воспитания: Воспитание всесторонне и гармонично развитой личности сочетающей в себе духовное богатство моральную чистоту и физическое совершенство. Воспитание социально компетентной...
32365. Методы исследования в психологии 14.05 KB
  Метод это способ посредством которого познается предмет науки это способ получения фактов о проявлениях психологических особенностей человека. Являясь средством изучения фактов и закономерностей психики человека той или иной метод опирается на основные закономерности ее развития и функционирования и основан на методологии той науки в рамках которой он используется а методология это совокупность принципов. Психика человека представляет собой сложную психологическую систему в которой все процессы и функции тесно взаимосвязаны. а есть...
32366. Семья как малая социальная группа. Функции семьи. Конфликты в семье, их профилактика и разрешение 13.51 KB
  Функции семьи. Функции семьи деятельность членов семьи направленная на удовлетворение потребностей. Генеративная продолжение рода первичной социализации экономическая накопление богатства гедонистическая здоровый секс рекреационная совместный отдых рождение и воспитание детей; сохранение развитие передача последующим поколениям ценностей и традиций общества; удовлетворение потребностей в психологическом конфликте эмоциональной поддержке чувство безопасности значимости собственного Я; создание условий для развития личности...
32367. Классификация методов психологического исследования 14.31 KB
  Этапы психологического исследования: Постановка цели психологического исследования определение предмета исследования выработка рабочей гипотезы: Выявление проблемы Уточнение проблемы и характера затруднений сбор необходимой для этого информации беседа с учителями и родителями наблюдение за ребенком в проблемной и непроблемной ситуации Выявление социальных и биологических условий развития формальные характеристики состав семьи возраст образование и профессия родителей; физическое развитие и состояние здоровья ребенка группа...