Что такое set of integer

9

Урок 89 — Множества

От рассмотрения простых типов данных переходим к более сложным наборам данных. Следует вспомнить, что простые типы данных позволяют хранить одно-единственное значение в одной переменной. Структуры данных позволяют хранить сразу несколько значений, причём некоторые такие структуры теоретически вообще не имеют ограничения на количество значений — этот предел определяется лишь объёмом доступной памяти. Сегодня мы поговорим о множествах.

Математическое понятие множества

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

Множества в Delphi

Понятие множества в языке программирования несколько отличается от математического определения этого понятия, но смысл сохраняется. Основное отличие в том, что в программировании множество может содержать только конечное число элементов, т.е. не может состоять из бесконечного числа объектов. В математике же последнее допустимо. Например, мы можем определить множество натуральных чисел, которое бесконечно: N =

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

Перейдём ближе к делу. Множество может быть построено на основе перечислимого типа данных (кто забыл — открываем предыдущий урок). Например, на основе символьного типа Char. По-английски множество называется set (набор) и именно этим словом описывается в Delphi:

В данном примере мы объявили множество A на основе символьного типа Char.

Запомните: множество не может состоять более чем из 255 элементов!

Например, следующее описание:

приведёт к ошибке "Set base type out of range".

Задание множеств

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

Чтобы задать множество, мы можем воспользоваться операцией присваивания, где слева стоит переменная-множество, а справа — нужный нам набор. Например, в описанное выше множество A мы хотим поместить элементы-символы A, B, C, D. Тогда это запишется так:

Теперь множество A содержит 4 элемента.

Если вспомнить, что тип данных Char упорядочен, то данную запись можно сократить следующим образом:

Мы просто указали диапазон значений, который должен находиться во множестве. Результаты одинаковый, но вторая запись короче и красивее. Допустимы, конечно же, комбинации диапазонов и отдельных значений:

Помните, что множество — это виртуальный набор элементов: множество нельзя ввести с клавиатуры и точно так же нельзя вывести на экран. Поэтому добавление элементов во множество делается только программным путём. Безусловно, вы каким-либо образом можете связать элементы интерфейса программы и операцию добавления элементов во множество, но напрямую ввести множество нельзя. Аналогично, вы можете показать множество на экране с помощью каких-либо элементов (например, флажков TCheckBox), но само множество "в чистом виде" вывести нельзя.

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

В программировании, как и в математике, над множествами допустимы некоторые операции. Рассмотрим их.

Находится ли элемент во множестве?

Самая простая операция, для понятия смысла которой даже не нужно задумываться. Чтобы проверить, входит ли элемент во множество, следует использовать специальную конструкцию с оператором in. Слева от него указывается элемент, справа — множество. Результатом, как несложно догадаться, является логичное значение — истина или ложь. True — элемент принадлежит множеству, False — не принадлежит:

Несложно проверить, что сообщение в данном случае появится на экране.

Объединение множеств

Если есть два множества, определённые на одном и том же типе данных, то их можно объединить и получить таким образом новое множество.

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

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

Объединение записывается знаком плюс "+". Пример:

Включение одного элемента во множество делается точно таким же образом, просто в этом случае включаемое множество содержит всего один элемент.

Пересечение множеств

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

Пересечение обозначается звёздочкой "*". Пример:

Разность множеств

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

Следует обратить внимание, что порядок множеств в данном случае важен, т.е. X-Y и Y-X — это разные множества.

Применение множеств

Множества находят широкое применение. С помощью множеств удобно задавать набор опций, каждая из которых либо включена, либо выключена. К примеру, поместите на форму кнопку (TButton), перейдите в инспектор объектов, разверните свойство Font (шрифт) и найдите свойство Style. Вот это свойство как раз и реализовано множеством. Во множестве 4 элемента: fsBold, fsItalic, fsUnderline и fsStrikeOut, каждый из которых отвечает за стиль шрифта. Принадлежность элементов ко множеству задаётся указанием значения True или False для каждого из этих пунктов. В строке "Style" находится описание данного множества. Попробуйте изменять стиль и посмотреть, как меняется описание множества Style.

А теперь давайте сделаем простенький интерфейс для доступа к этому свойству. Пусть будет меняться стиль шрифта у этой кнопки (Button1). Поместим на форму 4 TCheckBox — для доступа ко всем значениям и дадим им соответствующие имена. Изменение стиля будем делать при нажатии на саму эту кнопку. Пример реализации:

Чтобы не повторять везде одно и то же "Button1.Font.", эту часть кода можно, что называется, вынести за скобку при помощи специального оператора with. Ранее речь о нём не шла, однако этот оператор очень удобен. Смысл его прост: то, что вынесено вперёд, автоматически применяется ко всему, что находится внутри данного блока. В нашем случае будет так:

Согласитесь, так гораздо удобнее. Используйте оператор with как можно чаще — с его помощью и код по объёму становится меньше и скорость работы увеличивается.

У большинства компонент среди свойств можно найти множества. Например, у диалога открытия файла TOpenDialog (вкладка Dialogs) множеством представлено свойство Options, которое содержит приличное число элементов.

Что такое set of integer

В Паскале Множество — совокупность неупорядоченных данных указанного (базового) типа. Базовый тип:

Поэтому, базовым типом множества не может быть ни Real (не порядковый тип), ни типы ShorInt, Integer, LongInt или Word (несовпадение диапазонов).

Переменная типа множество может принимать как все значения множества, так и ни одного.

Любой множественный тип может принимать значение [], которое называется пустым множеством.

Множество можно описать тремя способами:

Примеры описания массивов

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

Над множествами возможны операции:

Операция объединения: С:=А+В

Операция пересечения: С:=А*В

Операция разности: С:=А-В

Операция равенства(совпадения) множеств: С=В

Операция неравенства: C <> B

Операция проверки на вхождение множества в множество: A ⇐ B — включено ли А в В;

Операция проверки на вхождение элемента в множество (in): С in B — входит ли элемент С в множество В

Решу Паскаль

Множества в языке Паскаль: описание, хранение, операции, вывод, использование

Когда мы произносим слово множество, подразумеваем большое количество объектов:

• множество целых чисел,
• множество латинских букв,
• множество слов.

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

Множество — это набор уникальных неупорядоченных значений одного типа.

Описание (объявление) множества

var m:set of базовый тип;

Примеры

Целые числа

Описание
в блоке var

m : set of integer ;

s : set of string ;

Хранение данных в множестве

m:=[3,4,6,8,9]; элементы множества заключаются в квадратные скобки и перечисляются через запятую

m:=[0..9]; диапазон значений через две точки

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

• пересечение
• объединение
• вычитание

Применение операций над множествами

m2:=m*m1; пересечение [3,4,9]

m2:=m+m1; объединение [3,4,6,8,9,15,20]

m2:=m1-m; разность [15,20]

Пустое множество

Как добавить значение в множество

m:=m+[x]; значение переменной x добавили в множество m

Операция вхождения in

Обратиться к элементу множества непосредственно нельзя. Но можно использовать операцию вхождения in.

Вывод множества на экран

for k:=10 to 24 do

if k in m then write(k); //если значение k принадлежит множеству m, то вывести k

В версии PascalABC.NET 3.8.2 множество можно вывести целиком:

Результат будет таким:

Использование множеств в задачах

Задача 1. Дано натуральное число. Сформировать множество его цифр (найти различные цифры числа)

В цикле while будем разбивать число на цифры и добавлять цифру в множество.

Исходные данные: n – натуральное число (тип integer)

Промежуточные данные: d – цифра числа (тип integer)

Выходные данные: m – множество цифр числа

Программа решения на языке Паскаль

var m:set of integer;

m:=[]; //пустое множество

writeln(‘Введите натуральное число’);

writeln(‘Множество цифр числа’);

Результат выполнения программы

Задача 2. Дан алфавит строчных русских букв, получить множество согласных букв вычитанием множества гласных букв.

Воспользуемся тем, что char является порядковым типом данных, в качестве букв алфавита возьмем множество b:=[‘а’..’я’] .

Множество гласных букв получим перечислением: g:=[‘у’,’е’,’ы’,’а’,’о’,’э’,’я’,’и’,’ю’]

Множество согласных букв получим вычитанием s:=b-g;

b – множество строчных русских букв

g – множество строчных гласных букв

Выходные данные: s – множество строчных согласных букв

Программа решения на языке Паскаль

var b,g,s:set of char;k:char;

if k in s then write(k,’ ‘);

Задача 3. Дана строка символов. Сколько в этой строке символов цифр?

Будем проверять принадлежность символа строки множеству символов цифр [‘0’..’9′] и копить счетчик.

Программа решения на языке Паскаль

for k:=1 to length(s) do

if s[k] in m then t:=t+1;

writeln(‘Символов цифр в строке: ‘,t);

Еще одна задача на применение операции вхождения in. Как проверить, есть ли в строке заданная подстрока.

Результат выполнения программы

Задача 4. Как найти все уникальные (неповторяющиеся) значения в массиве чисел?

Мы знаем, что множество хранит уникальные значения. Возьмем пустое множество.

Если в множестве нет значения, равного элементу массива, то добавим значение этого элемента в множество. Таким образом, в множестве сохранятся значения элементов массива, и они будут уникальными.

Программа решения на языке Паскаль

var a:array[1..100] of integer;

m:set of integer;

writeln(‘Введите количество элементов массива’);

m:=[]; //пустое множество

a[k]:=random(1,10);//случайные числа из промежутка [1;10]

if not(a[k] in m) then //если значения элемента a[k] нет в множестве

m:=m+[a[k]]; //добавить значения элемента a[k] в множество m

writeln(‘Уникальные элементы массива’);

for k:=1 to 10 do //цикл по числам из промежутка от 1 до 10

if k in m then write(k,’ ‘); //если число k принадлежит множеству, вывести число k

// либо вывод сразу всего множества write(m), цикл for k:=1 to 10 do тогда не нужен

Pascal Programming/Sets

This chapter introduces you to a new custom data type. Sets are one of the basic structured data types. When programming you will frequently find that some logic can be modeled with sets. Learning and mastering usage of sets is a key skill, since you will encounter them a lot in Pascal.

Contents

Basics [ edit | edit source ]

Notion [ edit | edit source ]

See also the chapter Sets in Algebra.

Sets are (possibly empty) aggregations of distinguishable objects. Either a set contains an object, or it does not. An object being part of a set is also referred to as element of that set.

Let’s say we know the objects “apple”, “banana” and “pencil”. The set Fruit ≔ <“apple”, “banana”>contains the objects “apple” and “banana”. “Pencil” is not a member of the set Fruit.

Digitization [ edit | edit source ]

When a computer is supposed to store and process a set, it actually handles a series of Boolean values. [fn 1] Every one of those Boolean values tells us whether a certain element is part of a set.

Sets in Pascal [ edit | edit source ]

The computer needs to know how many Boolean values it needs to set aside. In order to achieve this, a set in Pascal requires an ordinal type as a set’s base type. An ordinal type always has a finite range of permissible discrete values, thus the computer knows beforehand how many Boolean values to reserve, how many elements we can expect a set contain at most. In consequence, a valid set type declaration is:

A variable of the data type characters can only contain char values. This set cannot contain, for instance, 42 , that is an integer value, nor is this information stored in any way.

Remember, in order to qualify as an ordinal data type there must be a means to assign every legal value an integer value. [fn 2]

Sets are particularly useful in conjunction with enumeration data types, which you just learned in previous chapter. Let’s consider an example in Pascal:

Here, we have declared a variable slob , which represents a set of the skill enumeration data type values. In the penultimate line we populate our set slob with two objects, videogames and eating . The brackets indicate a set literal. [ videogames , eating ] is a set expression which we are assigning to the slob variable.

The set variable slob contains no other objects. However, the computer still stores five Boolean values for every potential member of that set. The number five is number of elements in skill , the set’s base type. The information that cooking , cleaning and driving are not part of the set slob is stored explicitly (by the proper Boolean value false ).

Inspecting a set [ edit | edit source ]

If we want to learn, whether a certain object is part of a set, the set operator in yields the corresponding Boolean value the computer uses to store that information.

Even though we, as humans, can say that 42 in slob is wrong, i. e. false , such a comparison is illegal. Per definition, the slob set can only contain skill values.

Operations [ edit | edit source ]

So far, sets probably seemed like a really complicated way for using Boolean values. The true power of sets lies in a number of distinct operations, making sets an easier, and thus better alternative to handling two or more individual (but related) Boolean values directly.

Combinations [ edit | edit source ]

In Pascal, two sets of the same kind, the same data type, can be combined forming a new set of the respective data type. Following operators are available:

_{†  The symmetric difference operator is only defined in EP .}

Union [ edit | edit source ]

In a Venn diagram both circles represent a (positive) number of objects belonging to either or both sets. The red area represents the result of a union.

The result of unifying two sets into one is called union. Let’s say, recently our slob has learned how to drive and does that now too. This can be written as:

Now, slob contains all objects it previously held, plus all objects from the other set, [ driving ] .

Difference [ edit | edit source ]

difference as a Venn diagram: right circle “minus” left circle

Of course sets can be deprived of a set of elements by using the difference operator, in source code written as — .

This removes all objects present in the second set from the first set. Here, the empty set ( [] ) does not contain any objects, thus removing no objects has virtually no effect on slob .

Intersection [ edit | edit source ]

intersection as a Venn diagram: the overlapping area, if any, here colored in red, represents the intersection

Furthermore you can intersect sets. The intersection of two sets is defined as the set of elements both operands contain.

The set common now (only) contains driving and eating , because those are the objects member of both operands, of both given sets.

Symmetric difference [ edit | edit source ]

symmetric difference as a Venn diagram

A disjunct result to the intersection gives the symmetric difference. It is the union of the operands without the elements contained in both sets.

Now unique is [ cooking , cleaning , videogames ] , because those are the values from either set, but not both.

Comparisons [ edit | edit source ]

Two sets of the same kind, the same data type, can be compared by looking at each element in both sets.

All comparison operators, as before, evaluate to a Boolean expression.

Inclusion [ edit | edit source ]

The inclusion of a two sets means that all objects one set contains are present in another set. If the expression A <= B evaluates to true , all objects present in the set A are also present B . In a Venn diagram you will notice that one circle’s area is completely surrounded by another circle, if not identical to the other circle.

Equality and inequality [ edit | edit source ]

The equality of two sets is defined as A <= B and B <= A . All objects contained in the left-hand set are present in the right-hand set and vice versa. In other words, there is not a single object that is present in just one of the sets. The inequality is just the negation thereof.

Element of [ edit | edit source ]

The in operator is the only set operator that does not act on two sets but on one potential set member candidate and a set. It has been introduced above. With respect to Venn diagrams, though, you can say that the in operator is “like” pointing with your index finger to a point inside a circle, or outside of it.

Pre-defined set routines [ edit | edit source ]

Cardinality [ edit | edit source ]

(After initialization) at any time a set contains a certain number of elements. In mathematics the number of objects being part of a set is called cardinality. The cardinality of a set can be retrieved using the function card , an EP extension.

This will print 0 as there are no elements in an empty set.

Unfortunately, not all compilers implement the card function. The FPC does not have none. The GPC does supply one, though.

Universe [ edit | edit source ]

Originally, Wirth proposed a function all :

[1]

The set superwoman would contain all available skill values, cooking , cleaning , driving , videogames , eating .

Inclusion and exclusion [ edit | edit source ]

The procedures allow you to quickly add or remove one object from one set.

is identical to

but you do not need to type out the set name twice and everything, thus reducing the chance of typing mistakes. Likewise,

will do the same as

Intermediate usage [ edit | edit source ]

Set literals [ edit | edit source ]

Effectively stating sets is a required skill when handling sets. It is important to understand that sets merely store the information that an object is a member of a set, or not. The set [ 'A' , 'A' , 'A' ] is identical to [ 'A' ] . Specifying 'A' multiple times does not make it “more” part of that set.

Also, it is not necessary to list all members in any particular order. [ 'X' , 'Z' , 'Y' ] is just as acceptable as [ 'X' , 'Y' , 'Z' ] is. Mathematically speaking, sets are not ordered. Pascal’s requirement that a set’s base data type has to be an ordinal type is purely a technical requirement. For readability reasons it is usually sensible, though, to list elements in ascending order.

Set literals are always a positive statement which objects are in a set. If we wanted a set of integer values between 0 and 10 without 3 , 5 and 7 , but do not want to write this set out entirely (i. e. as [ 0 , 1 , 2 , 4 , 6 , 8 , 9 , 10 ] ), you can either write [ 0 .. 2 , 4 , 6 , 8 .. 10 ] or the expression [ 0 .. 10 ] — [ 3 , 5 , 7 ] . The latter is probably a little easier to grasp what objects are and which are not in the final set.

Memory restrictions [ edit | edit source ]

Although a set of integer is legal and complies with all Pascal standards, many compilers do not support such large sets. Per definition, a set of integer can contain (at most) all values in the range — maxInt .. maxInt . That is a lot (try writeLn ( maxInt ) or read your compiler’s documentation to find out this value). On a 64‑bit platform this value (usually) is 2 63 −1, i. e. 9,223,372,036,854,775,808. As of the year 2020 many computers will quickly run out of main memory if they attempted to hold that many Boolean values.

Loops [ edit | edit source ]

Now that you have made the acquaintance of enumeration data types and sets, you see yourself faced with dealing a growing number of data. Pascal, like many other programming languages, support a language construct called loops.

Characteristics [ edit | edit source ]

Loops are (possibly empty) sequences of statements that are repeated over and over again, or even never, based on a Boolean value. The sequence of statements is termed loop body. The loop head contains (possibly implicitly) a Boolean expression determining whether the loop body is executed. Every time the loop body is run, an iteration is in progress.

The term loop originates from the circumstance that some early models of computers required programs to be fed (“loaded”) via punched paper tape. If a portion of that paper tape was meant to be processed multiple times, that piece of paper tape was cut, bent and temporarily fixated so it formed a physical loop. Thankfully, advancements in computer technology has made it far more convenient to handle repeating code.

Pascal (and many other programming languages) differentiate between two groups of loops:

• counting loops, presented here, and
• conditional loops, presented in a chapter to come.

Counting loops have in common that, before running the first iteration it can already be determined how many times the loop body will be executed just by evaluating the loop head. [fn 3] Conditional loops on the other hand are based on an abort condition, i. e. a Boolean expression. Except for infinite loops, there is no way to tell in advance how many times, how many iterations a conditional loop will have without thoroughly (mathematically) analyzing the loop body and loop head, and possibly even considering circumstances beyond the loop.

Counting loops [ edit | edit source ]

Counting loops do not necessarily count a quantity. They are named after the fact that they employ a variable, a counting variable. This variable of any ordinal data type (de facto) assigns every iteration a number.

A counting loop is introduced by the reserved word for :

After for follows a specially crafted assignment to the counting variable.

Range of counting variable [ edit | edit source ]

1 to 10 (with the auxiliary reserved word to ) denotes a range of values the counting variable i will assume while executing the loop body. 1 and 10 are both expressions possessing the counting variable’s data type, that means there could also appear variables or more complex expressions, not just constant literals as shown.

This range is like a set . It may possibly be empty: The range 5 to 4 is an empty range, since there are no values between  5 up to and including  4 . In consequence, the counting variable will not be assigned any value out of this empty range, as there simply are none available, and the loop body is never executed. Nevertheless, the range 8 to 8 contains exactly one value, i. e.  8 .

During the first iteration the corresponding counting variable, here  i , will have the first value out of the given range, the start value, in the example above this is the value 1 . In the successive iteration the variable i has the value  2 , and so forth up to and including the final value of the given range, here  10 .

Immutability of counting variable [ edit | edit source ]

Reverse direction [ edit | edit source ]

Pascal also allows for ‑loops in a reversed direction using the reserved word downto instead of to :

Here, the range is 'Z' down and including to 'B' . The loop’s terminating condition is still counting variable ≠ final value , but in this case the counting variable  c becomes  pred ( c ) (not  succ ) at the end of each iteration, after the loop body has been executed.

Loops on collections [ edit | edit source ]

Note, unlike the counting loops above, you are not supposed to make any assumptions about the order the loop variable is assigned values to. It may be in ascending, descending, or completely mixed up “order”, but the specific order is “implementation defined”, i. e. it depends on the used compiler. Accompanying documents of the compiler explain in which order the for … in loop is processed.