Смекни!
smekni.com

Основы дискретной математики (стр. 12 из 23)

р:=n {можно увеличить последний элемент} end if if p

1 then

for i from n downto p do

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

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

(b1,…, bn) = (а1…, ap-1, ар+ 1, ар + 2,…, ар + n-р +1), где р – максимальный индекс, для которого bn = ар + 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;

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