Основы дискретной математики (стр. 12 из 23)
р:=n {можно увеличить последний элемент} end if if p
1 thenfor 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}
Переходим от
к DD:=
={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;
{Задаем характеристические векторы}