Основы дискретной математики (стр. 16 из 23)
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.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:
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 |