Основы дискретной математики
Сущность сортировки данных, ее особенности, оценка времени исполнения. Порядок представления множеств на компьютере, в программах и приложениях Delphi. Исследование логических функций и методы их минимизации. Моделирование работы узлов с помощью Excel.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | учебное пособие |
| Язык | русский |
| Дата добавления | 29.04.2009 |
| Размер файла | 2,9 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Алгоритм построения бинарного кода Грея
Данный алгоритм генерирует последовательность всех подмножеств n_элементного множества, причем каждое следующее подмножество получается из предыдущего удалением или добавлением одного элемента.
Алгоритм 1.2: Алгоритм построения бинарного кода Грея Вход: n 0 - мощность множества
Выход: последовательность кодов подмножеств В
В: array [l..n] of 0..1 {битовая шкала для представления подмножеств}
for i from 1 to n do
B[i]: = 0 {инициализация} end for
yield В {пустое множество}
for i from I to 2n - 1 do
p: = Q(i) {определение элемента, подлежащего добавлению или удалению}
B[р]: = 1 - В[р] {добавление или удаление элемента}
yield В {очередное подмножество} end for
proc Q(i) {количество 2 в разложении i на множители + 1} q: = l; j: = i while j четно do
j:=j/2; q: = q + l end while return q end proc
Обоснование
Для n = 1 искомая последовательность кодов суть 0,1. Пусть есть искомая последовательность кодов В1,…, для n = к. Тогда последовательность кодов B10,…, 0, 1, …. B11 будет искомой последовательностью для n = к + 1. Действительно, в последовательности B10,…, 0, 1,…, В11 имеется 2k+1 кодов, они все различны и соседние различаются ровно в одном разряде по строению. Именно такое построение и осуществляет данный алгоритм. На нулевом шаге алгоритм выдает правильное подмножество В (пустое). Пусть за первые 2k - 1 шагов алгоритм выдал последовательность значений В. При этом В [k + 1] = В [k + 2] = * * * = В[n] = 0. На 2 k_ом шаге разряд В [k + 1] изменяет свое значение с 0 на 1. После этого будет повторена последовательность изменений значений В [1. k] в обратном порядке, поскольку Q (2k + m) = Q (2k - m) для
Пример 2.4
Таблица 2.5 - Протокол выполнения алгоритма 1.2 для п = 3
|
i |
Р |
В |
|||
|
0 |
0 |
0 |
|||
|
1 |
1 |
0 |
0 |
1 |
|
|
2 |
2 |
0 |
1 |
1 |
|
|
3 |
1 |
0 |
1 |
0 |
|
|
4 |
3 |
1 |
1 |
0 |
|
|
5 |
1 |
1 |
1 |
1 |
|
|
6 |
2 |
1 |
0 |
1 |
|
|
7 |
1 |
1 |
0 |
0 |
Представление множеств упорядоченными списками
Если универсум очень велик (или бесконечен), а рассматриваемые подмножества универсума не очень велики, то представление с помощью битовых шкал не является эффективным с точки зрения экономии памяти. В этом случае множества обычно представляются списками элементов. Элемент списка при этом представляется записью с двумя полями: информационным и указателем на следующий элемент. Весь список представляется указателем на первый элемент.
elem = record
i: info; {информационное поле}
n: elem {указатель на следующий элемент} end record
При таком представлении трудоемкость операции составит O(n), а трудоемкость операций составит О(nm), где n и m - мощности участвующих в операции множеств.
Если элементы в списках упорядочить, например, по возрастанию значения поля i, то трудоемкость всех операций составит О(n). Эффективная реализация операций над множествами, представленными в виде упорядоченных списков, основана на весьма общем алгоритме, известном как алгоритм типа слияния.
1
1 1
1 2 1
13 3 1
14 6 4 1
Рисунок 2.9 - Иллюстрация к алгоритму слияния
В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число сочетаний С (m, n) находится в (m + 1) - м ряду на (n + 1) - м месте.
Генерация подмножеств
Элементы множества {1,…, m} упорядочены. Поэтому каждое n_элементное подмножество также можно рассматривать как упорядоченную последовательность. На множестве таких последовательностей естественным образом определяется лексикографический порядок. Следующий простой алгоритм генерирует все n_элементные подмножества m_элементного множества в лексикографическом порядке.
Алгоритм 1.3. Генерация n_элементных подмножеств m_элементного множества
Вход: n - мощность подмножества, m - мощность множества, m n > 0.
Выход: последовательность всех n_элементных подмножеств m_элементного множества в лексикографическом порядке.
for i from 1 to m do
A[i]: = i {инициализация исходного множества} end for
if m = n then
yield A [1..n] {единственное подмножество} exit end if
p: = n {p - номер первого изменяемого элемента} while p 1 do
yield A [1..n] {очередное подмножество в первых n элементах массива А} if А[i] = m then
р: = р - 1 {нельзя увеличить последний элемент} else
р:=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;
{Задаем характеристические векторы}
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.
2.2.3 Варианты заданий
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
11)
12)
13)
14)
15)
16)
17)
18)
19)
20)
21)
22)
23)
24)
25)
26)
27)
28)
29)
30)
31)
32)
33)
34)
35)
36)
37)
38)
39)
40)
41)
42)
43)
44)
45)
46)
47)
47)
49)
50)
2.3 Вопросы для самопроверки
1) Какие основные символы, используемые в теории множеств, вы знаете?
2) Перечислите основные операции над множествами и функции, применимые к множествам, которые используются в Delphi.
3) Что такое множество? Как его обозначить? Как можно задать множество?
4) Какое множество называют счетным? Какое - пустым?
5) Что такое подмножество?
6) Сформулируйте основные свойства счетных множеств.
7) Определите понятие вектора, булеана.
8) Сформулируйте основные аксиомы теории множеств.
9) Какие соотношения (действия) между множествами вы знаете, как они обозначаются?
10) Какое множество можно назвать универсальным?
11) Какие операции (из аналогичных арифметическим) нельзя производить с множествами?
12) Что такое диаграмма Эйлера-Венна? Проиллюстрируйте с помощью диаграмм Эйлера-Венна объединение и пересечение трех множеств.
13) Дайте определение декартова произведения множеств; какие теоремы о декартовом произведении Вы знаете?
14) Поясните термин «мощность множества».
15) Сформулируйте (и докажите) основные тождества алгебры множеств.
16) Дайте определение проекции вектора.
17) Что понимается под соответствием между множествами?
18) Дайте определение функции с точки зрения теории множеств. Приведите пример.
19) Дайте определение бинарного отношения, перечислите свойства.
20) Какие отношения называют рефлексивными, транзитивными?
21) Что такое «класс эквивалентности»?
22) Для чего нужна диаграмма Хассе?
23) Дайте определение нечёткого множества.
24) Какие операции допустимы над нечёткими множествами?
25) Дайте определение расстояний Хемминга и его основных свойств.
26) Перечислите основные алгоритмы генерации множеств.
Практическая работа № 3. Элементы теории графов
Цель работы: изучение математических структур для представления графов, изучение наиболее известных алгоритмов на графах и построение приложений на Delphi для описания графов в виде математических структур, реализации некоторых алгоритмов на графах.
3.1 Теоретическая часть
В данном параграфе многие определения и рисунки взяты из [17] и [19], являются дополнительными сведениями для материала, рассматриваемого в [24].
Пусть V - конечное множество (множество вершин), А - множество упорядоченных пар вершин, элементы которого называются ребрами.
Тогда графом G (V, A) называется совокупность множества вершин и множества ребер. Вершины а и с соединяются ребром, если (а, с)А.
Пусть дано множество вершин V и декартово произведение VхV - множество всевозможных пар вершин. Тогда графом G является подмножество декартового произведения.
Ребро графа G ориентировано, если порядок пары (a, b) существенен.
Ребро графа G не ориентировано, если порядок пары (a, b) несущественен.
Рисунок 3.1 - Ориентированный граф
Граф называется ориентированным, если все его ребра ориентированы.
Граф G называется неориентированным, если все его ребра неориентированы.
Смешанным графом называется граф, у которого есть как ориентированные, так и неориентированные ребра.
Каждому ребру E=a, b можно поставить в соответствие некоторое число.
Граф G, каждому ребру которого присвоено число (например, расстояние) называется сетью.
Пусть даны a, b - вершины графа. Ребро E их соединяет. Тогда говорят, что ребро E инцидентно вершинам a и b. И обратно - вершины a и b инцидентны ребру E.
При изображении графа имеется большая свобода в размещении вершин и дуг.
Рисунок 3.2 - Три изображения одного и того же графа
Пусть G и G1 графы, V и V1 - множества их вершин соответственно. Графы G и G1 изоморфны, если существует взаимнооднозначное соответствие между множествами их вершин V и V1 и вершины в графе G соединены ребром в том и только том случае, если соответствующие вершины соединены ребром в графе G1.
Если графы G и G1 ориентированы, то направления ребер должны соответствовать друг другу. Изоморфные графы имеют одинаковые свойства.
Вершина, не инцидентная никакому ребру, называется изолированной. Граф, состоящий из изолированных вершин, называется нуль граф. Обозначается через О.
Граф, любые две вершины которого соединены ребром, называется полным графом U=U(V).
Петлей называется ребро L=(a, a). Петля считается неориентированным ребром.
Рисунок 3.3 - Петля
Пара вершин может соединяться несколькими различными ребрами.
Пара ребер Ei Ej, ориентированная в противоположном направлении, эквивалентна одному неориентированному ребру.
Таким образом, мы можем любой неориентированный граф превратить в ориентированный. При этом количество ребер увеличивается в 2 раза.
Граф называется плоским, если может быть изображен на плоскости так, чтобы его ребра пересекались только в вершинах.
Граф назовем однородным степени k, если локальные степени во всех его вершинах равны k, т. е.
|
Рисунок 3.4 - Бесконечный однородный граф |
Рисунок 3.5 - Конечный однородный граф |
Граф H называется частью графа G, если подмножество вершин его V(H) содержится во множестве вершин V(G) и все ребра части графа H являются ребрами G и обозначается HG.
Для любой части H графа G существует дополнение , которое состоит из всех ребер графа G, не принадлежащих H.
Рисунок 3.6 - Граф G Рисунок 3.7 - Часть графа G
Пусть H1 и H2 - две части графа G. Сумма этих частей H1UH2 есть часть, состоящая из ребер, принадлежащих H1 или H2. Пересечение D=H1H2 - есть часть, состоящая из ребер, принадлежащих H1 и H2 одновременно. Две части не пересекаются по вершинам, если они не имеют общих вершин, и, следовательно, ребер. Части H1 и H2 не пересекаются по ребрам, если они не имеют общих ребер H1H2=0. Если H1 и H2 непересекающиеся части графа G, то их сумма называется прямой и H1UH2=G.
Бинарные отношения и графы
Бинарные отношения можно изобразить графом: вершины графа - элементы множества V, ребра графа соединяют вершины, которые находятся в отношении друг к другу.
Любой граф определяет бинарное отношение R на множестве вершин V, если для каждого ребра (a, b) выполняется aRb. Нельзя говорить о взаимнооднозначном соответствии между графами и бинарными отношениями. Пустому бинарному отношению соответствует нуль-граф О. Универсальному бинарному отношению отвечает полный граф U. Бинарному отношению aRb, где R - отрицание R (дополнительное бинарное отношение) отвечает граф G(R)=U(V) - G(R). Обратному бинарному отношению bR*a отвечает обратный граф G (R*), т. е. граф с измененной ориентацией ребер. Операции, которые вводятся для бинарных отношений, могут быть перенесены на графы.
Симметричное бинарное отношение: если aRb, то bRa.
Рефлексивность: бинарное отношение aRa соответствует графу с петлей в каждой вершине.
Транзитивность: если aRb и bRc, то aRc. Для графа это означает, что если существует ребро (a, b) и ребро (b, c), то существует ребро (a, c). Такой граф называется связным.
Свойство связности можно рассмотреть как бинарное отношение, которое:
а) рефлексивно: вершина а связана сама с собой;
б) симметрично: если вершина а связана с вершиной b, то и вершина b связана с вершиной a;
в) транзитивно: если вершина a связана с вершиной b, и b связана с вершиной с, то вершина a связана с вершиной c.
Отношение связности есть отношение эквивалентности, т. е. оно разбивает множество вершин на попарно непересекающиеся классы.
Так как каждое множество Vi - множество связанных вершин, а вершины из разных множеств Vi не связаны, то имеем разложение графа G на части, которые не пересекаются и каждая часть - связная.
Подграфы G(Vi) называются связными компонентами графа G.
Каждый неориентированный граф распадается единственным образом в прямую сумму всех своих связных компонент.
Покрывающие деревья
Граф, не содержащий циклов, называется ациклическим. Деревом называется связный граф, не содержащий циклов. Пусть VG - число элементов в множестве вершин, VL - число элементов множества ребер дерева.
Рисунок 3.8 - Дерево
VG =VL_1
Добавим ребро - появляется цикл, удалим ребро - теряется связность. Лесом называется несвязный граф, компонентами которого являются деревья.
Пусть VLl - число элементов в множестве ребер леса, VGl - число элементов в множестве вершин леса, k - число деревьев в лесе.
VLl = VGl - k
Если дерево Т имеет корень, то дерево называется деревом с корнем. Выделим в дереве Т некоторую цепь.
Рисунок 3.9 - Дерево
Задача.
Как узнать, существуют ли циклы в графе?
Для дерева связь между числом ребер и числом вершин такова
Vl=VG_1. Рассмотрим = Vl-VG+1, называется цикломатическим числом. Если граф G - дерево, то =0, если не равно нулю, то в графе G есть циклы.
Алгоритм построения произвольного покрывающего дерева [20]
Ограничения: в графе не должно быть петель. Букетом называется произвольное дерево в графе.
Шаг 1. Выбираем произвольное ребро и помечаем его х (красим в голубой цвет).
Шаг 2. Выбираем другое произвольное непомеченное ребро. Если оба конца ребра лежат в одном букете, красим ребро в красный цвет. В противном случае - в голубой.
Шаг 3. Если все вершины графа вошли в один букет, то процедура заканчивается, т. к. помеченные голубым ребра образуют покрывающее дерево. В противном случае - перейти к шагу 2.
Рисунок 3.10 - Граф
1 шаг: (a, d) - помечаем голубым
2 шаг: (b, e) - помечаем голубым
3 шаг: (d, e) - помечаем голубым
4 шаг: (a, b) - помечаем красным
5 шаг: (a, c) - получаем голубым
Рисунок 3.11 - Дерево
Алгоритм построения минимального и максимального покрывающего дерева [21]
Пусть каждому ребру графа G присвоена длина (вес) l (x, y) (таблица 3.1). Весом дерева называется сумма весов ребер, входящих в дерево. Минимальным деревом называется дерево с минимальным весом.
Алгоритм формируется так же, как и алгоритм построения произвольного покрывающего дерева. Но ребра просматриваются в порядке возрастания их веса.
Таблица 3.1 - Веса ребер графа
|
A |
b |
c |
d |
e |
||
|
a |
0 |
5 |
50 |
85 |
90 |
|
|
b |
5 |
0 |
70 |
60 |
50 |
|
|
c |
50 |
70 |
0 |
8 |
20 |
|
|
d |
85 |
60 |
8 |
0 |
10 |
|
|
e |
90 |
50 |
20 |
10 |
0 |
Порядок просмотра
(a, b) - 5 (b, e) - 50 упорядочим ребра по возрастанию
(c, d) - 8 (b, d) - 60
(d, e) - 10 (b, c) - 70
(c, e) - 20 (a, d) - 85
(a, c) - 50 (a, b) - 90
1 шаг: (a, b) - помечаем голубым
2 шаг: (c, d) - помечаем голубым
3 шаг: (d, e) - помечаем голубым
4 шаг: (c, e) - помечаем красным
5 шаг: (a, c) - помечаем голубым
Дерево построено!
Рисунок 3.12 - Дерево
Алгоритм построения максимального ориентированного дерева(алгоритм Эдмонса) [15]:
Шаг 1. Последовательно в произвольном порядке просматриваем вершины графа G0. Просмотр вершины заключается в том, чтобы из дуг, заходящих в эту вершину, выбрать дугу с максимальным весом. При просмотре следующих вершин к уже отобранным ранее дугам добавляются новые дуги. Если добавление ребра не нарушает свойства букета, то добавление ребер продолжается. Если новое ребро образует контур, перейти к шагу 2.
Шаг 2. В случае формирования контура строится уменьшенный граф путем стягивания дуг и вершин выявленного контура исходного графа Go в одну вершину V.
В новом графе веса ребер (xi, vi) полагаются равными
l (x, vi)=l (x, y)+l (r, s) - l (t, y),
где К - контур, а у - вершина, принадлежащая контуру.
l (x, vi) - ребро, переходящее в ребро l (x, vi)
l (r, s) - ребро, имеющее в контуре минимальный вес
l (t, y) - ребро, заходящее в вершину у и имеющее максимальный вес
Шаг 3. Выполняется тогда, когда вершины нового графа попадают в букет, а дуги образуют дерево.
Возможны 2 случая:
вершина Vo является корнем дерева, тогда необходимо рассмотреть ребра букета в новом графе совместно с ребрами контура. Удалить из рассматриваемого множества ребер ребро с минимальным весом;
если Vo не является корнем дерева - в букете нового графа имеется лишь одно ребро, заходящее в некоторую вершину Z и одно ребро контура, заходящее в ту же вершину. Удаляем ребро контура, заходящее в вершину Z.
Пример.
Рисунок 3.13 - Граф
Просмотр вершин: Букет получаемых ребер
a (da)
b (da) (cb)
c (da) (cb) (ac)
d (da) (cb) (ac) (bd)
Ребра (ac) (cb) (bd) (da) образуют контур. Минимальный вес ребра в контуре 2.
Стягиваем контур в одну вершину и рассматриваем граф:
Рисунок 3.14 - Граф
l(fe)=1
l (e, Vo)=l(ea)+2-3=3+2-3=2
l (f, Vo)=l (f, a)+2-3=-1
l (f, Vo) 1=l(fd)+2_l (b, d)=1+2-2=1
Просмотр вершин Букет ребер
e (fe)
f (fe)
Vo (fe) (eVo)
Получили множество ребер исходного графа Go такое:
(fe) (ea) - образуют букет
(ac) (cb) (bd) (da) - образуют контур
Vo не является контуром дерева, удаляем (da), поскольку (da) - ребро из контура. Получили дерево:
(fe) (ea) (ac) (cb) (bd) с весом l=1+2+3+2+2=10
Задача о кратчайших путях
Пусть G - ориентированный граф, Е - ребра графа. Каждому ребру соответствует число.
Рисунок 3.15 - Эйлеров цикл
Задача Эйлера о Кенигсбергских мостах [19]: необходимо выйти из любой точки города и вернуться в нее, при этом пройдя по каждому мосту только один раз. Эйлер свел эту задачу к графу: существует ли в конечном графе такой цикл, в котором каждое ребро участвует только один раз? Цикл, в котором каждое ребро графа G участвует всего один раз, называется эйлеровым циклом. Граф, содержащий эйлеров цикл, называется эйлеровым.
Дальнейшее развитие задачи об Эйлеровом цикле
Припишем ребрам графа длину м (ai, aj). Требуется найти путь в графе, который проходит через все ребра и имеет наименьшую длину.
Пример.
Рисунок 3.16 - Граф
S - стартовая вершина. Из вершины S надо пройти по всем ребрам так, чтобы маршрут имел минимальную длину. Очевидно, что длина маршрута будет минимальной, если каждое ребро будет пройдено всего один раз - т. е. маршрут будет эйлеровым циклом.
Все локальные степени - четные, значит граф эйлеров.
Варианты прохождения по циклу:
1) (sa) (ab) (bc) (cd) (db) (ds)
2) (sa) (ab) (bd) (dc) (cb) (bs)
3) (sb) (bc) (cd) (db) (ba) (as)
4) (sb) (bd) (dc) (cb) (ba) (as)
Длина эйлерова цикла - 22. Любой из вариантов 1-4 содержит каждое ребро графа, следовательно, длина одинакова для всех циклов 1-4. Длина эйлерова цикла не зависит от того, какая вершина будет выбрана за исходную.
Задача поиска эйлерова цикла - это задача о: - поиске наилучшего способа прохождения бригады по дорогам; - прохождении с/х техники по полям.
Впервые эта задача рассматривалась в связи с нахождением оптимального маршрута следования почтальона, который доставляет письма своим адресатам и должен при этом пройти минимальный путь.
Алгоритм нахождения эйлерова цикла для неориентированного графа [19]:
Дан эйлеров граф - т. е. граф с четными локальными степенями.
Найдем первое ребро х, инцидентное вершине S. Затем найдем ребро, смежное с ребром х, которое не образует цикл и еще не было использовано. Продолжим этот процесс до тех пор, пока не вернемся в вершину S. Если в построенный цикл С1 вошли все ребра графа - задача решена.
Если в построенный цикл С1 вошли не все ребра - строим цикл С2, состоящий из неиспользованных ребер и начинающийся с произвольного неиспользованного ребра.
Таким образом, строим циклы С2, С3,….Образование циклов продолжается до тех пор, пока не будут использованы все ребра.
Все циклы Сi необходимо объединить в один цикл. Условие объединения циклов С1 и С2 - наличие у них общей вершины х. Начинаем движение с любой вершины и двигаемся по циклу С1 до тех пор, пока не дойдем до х. Затем проходим ребро. С» и возвращаемся в х. Продолжаем обход по оставшимся ребрам до возвращения к исходной точке. Эта процедура легко обобщается на случай любого числа объединяемых циклов.
Циклы Эйлера для ориентированного графа
Алгоритм построения эйлерова цикла в эйлеровом ориентированном графе является аналогом алгоритма построения эйлерова цикла для неориентированного графа.
Строятся циклы Сi с учетом ориентации ребер, и затем все циклы объединяются в один.
Гамильтонов цикл (задача о коммивояжере)
Простой цикл, проходящий через каждую вершину графа только один раз, называется гамильтоновым циклом.
Если ребрам приписана длина, то различные варианты циклов отличаются друг от друга. Поэтому ставится задача нахождения гамильтонова цикла, имеющего минимальную длину.
Гамильтонов цикл наименьшей длины называется оптимальным гамильтоновым циклом (ОГЦ)
Поиск оптимального гамильтонова цикла - задача о коммивояжере, который должен посетить множество пунктов и вернуться домой, пройдя наименьший путь.
Решением задачи о коммивояжере не всегда является ОГЦ.
Гамильтоновы графы применяются для моделирования многих практических задач. Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра - связывающие их дороги. Кроме того, каждое ребро оснащено весом, обозначающим транспортные затраты, необходимые для путешествия по соответствующей дороге, например, расстояние между городами или время движения по дороге. Для решения задачи нам необходимо найти гамильтонов цикл минимального общего веса.
Рисунок 3.17 - Ребра, входящие в гамильтонов цикл С
К сожалению, алгоритм решения данной задачи, дающий оптимальное решение, пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно. Однако существуют алгоритмы поиска субоптимального решения [1]. Субоптимальное решение необязательно даст цикл минимального общего веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамильтоновых циклов! Один из таких алгоритмов - алгоритм ближайшего соседа.
Этот алгоритм выдает субоптимальное решение задачи коммивояжера, генерируя гамильтоновы циклы в нагруженном графе с множеством вершин V. Цикл, полученный в результате работы алгоритма, будет совпадать с конечным значением переменной маршрут, а его общая длина - конечное значение переменной w.
begin
Выбрать v € V;
маршрут:=v;
w:=0;
v':=v;
Отметить v';
while остаются неотмеченные вершины do begin
Выбрать неотмеченную вершину и,
ближайшую к v';
маршрут:= маршрут u;
w:= w + вес ребра v'u;
v':=u;
Отметить v';
end
маршрут:= маршрут v;
w:= w + вес ребра v'v;
end
Пример. Примените алгоритм ближайшего соседа к графу, изображенному на рисунке 3.18. За исходную вершину возьмите вершину D.
Рисунок 3.18 - Граф
Таблица 3.2 - Алгоритм ближайшего соседа
|
и |
маршрут |
w |
v' |
||
|
Исходные значения |
- |
D |
0 |
D |
|
|
С |
dc |
3 |
С |
||
|
А |
DCA |
9 |
A |
||
|
В |
DCAB |
14 |
В |
||
|
Последний проход |
В |
DCABD |
24 |
В |
В результате работы алгоритма был найден гамильтонов цикл DCABD общего веса 24. Делая полный перебор всех циклов в этом маленьком графе, можно обнаружить еще два других гамильтоновых цикла: ABCDA общего веса 23 и ACBDA общего веса 31. В полном графе с двадцатью вершинами существует приблизительно 6,1 * 10^16 гамильтоновых циклов, перечисление которых требует чрезвычайно много машинной памяти и времени.
Реализация примера данного алгоритма в Delphi:
procedure TForm1. Button1Click (Sender: TObject);
const mat:array [1.. 4,1..4] of byte=((0,5,6,8), (5,0,7,10), (6,7,0,3), (8,10,3,0));
Versh:array [1..4] of char=('a', 'b', 'c', 'd');
buk:char='d';
Type t=set of 'a'..'d';
Var dlina, i, j, min, n, k, s:byte;
put:string;
z:t;
begin
dlina:=0;
Memo1. Lines. Clear;
for i:=1 to 4 do if versh[i]=buk then begin n:=i; s:=i;
include (z, buk);
put:=put+buk;
end;
for j:=1 to 3 do begin
if mat [n, 1]<>0 then begin min:=mat [n, 1]; k:=1; end
else begin min:=mat [n, 2]; k:=2; end;
for i:=1 to 4 do
if (mat [n, i]<min) and (mat [n, i]<>0) and (not (versh[i] in z)) then begin
min:=mat [n, i];
k:=i;
end;
dlina:=dlina+min;
put:=put+versh[k];
include (z, versh[k]);
n:=k;
end;
put:=put+'d';
dlina:=dlina+mat [k, s];
Memo1. Lines. Add ('маршрут:'+' '+put);
Memo1. Lines. Add ('длина маршрута='+IntToStr(dlina));
end;
end.
Рисунок 3.19 - Форма с результатом
3.2 Практическая часть
3.2.1 Задание к работе
1 изучить теоретический материал по методическому пособию [24], лекциям и записям на практических занятиях;
2 получить задание по индивидуальному варианту в виде графа или матрицы смежности, в первом случае построить матрицу смежности, во втором - нарисовать граф;
3 составить подробное описание графа: ориентированный или неориентированный, количество вершин, дуг (рёбер), содержит ли циклы и какие, найти степени вершин, количество компонент связности и т. д.;
4 создать приложение на Delphi для расчёта матрицы инцидентности по известной матрице смежности (если граф достаточно сложный, то можно взять подграф этого графа);
5 в качестве дополнительного творческого задания создать приложение на Delphi для реализации алгоритма ближайшего соседа, алгоритма Прима, алгоритма Уоршелла, алгоритма Дейкстры, алгоритма определения количества компонент связности графа и других известных алгоритмов на графах. [13], [17], [18], [19], [20], [21].
3.2.2 Примеры выполнения
Пример 1: По заданной матрице смежности построить матрицу инцидентности.
implementation
procedure TForm1. UpDown1Click (Sender: TObject; Button: TUDBtnType);
begin
with UpDown1 do begin
with StringGrid1 do begin
RowCount:=Position;
ColCount:=Position;
end;
StringGrid2. RowCount:=Position;
end;
end;
procedure TForm1. BitBtn1Click (Sender: TObject);
var i, j, CD, P, n:byte;
MS:array of array of byte;
MI:array of array of ShortInt;
begin
P:=StrToInt (Edit1. Text);
SetLength (MS, P, P);
CD:=0;
for i:=0 to P_1 do for j:=0 to P_1 do begin
MS [i, j]:=StrToInt (StringGrid1. Cells [j, i]);
if MS [i, j]=1 then inc(CD);
end;
SetLength (MI, P, CD);
for i:=0 to High(MS) do for j:=0 to CD_1 do MI [i, j]:=0;
n:=0;
for i:=0 to High(MS) do for j:=0 to High(MS) do
if MS [i, j]=1 then begin
MI [i, n]:=1;
MI [j, n]:=-1;
inc(n);
end;
StringGrid2. ColCount:=CD;
for i:=0 to High(MS) do for j:=0 to CD_1 do
StringGrid2. Cells [j, i]:=IntToStr (MI[i, j]);
end;
end.
Рисунок 3.20 - Форма с результатом
Пример 2: По заданной матрице смежности построить матрицу инцидентности.
var
Form1: TForm1;
const maxv=4;
type canh=record dinh1, dinh2:byte;
dodai:real; end;
dothi=record n:byte;
l:array [1..maxv, 1..maxv] of real;
x, y:set of 1..maxv;
t:array [1..maxv] of canh;
nt:byte;
it:real; end;
implementation
{$R *.dfm}
procedure TForm1. Button1Click (Sender: TObject);
var g:dothi;
min:real;
x, y, x0, y0:1..maxv;
i, j:byte;
begin memo1. Clear;
g.n:=maxv;
edit1. Text:=inttostr(maxv);
stringgrid1.cells [0,0]:=' Номер';
for i:=1 to maxv do begin
stringgrid1.cells [0, i]:=inttostr(i);
stringgrid1.cells [i, 0]:=inttostr(i); end;
g.nt:=0; g.it:=0; g.x:=[1..g.n]; g.y:=[1];
for i:=1 to maxv do
for j:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]);
while g.nt<g.n_1 do begin
min:=-1;
for x:=1 to g.n do
for y:=1 to g.n do
if (x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then
begin
if (min=-1) or (min>g.l [x, y]) then begin
min:=g.l [x, y];
x0:=x; y0:=y; end;
end;
g.y:=g.y+[y0];
g.nt:=g.nt+1;
g.it:=g.it+min;
with g.t [g.nt] do begin
dinh1:=x0;
dinh2:=y0;
dodai:=min; end; end;
for i:=1 to (maxv_1) do
with g.t[i] do
memo1. Lines.add ('Ребро: '+inttostr(dinh1)+inttostr(dinh2)+' '+
'Весом: '+floattostr(dodai));
end;
end.
Рисунок 3.21 - Форма с результатом
Пример 3: Составить приложение на Delphi, реалилующее алгоритм Уоршелла.
var
Form1: TForm1;
const maxv=4;
type canh=record dinh1, dinh2:byte;
dodai:real; end;
dothi=record n:byte;
l:array [1..maxv, 1..maxv] of real;
x, y:set of 1..maxv;
t:array [1..maxv] of canh;
nt:byte;
it:real; end;
implementation
{$R *.dfm}
procedure TForm1. Button1Click (Sender: TObject);
var g:dothi;
min:real;
x, y, x0, y0:1..maxv;
i, j:byte;
begin memo1. Clear;
g.n:=maxv;
stringgrid1.cells [0,0]:=' Номер';
for i:=1 to maxv do begin
stringgrid1.cells [0, i]:=inttostr(i);
stringgrid1.cells [i, 0]:=inttostr(i); end;
g.nt:=0; g.it:=0; g.x:=[1..g.n]; g.y:=[1];
for i:=1 to maxv do
for j:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]);
while g.nt<g.n_1 do begin
min:=-1;
for x:=1 to g.n do
for y:=1 to g.n do
if (x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then
begin
if (min=-1) or (min>g.l [x, y]) then begin
min:=g.l [x, y];
x0:=x; y0:=y; end;
end;
g.y:=g.y+[y0];
g.nt:=g.nt+1;
g.it:=g.it+min;
with g.t [g.nt] do begin
dinh1:=x0;
dinh2:=y0;
dodai:=min; end; end;
for i:=1 to (maxv_1) do
with g.t[i] do
memo1. Lines.add ('Ребро: '+inttostr(dinh1)+inttostr(dinh2)+' '+
'Весом: '+floattostr(dodai));
end;
end.
Рисунок 3.23 - Форма с результатом
3.2.3 Вариантв заданий
3.3 Вопросы для самопроверки
1) Какие операции над графами Вы знаете?
2) Как формируется матрица смежности?
3) Как формируется матрица весов?
4) Как формируется матрица достижимости?
5) Как формируется матрица инцидентности?
6) Перечислите основные понятия, относящиеся к графам-деревьям.
7) Приведите пример сортировки и поиска в деревьях.
8) Для чего применяется алгоритм, подобный алгоритму Дейкстры, в коммуникационных сетях?
9) Перечислите известные Вам алгоритмы обхода графов.
10) Что такое транспортная сеть? Приведите пример.
11) Какой граф называется эйлеровым? Приведите пример эйлерова графа.
12) Какой граф называется гамильтоновым? Приведите пример гамильтонова графа.
13) Какой вид отношений на графах представляет изоморфизм графов?
14) Приведите пример отношения порядка и отношения эквивалентности на графе.
15) Какие алгоритмы обхода графов Вам известны?
16) Какие виды графов Вы знаете?
17) Что понимается под степенью вершины?
18) Как определяются числа внутренней и внешней устойчивости графа?
19) Как определяются хроматическое и цикломатическое числа графа?
20) Сформулируйте транспортную задачу и связанные с ней понятия?
21) Опишите кратко алгоритм управления проектами.
22) Приведите пример построения разреза графа.
23) Приведите пример дерева с корнем.
Практическая работа № 4. Элементы теории множеств и алгебры логики
Цель работы: применение знаний теории множеств и алгебры логики для решения практической задачи.
4.1 Указание к выполнению
Данная практическая работа сочетает в себе использование элементов теории множеств и алгебры логики. Все теоретические сведения, необходимые для выполнения данной работы, изложены в лекциях и в уже изданных методических пособиях [23], [25]. Выполнение данной работы рекомендуется выполнять по образцу, рассмотренному далее.
4.2 Задание к работе
1. Составить множества из букв Ф.И.О..
2. Представить полученные множества на кругах Эйлера.
3. Представить буквы Ф.И.О. в двоичной системе.
4. Представить диаграмму Венна. СНДФ.
5. Перевести числа даты рождения в двоичную систему счисления.
Примечание: желательно реализовать основные вычисления в приложении на Delphi.
4.3 Практическая часть
Пример 1:
1 Множества из букв Ф.И.О.
МОРОЗОВ ОЛЕГ ЕВГЕНЬЕВИЧ
Ф = {М, О, Р, З, В};
И = {О, Л, Е, Г};
О = {Е, В, Г, Н, Ь, И, Ч};
2 Круги Эйлера и диаграммы Венна
Рисунок 4.1 - Круги Эйлера
Таблица 4.1 - Буквы алфавита в двоичной системе
|
А |
00001 |
Л |
01011 |
Ц |
10110 |
|
|
Б |
00010 |
М |
01100 |
Ч |
10111 |
|
|
В |
00011 |
Н |
01101 |
Ш |
11000 |
|
|
Г |
00100 |
О |
01110 |
Щ |
11001 |
|
|
Д |
00101 |
П |
01111 |
Ъ |
11010 |
|
|
Е |
00110 |
Р |
10000 |
Ы |
11011 |
|
|
Ж |
00111 |
С |
10001 |
Ь |
11100 |
|
|
З |
01000 |
Т |
10010 |
Э |
11101 |
|
|
И |
01001 |
У |
10011 |
Ю |
11110 |
|
|
К |
01010 |
Ф |
10100 |
Я |
11111 |
|
|
Х |
10101 |
Таблица 4.2 - Буквы Ф.И.О. в двоичной системе
|
М |
О |
Р |
З |
В |
О |
Л |
Е |
Г |
Е |
В |
Г |
Н |
Ь |
И |
Ч |
|||
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
3 |
||
|
F1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
8 |
|
|
F2 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
10 |
|
|
F3 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
8 |
|
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
6 |
Таблица 4.3 - СНДФ из букв Ф.И.О.
|
x1 x2 x3 x4 |
F1 |
F2 |
F3 |
|
|
0 0 0 0 |
1 |
1 |
0 |
|
|
0 0 0 1 |
1 |
1 |
1 |
|
|
0 0 1 0 |
0 |
0 |
0 |
|
|
0 0 1 1 |
1 |
0 |
0 |
|
|
0 1 0 0 |
0 |
0 |
1 |
|
|
0 1 0 1 |
1 |
1 |
1 |
|
|
0 1 1 0 |
1 |
0 |
1 |
|
|
0 1 1 1 |
0 |
1 |
1 |
|
|
1 0 0 0 |
0 |
1 |
0 |
|
|
1 0 0 1 |
0 |
1 |
1 |
|
|
1 0 1 0 |
0 |
0 |
1 |
|
|
1 0 1 1 |
0 |
1 |
0 |
|
|
1 1 0 0 |
1 |
1 |
0 |
|
|
1 1 0 1 |
1 |
1 |
0 |
|
|
1 1 1 0 |
1 |
0 |
0 |
|
|
1 1 1 1 |
0 |
1 |
1 |
F1
F2
F3
Рисунок 4.2 - Диаграммы Венна для функций F1, F2, F3
3 Перевод даты рождения в двоичную систему
1982.0212
|
1982 |
2 |
||||||||||
|
991 0 |
2 |
||||||||||
|
495 1 |
2 |
||||||||||
|
247 1 |
2 |
||||||||||
|
123 1 |
2 |
||||||||||
|
61 1 |
2 |
||||||||||
|
30 1 |
2 |
||||||||||
|
15 0 |
2 |
||||||||||
|
7 1 |
2 |
||||||||||
|
3 1 |
2 |
||||||||||
|
1 1 |
|
0.0212 |
0.3568 |
1.4272 |
||||
|
2 |
2 |
2 |
||||
|
0 |
0.0424 |
0 |
0.7136 |
0 |
0.8544 |
|
|
2 |
2 |
2 |
||||
|
0 |
0.0848 |
1 |
1.4272 |
1 |
1.7088 |
|
|
2 |
||||||
|
0 |
0.1696 |
|||||
|
2 |
||||||
|
0 |
0.3392 |
|||||
|
2 |
||||||
|
0 |
0.6784 |
|||||
|
2 |
||||||
|
1 |
1.3568 |
(1982.0212) 10=(11110111110.0000010101) 2
Пример 2: автор - Якухин Дмитрий
var
k:byte;
Form1: TForm1;
type R = set of 'A'..'Я';
implementation
{$R *.dfm}
procedure SNDF (y:byte; t:string);
var i:byte;
begin
for i:=1 to 5 do begin
Form1. StringGrid1. Cells [y, i]:=t[i];
end;
for i:=1 to 3 do begin
Form1. StringGrid2. Cells [i+4, y]:=t [i+1];
end;
end;
procedure Perebor (T:R; S:TMemo);
begin
if ('А' in T) then begin S. Lines. Add ('А = '+' 00001'); inc(k); SNDF (k, '00001'); Form1. StringGrid1. Cells [k, 0]:='А'; end;
if ('Б' in T) then begin S. Lines. Add ('Б = '+' 00010'); inc(k); SNDF (k, '00010'); Form1. StringGrid1. Cells [k, 0]:='Б'; end;
if ('В' in T) then begin S. Lines. Add ('В = '+' 00011'); inc(k); SNDF (k, '00011'); Form1. StringGrid1. Cells [k, 0]:='В'; end;
if ('Г' in T) then begin S. Lines. Add ('Г = '+' 00100'); inc(k); SNDF (k, '00100'); Form1. StringGrid1. Cells [k, 0]:='Г'; end;
if ('Д' in T) then begin S. Lines. Add ('Д = '+' 00101'); inc(k); SNDF (k, '00101'); Form1. StringGrid1. Cells [k, 0]:='Д'; end;
if ('Е' in T) then begin S. Lines. Add ('Е = '+' 00110'); inc(k); SNDF (k, '00110'); Form1. StringGrid1. Cells [k, 0]:='Е'; end;
if ('Ж' in T) then begin S. Lines. Add ('Ж = '+' 00111'); inc(k); SNDF (k, '00111'); Form1. StringGrid1. Cells [k, 0]:='Ж'; end;
if ('З' in T) then begin S. Lines. Add ('З = '+' 01000'); inc(k); SNDF (k, '01000'); Form1. StringGrid1. Cells [k, 0]:='З'; end;
if ('И' in T) then begin S. Lines. Add ('И = '+' 01001'); inc(k); SNDF (k, '01001'); Form1. StringGrid1. Cells [k, 0]:='И'; end;
if ('К' in T) then begin S. Lines. Add ('К = '+' 01010'); inc(k); SNDF (k, '01010'); Form1. StringGrid1. Cells [k, 0]:='К'; end;
if ('Л' in T) then begin S. Lines. Add ('Л = '+' 01011'); inc(k); SNDF (k, '01011'); Form1. StringGrid1. Cells [k, 0]:='Л'; end;
if ('М' in T) then begin S. Lines. Add ('М = '+' 01100'); inc(k); SNDF (k, '01100'); Form1. StringGrid1. Cells [k, 0]:='М'; end;
if ('Н' in T) then begin S. Lines. Add ('Н = '+' 01101'); inc(k); SNDF (k, '01101'); Form1. StringGrid1. Cells [k, 0]:='Н'; end;
if ('О' in T) then begin S. Lines. Add ('О = '+' 01110'); inc(k); SNDF (k, '01110'); Form1. StringGrid1. Cells [k, 0]:='О'; end;
if ('П' in T) then begin S. Lines. Add ('П = '+' 01111'); inc(k); SNDF (k, '01111'); Form1. StringGrid1. Cells [k, 0]:='П'; end;
if ('Р' in T) then begin S. Lines. Add ('Р = '+' 10000'); inc(k); SNDF (k, '10000'); Form1. StringGrid1. Cells [k, 0]:='Р'; end;
if ('С' in T) then begin S. Lines. Add ('С = '+' 10001'); inc(k); SNDF (k, '10001'); Form1. StringGrid1. Cells [k, 0]:='С'; end;
if ('Т' in T) then begin S. Lines. Add ('Т = '+' 10010'); inc(k); SNDF (k, '10010'); Form1. StringGrid1. Cells [k, 0]:='Т'; end;
if ('У' in T) then begin S. Lines. Add ('У = '+' 10011'); inc(k); SNDF (k, '10011'); Form1. StringGrid1. Cells [k, 0]:='У'; end;
if ('Ф' in T) then begin S. Lines. Add ('Ф = '+' 10100'); inc(k); SNDF (k, '10100'); Form1. StringGrid1. Cells [k, 0]:='Ф'; end;
if ('Х' in T) then begin S. Lines. Add ('Х = '+' 10101'); inc(k); SNDF (k, '10101'); Form1. StringGrid1. Cells [k, 0]:='Х'; end;
if ('Ц' in T) then begin S. Lines. Add ('Ц = '+' 10110'); inc(k); SNDF (k, '10110'); Form1. StringGrid1. Cells [k, 0]:='Ц'; end;
if ('Ч' in T) then begin S. Lines. Add ('Ч = '+' 10111'); inc(k); SNDF (k, '10111'); Form1. StringGrid1. Cells [k, 0]:='Ч'; end;
if ('Ш' in T) then begin S. Lines. Add ('Ш = '+' 11000'); inc(k); SNDF (k, '11000'); Form1. StringGrid1. Cells [k, 0]:='Ш'; end;
if ('Щ' in T) then begin S. Lines. Add ('Щ = '+' 11001'); inc(k); SNDF (k, '11001'); Form1. StringGrid1. Cells [k, 0]:='Щ'; end;
if ('Ъ' in T) then begin S. Lines. Add ('Ъ = '+' 11010'); inc(k); SNDF (k, '11010'); Form1. StringGrid1. Cells [k, 0]:='Ъ'; end;
if ('Ы' in T) then begin S. Lines. Add ('Ы = '+' 11011'); inc(k); SNDF (k, '11011'); Form1. StringGrid1. Cells [k, 0]:='Ы'; end;
if ('Ь' in T) then begin S. Lines. Add ('Ь = '+' 11100'); inc(k); SNDF (k, '11100'); Form1. StringGrid1. Cells [k, 0]:='Ь'; end;
if ('Э' in T) then begin S. Lines. Add ('Э = '+' 11101'); inc(k); SNDF (k, '11101'); Form1. StringGrid1. Cells [k, 0]:='Э'; end;
if ('Ю' in T) then begin S. Lines. Add ('Ю = '+' 11110'); inc(k); SNDF (k, '11110'); Form1. StringGrid1. Cells [k, 0]:='Ю'; end;
if ('Я' in T) then begin S. Lines. Add ('Я = '+' 11111'); inc(k); SNDF (k, '11111'); Form1. StringGrid1. Cells [k, 0]:='Я'; end;
end;
procedure TForm1. BitBtn1Click (Sender: TObject);
Подобные документы
Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.
лабораторная работа [1,2 M], добавлен 23.07.2012Встроенные функции Excel, их статистический анализ. Организации данных в таблице для документирования и графического представления информации. Создание базы данных "Автомагазин". Построение логических конструкций, создание графиков и диаграмм в MS Excel.
курсовая работа [711,7 K], добавлен 31.07.2014Среда Borland Delphi и ее графические средства для построения фрактальных множеств. Разработка программы для построения изображения листа папоротника при помощи вероятностных распределений с использованием средств для отображения графической информации.
курсовая работа [1,3 M], добавлен 29.07.2013Эскизный, технический и рабочий проект расчета основоположной задачи теории множеств, решение которой необходимо для доказывания теорем высшей математики. Разработка алгоритма и написание программы в среде Delphi 7 на языке программирования Delphi.
курсовая работа [1,5 M], добавлен 21.09.2011Примеры решения математических и экономических задач, выполняемых с помощью средств электронной таблицы Excel и логических функций. Создание и форматирование таблиц. Создание разных баз данных с помощью системы Microsoft Access с использованием запроса.
контрольная работа [88,7 K], добавлен 28.05.2009Основные понятия алгебры логики. Логические основы работы ЭВМ. Вычислительные устройства как устройства обработки информации. Основные формы мышления. Обзор базовых логических операций. Теоремы Булевой алгебры. Пути минимизации логических функций.
контрольная работа [62,8 K], добавлен 17.05.2016Шифрование как метод защиты информации. История развития криптологии. Классификация алгоритмов шифрования, симметричные и асимметричные алгоритмы. Использование инструментов криптографии в Delphi-приложениях. Краткая характеристика среды Delphi 7.
курсовая работа [48,5 K], добавлен 19.12.2009Сведения о языке Delphi. Основы разработки баз данных. Разработка конвертера таблицы Excel, интерфейса главной формы, модуля отображения, системы поиска информации, средств редактирования. Системные требования программы. Инструкция по эксплуатации.
курсовая работа [2,6 M], добавлен 29.12.2008Назначение и составляющие формул, правила их записи и копирования. Использование математических, статистических и логических функций, функций даты и времени в MS Excel. Виды и запись ссылок табличного процессора, технология их ввода и копирования.
презентация [193,2 K], добавлен 12.12.2012Общая характеристика и функциональные особенности табличного редактора MS Excel, содержание его меню и оценка рабочих возможностей. Порядок построения графика и диаграммы. Изучение логических функций. Составление сводной таблицы. Работа с MS Power Point.
лабораторная работа [408,2 K], добавлен 23.05.2014
