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'.


 

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

22656. Явище дифракції світла. Дифракція Фраунгофера. Дифракція Френеля 1.35 MB
  Дифракція Фраунгофера. Дифракція Френеля. Дифракція світла – явище огинання світлом контурів тіл і відповідно проникнення світла в область геометричної тіні. Дифракція є проявом хвильових властивостей світла.
22657. Роздільна здатність оптичних приладів 70 KB
  Характеризує здатність давати зображення двох близько розташованих одна від одної точок об’єкта рознесених в просторі. Найменша лінійна кутова відстань між двома точками починаючи з якої їх зображення зливаються і не розрізняються наз. Релей ввів критерій згідно до якого: зображення двох точок можна розрізнити якщо дифр. Предмет знаходиться на а зображення утворюється в фокальній площині об`єктива телескопа з фокусною відстанню f .
22658. Принципы объединения сетей на основе протоколов сетевого уровня 138.5 KB
  Протоколы сетевого уровня реализуется, как правило, в виде программных модулей и выполняются на конечных узлах-компьютерах, называемых хостами, а также на промежуточных узлах-маршрутизаторах, называемых шлюзами. Функции маршрутизаторов могут выполнять как специализированные устройства, так и универсальные компьютеры с соответствующим программным обеспечением.
22659. Інтерференція поляризованих променів при проходженні через кристали 89 KB
  Світло поширюється вздовж вісі OZ. Ніколь N1 забезпечує лінійно поляризоване світло в площині XOY. На пластинку падає лінійно поляризоване світлоко де розпадається на звичайний і незвичайний промені.векторів звичайної і незвичайної хвиль на вході в пластинку у вигляді: де різниця фаз між звичайним і не звичайним променями Склавши два останні рівняння отримаємо Розглянемо два випадки: 1 еліптично поляризоване світло.
22660. Явища обертання площини поляризації падаючого світла в речовинах 359 KB
  Явища обертання площини поляризації падаючого світла в речовинах Відомо що світло – це поперечна хвиля тобто вона розповсюджується у напрямку  до площини що утворюють вектори E та H. Частковим випадком еліптичної поляризації є колова поляризація. Деякі речовини при проходженні через них світла можуть змінювати площину поляризації. Це пояснюється поворотом площини поляризації що здійснюється оптично активним зразком схема: Джерело – поляризатор – зразок – аналізатор Розглянемо явище у різних середовищах: 1 Усі одновісні оптично активні...
22661. Основні закони випромінювання. Ф-ла Планка 381 KB
  Основні закони випромінювання. Закон СтефанаБольцмана для ачт : M=σT4 де М – енергетична густина випромінення σконстанта Стеф. Закон зміщення Віна: Tλmax=b де bconst яка не залежить від темпер. Класичній підхід: ймовірність що енергія моди лежить в проміжку тоді отримуємо формулу РелеяДжинса: ; Планк: тоді: формула Планка З формули Планка можна отримати закон зміщення Віна і М Т4 при Закон Кіргофа: спектральна випромінююча здатність поглинаюча здатність Це відношення не залежить від природи...
22662. Квантування енергії лінійного гармонічного осцилятора 75 KB
  Модель гармонічного осцилятора : частинка коливається навколо положення рівноваги тоді ми можемо розкласти наш потенціал в ряд поблизу положення рівноваги x0=0. Тоді гамільтоніан для такої системи буде Щоб перейти від класичної системи до квантової необхідно від фізичних величин перейти до операторів тоді . Щоб його розв’язати необхідно перейти до безрозмірних змінних тоді Розглянемо асимтотики цього рівняння: отримуєм при . Тоді підставляючи цей вираз у рівняння для U і роблячи деякі перетворення можна отримати вираз для...
22663. Явище радіоактивності. Види радіактивного розпаду 27.5 KB
  Види радіактивного розпаду. Ядра що підлягають такому розпаду наз. В процессі розпаду у ядра може змінюватись як атомний номер Z так і масове число A. Фізичною характеристикою розпаду є середній час життя ядер.
22664. γ – випромінювання та ефект Месбауера 46 KB
  γ – випромінювання та ефект Месбауера Явище γ – випромінювання ядер полягає в тому що ядро випромінює γ – квант без зміни А кількість нуклонів та Z кількість протонів. Гама – випромінювання виникає за рахунок енергії збудження ядра. Спектр γ – випромінювання завжди дискретний через дискретність ядерних рівнів. Особливо інтенсивне γ – випромінювання з’являється коли β – розпад у високій степені заборонений в основний стан кінцевого ядра і дозволений в один із збуджених станів.