Then

for i from n downto p do

А[i]: = А[р]+i‑р+1 {увеличение элементов} end for end if end while

Заметим, что в искомой последовательности n‑элементиых подмножеств (каждое из которых является возрастающей последовательностью n чисел из диапазона l..m) вслед за последовательностью (a_i,…, a_n) следует последовательность

(b₁,…, b_n) = (а₁…, a_p-1, а_{р+ 1}, а_{р + 2},…, а_{р + n-р +1}), где р – максимальный индекс, для которого b_n = а_{р + n - р + 1} m. Другими словами, следующая последовательность получается из предыдущей заменой некоторого количества элементов в хвосте последовательности на идущие подряд целые числа, но так, чтобы последний элемент не превосходил n, а первый изменяемый элемент был на 1 больше, чем соответствующий элемент в предыдущей последовательности. Таким образом, индекс р, начиная с которого следует изменить «хвост последовательности», определяется по значению элемента А[n]. Если А[n] < m, то следует изменять только А[n], и при этом р: = n. Если же уже А(n) = m, то нужно уменьшать индекс р: =р – 1, увеличивая длину изменяемого хвоста.

2.1.4 Представление множеств в приложениях на Delphi

Тип множество задает неупорядоченную совокупность неповторяющихся объектов. Переменная типа множество – это совокупность объектов из исходного заданного множества – может иметь значение «пусто» (пустое множество). Число элементов исходного множества ограничено – оно не может быть более 256. Для задания элементов множества может использоваться любой порядковый тип, однако порядковые номера элементов множества, т. е. значения функции ord, должны находиться в пределах от 0 до 255. Для задания типа множества используется следующее объявление [22]:

Type <Имя> = set of <тип элементов>;

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

Type A = set of Char; A1 = set of ‘A’.’Z’;

Oper = set of (Plus, Minus, Mult, Divide);

Number = set of Byte; D = set of 1..20;

Для переменных типа множество можно задавать типизированные константы. При этом значения задаются в виде конструктора множества.

Const K:D = [5,9,11,17]; R:D = [1.. 9,13,20];

Для задания значений переменным типа множество также можно использовать конструкторы. Пусть объявлено

Var AA:A;, тогда возможна запись (тип A объявлен выше)

AA:=[Char(13), Char(7), ‘0’, ‘Q’];

Если требуется присвоить этой переменной значение «пусто», то используется такой конструктор: AA:= [];

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

Как и для других типов, имеется ряд встроенных операций для типа множество. Пусть заданы следующие типы и переменные: Type Mn = set of 1..50; Var A, B, C: Mn;

Пусть переменным присвоены значения:

A:= [3,5,9,10]; B:= [1,7,9,10];

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

C:=A+B; {1,3,5,7,9,10}

Разность (A-B <> B-A)

C:=A-B; {3,5}

C:=B-A; {1,7}

Пересечение (умножение)

C:=A*B; {9,10}

Проверка эквивалентности, например в операторе IF

(A = B) {False}

Проверка неэквивалентности

(A <> B) {True}

Проверка, является ли одно множество подмножеством другого

(A>=B) {False}

(A<=B) {False}

Проверка, входит ли заданный элемент в заданное множество

(3 in A) {True}

(3 in B) {False}

Стандартные подпрограммы для выполнения некоторых действий над множествами

Exclude (A, 3); удалить из множества A элемент 3}

Include (A, 3); {вставить элемент 3 в множество A}.

2.1.5 Характеристический вектор множества

Характеристическим вектором Vx множества X, заданного на универсальном множестве I, является вектор, содержащий 0 и 1. Количество элементов в векторе Vx равно количеству элементов в универсальном множестве, причём, 1 записывается в случае, если элемент присутствует и в универсальном множестве I, и в множестве X, в противном случае записывается 0. Некоторые задачи с множествами, особенно на компьютере, удобно решать, используя характеристические векторы [1].

Действия над векторами похожи на логические операции.

Над характеристическими векторами выполняются поразрядно логические операции:

при пересечении – логическое умножение;

при объединении – логическое сложение;

при нахождении дополнения – значения в исходном векторе изменяются на противоположные.

При объединении множеств  элементы характеристического вектора считают по правилу:

2) При пересечении множеств  элементы характеристического вектора считают по правилу:

3) При нахождении дополнения  нули меняют на единицы, единицы – на нули;

4) При нахождении симметричной разности , используют формулу:

Пример 2.5 Пусть I = {1, 2, 3, 4, 5, 6}, А={1, 2, 4, 5} и В={3, 5} Характеристическим вектором множества А является вектор а = (1, 1, 0, 1, 1, 0). Характеристический вектор множества В равен b = (0, 0, 1, 0, 1, 0).

Вычислим характеристический вектор множества A U . Он равен

а или (не b) = (1, 1, 0, 1, 1, 0) или (1, 1, 0 1, 0, 1) = (1,1,0,1,1,1).

Следовательно, A U = {1, 2, 4, 5, 6}.

Характеристический вектор множества А Δ В равен

(а и (не b)) или (b и (не а)) = ((1, 1, 0, 1, 1, 0) и (1, 1, 0, 1, 0, 1)) или

или ((0, 0, 1, 0, 1, 0) и (0, 0, 1, 0, 0, 1)) = (1, 1, 0, 1, 0, 0) или (0, 0, 1, 0, 0, 0) = (1, 1, 1, 1, 0, 0).

Таким образом, А Δ В = {1, 2, 3, 4}.

2.2 Практическая часть

2.2.1 Задание к работе

1. Изучить теоретический материал, включая и дополнительные сведения, представленные в теоретической части.

2. Задать самостоятельно универсальное множество X, множества A, B, C (или некоторые из них, т. к. в некоторых вариантах используются только два множества).

3. Cформировать характеристические векторы для исходных множеств и получить результирующее множество (по варианту), используя характеристические вектора.

4. Вычислить элементы результирующего множества (по варианту), используя операции над множествами.

5. Вывести результаты, полученные в пункте 3 и пункте 4.

6. Сравнить эти результаты и сделать выводы.

7. Пункты 3 и 4 выполнить двумя способами: аналитически и реализовать в виде приложения на Delphi.

Примечание:

1. Если в выражении используется операция разности или симметрической разности, то при выполнении действий с характеристическими векторами (пункт 3) заменить их другими операциями на множествах (использовать формулы из лекций и [23]).

2. При выполнении пункта 4 операцию симметрической разности заменить другими операциями, которые используются в Object Pascal.

3. В качестве дополнительного задания предлагается реализовать любой описанный в теоретической части алгоритм в виде приложения на Delphi.

2.2.2 Примеры выполнения

Пример 1.

1) Задание по варианту

I:={1,2,3,4,5,6,7}

Значения векторов A, B, C берутся произвольно, но с учетом, что количество элементов не должно быть больше 7.

Найти: характеристический вектор множеств A, B и C, характеристический вектор множества D – Vd, перейти от Vd к D.

2) Создать приложение в среде Delphi, которое решит данную задачу.

3) Решить задачу аналитически.

4) К защите данной работы необходимо знать теоретический материал по данной теме из лекций и методички, а также ответить на «Вопросы для самопроверки».

D=

Аналитическое решение:

Характеристические векторы

A:={1,0,1,0,1,0,1}

B:={1,1,1,1,0,0,0}

C:={1,0,1,1,1,0,1}

Переходим от  к D

D:= ={1,3}

Форма

Рисунок 2.10 – Формы с результатами

Код программы

implementation

procedure TForm1. Button1Click (Sender: TObject);

var

n, A, B, C: set of char;

s, s1, s2, s3, s11, s22, s33, s4, s44, s5, s55:string;

i:integer;

begin

s:='1234567';

n:=['1'..'7'];

A:=['1', '3', '5', '7'];

B:=['1', '2', '3', '4'];

C:=['1', '3', '4', '5', '7'];

begin

for i:=1 to 7 do

begin

if (s[i] in A) then

s1:=s1+'1'

else

s1:=s1+'0';

end;

s11:=' {'+s1+'}';

label7. Caption:=s11;

end;

begin

for i:=1 to 7 do

begin

if (s[i] in B) then

s2:=s2+'1'

else

s2:=s2+'0';

end;

s22:=' {'+s2+'}';

label12. Caption:=s22;

end;

begin

for i:=1 to 7 do

begin

if (s[i] in C) then

s3:=s3+'1'

else

s3:=s3+'0';

end;

s33:=' {'+s3+'}';

label13. Caption:=s33;

{Задаем характеристические векторы}

end;

begin

for i:=1 to 7 do

if((s1 [i])=(s2 [i])) and ((s3 [i])=(s2 [i])) and ((s3 [i])='1') then

s4:=s4+'1' else

s4:=s4+'0';

s44:=' {'+s4+'}';

label17. Caption:=s44;

{Находим Характеристический вектор

множества Vd}

end;

begin

for i:=1 to 7 do

if s4 [i]='1' then

s5:=s5+inttostr(i);

s55:=' {'+s5+'}';

label21. Caption:=s55;

{Переходим от Vd к D}

end;

end;

procedure TForm1. Button2Click

(Sender: TObject);

begin

close;

end;

end.

Похожие работы

Дискретная математика

Скачать

11313

1

5

... Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельным. Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики … Если универсальное множество состоит из n элементов, то число подмножеств = 2n. Если , состоящее из элементов E, не принадлежащих А, называется дополненным. Множество можно задать: ...

Конспект по дискретной математики

Скачать

6003

0

1

в и формальных систем является центральной в дисциплине. В настоящие время от нее возникли ответвления, например, разработка алгоритмических языков программирования.Одной из важнейших проблем в дискретной математики является проблема сложности вычислений.Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно ...

Решение практических заданий по дискретной математике

Скачать

14778

4

22

... которой были разработаны в последней четверти 19 века Георгом Кантором. Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания. Задание 1 Представить с помощью кругов Эйлера множественное выражение . Используя законы и свойства алгебры множеств, упростить заданное ...

Применение методов дискретной математики в экономике

Скачать

34329

6

25

элементы теории нечетких множеств можно применять для решения экономических задач в условиях неопределённости. 1. применение Логических функций   1.1 Применение методов дискретной математики в экономике   При исследовании, анализе и решении управленческих проблем, моделировании объектов исследования и анализа широко используются методы формализированного представления, являющегося предметом ...