Описание программного кода

2015-12-04

356

Обсуждений (0)

0.00 из 5.00 0 оценок

⇐ Предыдущая 1 2 3 4 5 67

Прикладная программа Max_potоk написана языком Object Pascal в интегрированной среде Delphi7.

Окно программы (Form1: TForm) содержит такие компоненты:

- текстовые поля (Eij: TEdit ; Inij: TEdit (i,j = 1..10));

– компоненты (STy: TStaticText (y = 1..10), OSTx: TStaticText (x = 1..10), VSTz: TStaticText (z = 1..10), OVSTe: TStaticText (e = 1..10), StaticTextij: TStaticText (i = 4, j = 1..4));

- надписи (Label1, Label2, Label3: TLabel);

- панель группировки компонентов (GB1: TGroupBox);

- кнопки (Buttonk: TButton (k = 1..5)).

В программе отслеживается 7 действий (табл. 6).

Таблица 6

Название действия	Назначение
TButton1.Click	Рассчитывает максимальный поток
TButton2.Click	Создаёт таблицы матриц пропускных способностей и потока заданной размерности
TButton3.Click	Считает одну итерацию
TButton4.Click	Выводит пометки
TButton5.Click	Начинает итерацию заново
TForm1.Create	Задаёт высоту и ширину окна программы
TForm1.Close	Совершает затухание формы при её закрытии

Предназначение текстовых полей приведено в таблице 7.

Метка поля	Название поля	Предназначение
Количество	Col	Задаётся количество вершин сети
s=	SSS	Задаётся источник сети
t=	TTT	Задаётся сток сети
Вершина	р1	Задаётся вершина, пометки которой будут рассчитываться
Предыдущая вершина	р2	Выводятся пометки вершины
Знак	р3
d	р4
Максимальный поток	max	Выводится максимальный поток сети
Xij	Inij	Задаётся матрица пропускных способностей сети
Xij	Eij	Выводится матрица потока в сети

Таблица 7

ВЫВОДЫ

Решая жизненные практические задачи, мы неоднократно сталкиваемся с проблемой поиска максимальных потоков в сетях (поиск максимального потока машин в сети дорог без возникновения пробок, поиск максимального количества нефти, которую можно перекачать по трубопроводу и др.).

В данной работе изучалась эта проблема, была рассмотрена теория, которая изучает методы поиска максимальных потоков в сетях, изучен алгоритм поиска максимального потока (алгоритм Форда-Фалкерсона), в интегрированной среде Delphi было разработано дополнение, которое позволяет в удобной для пользователя форме найти максимальный поток в заданной сети.

Это дополнение может быть использовано при проведении практических занятий по теме ”Теория графов” для студентов специальностей “Математика” и “Информатика” при изучении дисциплины “Дискретная математика”, а также для проверки тестовых заданий по этой теме.

ЛИТЕРАТУРА

1. Алгоритмы и программы решения задач на графах и сетях. Отв. ред. М.И. Нечепуренко. –Новосибирск: Наука. Сиб. отделение, 1990. – 513 с.

2. Андрійчук В.І., Комарницький М.Я., Іщук Ю.Б. Вступ до дискретної математики: Навчальний посібник. – Київ: Центр навчальної літератури, 2004. – 254 с.

3. Архангельский А.Я. Приемы программирования в Delphi. Версии 5 – 7. М.: ЗАО «Издательство БИНОМ», 2003.

4. Дискретна математика: Підручник/ Ю.М. Бардачов, Н.А. Соколова, В.Є. Ходаков; за ред. В.Є. Ходакова. – К.: Вища шк., 2002. – 287 с.: іл.

5. Дискретная математика: логика, группы, графы/ О.Е. Акимов. – 2-е изд., доп. – М.: Лаборатория Базовых Знаний, 2003. – 376 с.: ил.

6. Зыков А.А. Основы теории графов. – М.: Наука, 1987. – 381 с.

7. Климова Л.М. Delphi 7. Основы программирования. Решение типовых задач. Самоучитель – М.: КУДИЦ-ОБРАЗ, 2004. – 480 с.

8. Крістофідес Р. “Теория графов”. Переклад на російську мову “Мир” 1978.

9. Лекции по дискретной математике/ Ю.В. Капитонова, С.Л. Кривой, А.А. Летичевский и др. – СПб.: БХВ-Петербург, 2004. – 624 с.

10. Лекции по теории графов/ Емеличев В.А., Мельниченков О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука, Гл. ред. физ.-мат. лит., 1990. – 384 с.

11. Лекции по теории графов: Учебн. пособие. – М.: Наука, 1990. – 384 с.

12. Липский В. Комбинаторика для программистов: Пер. с польск. – М.: Мир, 1988. – 213 с.: ил.

13. Магрупов Т.М. Графы, сети, алгоритмы и их приложения/ Под ред. Ф.Б. Абуталиева; АН УсССР, Ин-т кибернетики с ВЦ УзНПО “Кибернетика”: – Ташкент: Фан, 1990. – 120 с.

14. Математическое программирование (с элементами информационных технологий): Учеб. пособие для студ. нематемат. спец. вузов/ В.Р. Кулян, Е.А. Юнькова, А.Б. Жильцов. – К.: МАУП, 2000. – 124 с.: ил.

15. Мiхайленко В.М. Дискретна математика. – К.: Європейський ун-т, 2003. – 319.

16. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2004. – 302 с.: ил.

17. Седжвік Д. “Програмирование на С++. Часть 5. Алгоритмы на графах”. Київ, 2003.

18. Теория графов и её применение: сборник научных трудов/ Институт математики им. С.Л. Соболева. – Новосибирск, 1996. – 106 с.

19. Яблонский С.В. Введение в дискретную митематику. – М.: Наука, 1986. – 384 с.

ПРИЛОЖЕНИЕ

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, DBGrids, AxCtrls, OleCtrls, VCF1, ComCtrls, StdCtrls;

type

TForm1 = class(TForm)

E11: TEdit; E21: TEdit; E31: TEdit; E41: TEdit; E51: TEdit; E61: TEdit;

E71: TEdit; E81: TEdit; E91: TEdit; E101: TEdit; E12: TEdit; E22: TEdit;

E32: TEdit; E42: TEdit; E52: TEdit; E62: TEdit; E72: TEdit; E82: TEdit;

E92: TEdit; E102: TEdit; E13: TEdit; E23: TEdit; E33: TEdit; E43: TEdit;

E53: TEdit; E63: TEdit; E73: TEdit; E83: TEdit; E93: TEdit; E103: TEdit;

E14: TEdit; E24: TEdit; E34: TEdit; E44: TEdit; E54: TEdit; E64: TEdit;

E74: TEdit; E84: TEdit; E94: TEdit; E104: TEdit; E15: TEdit; E25: TEdit;

E35: TEdit; E45: TEdit; E55: TEdit; E65: TEdit; E75: TEdit; E85: TEdit;

E95: TEdit; E105: TEdit; E16: TEdit; E26: TEdit; E36: TEdit; E46: TEdit;

E56: TEdit; E66: TEdit; E76: TEdit; E86: TEdit; E96: TEdit; E106: TEdit;

E17: TEdit; E27: TEdit; E37: TEdit; E47: TEdit; E57: TEdit; E67: TEdit;

E77: TEdit; E87: TEdit; E97: TEdit; E107: TEdit; E18: TEdit; E28: TEdit;

E38: TEdit; E48: TEdit; E58: TEdit; E68: TEdit; E78: TEdit; E88: TEdit;

E98: TEdit; E108: TEdit; E19: TEdit; E29: TEdit; E39: TEdit; E49: TEdit;

E59: TEdit; E69: TEdit; E79: TEdit; E89: TEdit; E99: TEdit; E109: TEdit;

E110: TEdit; E210: TEdit; E310: TEdit; E410: TEdit; E510: TEdit;

E610: TEdit; E710: TEdit; E810: TEdit; E910: TEdit; E1010: TEdit;

In11: TEdit; In21: TEdit; In31: TEdit; In41: TEdit; In51: TEdit;

In61: TEdit; In71: TEdit; In81: TEdit; In91: TEdit; In101: TEdit;

In12: TEdit; In22: TEdit; In32: TEdit; In42: TEdit; In52: TEdit;

In62: TEdit; In72: TEdit; In82: TEdit; In92: TEdit; In102: TEdit;

In13: TEdit; In23: TEdit; In33: TEdit; In43: TEdit; In53: TEdit;

In63: TEdit; In73: TEdit; In83: TEdit; In93: TEdit; In103: TEdit;

In14: TEdit; In24: TEdit; In34: TEdit; In44: TEdit; In54: TEdit;

In64: TEdit; In74: TEdit; In84: TEdit; In94: TEdit; In104: TEdit;

In15: TEdit; In25: TEdit; In35: TEdit; In45: TEdit; In55: TEdit;

In65: TEdit; In75: TEdit; In85: TEdit; In95: TEdit; In105: TEdit;

In16: TEdit; In26: TEdit; In36: TEdit; In46: TEdit; In56: TEdit;

In66: TEdit; In76: TEdit; In86: TEdit; In96: TEdit; In106: TEdit;

In17: TEdit; In27: TEdit; In37: TEdit; In47: TEdit; In57: TEdit;

In67: TEdit; In77: TEdit; In87: TEdit; In97: TEdit; In107: TEdit;

In18: TEdit; In28: TEdit; In38: TEdit; In48: TEdit; In58: TEdit;

In68: TEdit; In78: TEdit; In88: TEdit; In98: TEdit; In108: TEdit;

In19: TEdit; In29: TEdit; In39: TEdit; In49: TEdit; In59: TEdit;

In69: TEdit; In79: TEdit; In89: TEdit; In99: TEdit; In109: TEdit;

In110: TEdit; In210: TEdit; In310: TEdit; In410: TEdit; In510: TEdit;

In610: TEdit; In710: TEdit; In810: TEdit; In910: TEdit; In1010: TEdit;

ST1: TStaticText; ST2: TStaticText; ST3: TStaticText; ST4: TStaticText;

ST5: TStaticText; ST6: TStaticText; ST7: TStaticText; ST8: TStaticText;

ST9: TStaticText; ST10: TStaticText; OST1: TStaticText;

OST4: TStaticText; OST3: TStaticText; OST2: TStaticText;

OST5: TStaticText; OST6: TStaticText; OST7: TStaticText;

OST8: TStaticText; OST9: TStaticText; OST10: TStaticText;

VST1: TStaticText; VST2: TStaticText; VST3: TStaticText;

VST4: TStaticText; VST5: TStaticText; VST6: TStaticText;

VST7: TStaticText; VST8: TStaticText; VST9: TStaticText;

VST10: TStaticText; OVST1: TStaticText; OVST2: TStaticText;

OVST3: TStaticText; OVST4: TStaticText; OVST5: TStaticText;

OVST6: TStaticText; OVST7: TStaticText; OVST8: TStaticText;

OVST9: TStaticText; OVST10: TStaticText; SSS: TEdit;

StaticText41: TStaticText; TTT: TEdit; StaticText42: TStaticText;

Button1: TButton; StaticText43: TStaticText; StaticText44: TStaticText;

col: TEdit; label1: TLabel; Button2: TButton; Label2: TLabel;

max: TEdit; Button3: TButton; GB1: TGroupBox; Label3: TLabel;

Label4: TLabel; Label5: TLabel; Label6: TLabel; p1: TEdit;

p2: TEdit; p3: TEdit; p4: TEdit; Button4: TButton; Button5: TButton;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

procedure FormCreate(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

procedure Button5Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

function min(x,y: double): double;

const p1=10;

type

sign=(minus,plus);

ibool=0..1;

Rec=record

s:sign; {направление дуги}

n:1..p1; {предшествующая вершина в аугментальной цепи}

delta:double; {величина возможного увеличения потока}

end;

var

Form1: TForm1;

F: array of array of double;

P: array of Rec;

implementation

{$R *.dfm}

function min(x,y: double): double;

begin

if x < y then

Result := x

else

Result := y;

end;

procedure TForm1.Button1Click(Sender: TObject);

label M;

const p1=10;

type

sign=(minus,plus);

ibool=0..1;

Rec=record

s:sign; {направление дуги}

n:1..p1; {предшествующая вершина в аугментальной цепи}

delta:double; {величина возможного увеличения потока}

end;

var i,j: integer;

del,ch:double;

C,F: array of array of double;

P: array of Rec;

N,S: array of ibool;

a:ibool;

pp,s1,t1,x: byte;

input,output:array of array of TEdit;

begin

pp:=StrToInt(col.Text);

SetLength(input,pp);

SetLength(output,pp);

SetLength(C,pp);

SetLength(F,pp);

SetLength(P,pp);

SetLength(N,pp);

SetLength(S,pp);

for i:=0 to pp-1 do

begin

SetLength(input[i],pp);

SetLength(output[i],pp);

SetLength(C[i],pp);

SetLength(F[i],pp);

end;

for i:=1 to pp do

for j:=1 to pp do

begin

F[i-1,j-1] := 0; {вначале поток нулевой}

input[i-1,j-1]:=FindComponent(Format('In%d%d',[i,j])) as TEdit;

output[i-1,j-1]:=FindComponent(Format('E%d%d',[i,j])) as TEdit;

if input[i-1,j-1].Text<>'' then C[i-1,j-1]:=StrToFloat(input[i-1,j-1].Text)

else C[i-1,j-1]:=0;

end;

s1 := StrToInt(SSS.Text[2]);

if (s1=1) and (length(SSS.Text)=3) then

s1:=10;

t1 := StrToInt(TTT.Text[2]);

if (t1=1) and (length(TTT.Text)=3) then

t1:=10;

M: {итерация увеличения потока}

for i:=1 to pp do

begin

S[i-1] := 0;

N[i-1] := 0;

with P[i-1] do

begin

//s := null;

//n := nil;

delta := 0;

end;

S[s1-1]:=1;

with P[s1-1] do

begin

s:=plus;

n:=s1;

end;

repeat

a:=0; {признак расширения S}

for i:=1 to pp do

begin

if (S[i-1]=1) and (N[i-1]=0) then

begin

for j:=1 to pp do

begin

if C[i-1,j-1]<>0 then

begin

if (S[j-1]=0) and (F[i-1,j-1] < C[i-1,j-1]) then

begin

S[j-1] := 1;

with P[j-1] do

begin

s := plus;

n := i;

if i=s1 then delta := C[i-1,j-1] - F[i-1,j-1]

else delta := min(P[i-1].delta,C[i-1,j-1] - F[i-1,j-1]);

end;

a := 1;

end;

if C[j-1,i-1]<>0 then

begin

if (S[j-1]=0) and (F[j-1,i-1]>0) then

begin

S[j-1] := 1;

with P[j-1] do

begin

s := minus;

n := i;

if i=s1 then delta := F[j-1,i-1]

else delta := min(P[i-1].delta,F[j-1,i-1]);

end;

a:=1;

end;

N[i-1] := 1;

end;

if S[t1-1]<>0 then

begin

x:=t1;

del:=P[t1-1].delta;

while x<>s1 do

begin

if P[x-1].s=plus then

F[P[x-1].n-1,x-1]:=F[P[x-1].n-1,x-1]+del

else

F[x-1,P[x-1].n-1]:=F[x-1,P[x-1].n-1]-del;

x:=P[x-1].n

end;

goto M;

end;

until a=0;

ch:=0;

for i:=1 to pp do

begin

ch:=ch+F[s1-1,i-1];

for j:=1 to pp do

begin

if C[i-1,j-1]<>0 then

output[i-1,j-1].Text := FloatToStr(F[i-1,j-1])

else

output[i-1,j-1].Text := '';

end;

max.Text := FloatToStr(ch);

end;

//----------------------------------------------------

procedure TForm1.Button2Click(Sender: TObject);

const p1=10;

var InG,InV,OutG,OutV :array[1..p1] of TStaticText;

i,pp,j: byte;

input,output:array[1..p1,1..p1] of TEdit;

begin

SSS.Text:='';

TTT.Text:='';

max.Text:='';

pp:=StrToInt(Col.Text);

SetLength(F,pp);

for i:=1 to pp do

begin

SetLength(F[i-1],pp);

for j:=1 to pp do

F[i-1,j-1] := 0;

end;

for i:=1 to p1 do

begin

InG[i] := FindComponent(Format('ST%d',[i])) as TStaticText;

InV[i] := FindComponent(Format('VST%d',[i])) as TStaticText;

OutG[i] := FindComponent(Format('OST%d',[i])) as TStaticText;

OutV[i] := FindComponent(Format('OVST%d',[i])) as TStaticText;

if i<=pp then

begin

InG[i].Visible:=true;

InV[i].Visible:=true;

OutG[i].Visible:=true;

OutV[i].Visible:=true;

end

else

begin

InG[i].Visible:=false;

InV[i].Visible:=false;

OutG[i].Visible:=false;

OutV[i].Visible:=false;

end;

for j:=1 to p1 do

begin

input[i,j] := FindComponent(Format('In%d%d',[i,j])) as TEdit;

output[i,j] := FindComponent(Format('E%d%d',[i,j])) as TEdit;

if (i<=pp) and (j<=pp) then

begin

input[i,j].Visible:=true;

output[i,j].Visible:=true;

input[i,j].Text:='';

output[i,j].Text:='';

end

else

begin

input[i,j].Visible:=false;

output[i,j].Visible:=false;

end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

var

i, cavb : 0..255;

begin

if AlphaBlend=False then

begin

AlphaBlendValue:=255;

AlphaBlend:=True;

end;

cavb:=AlphaBlendValue;

for i := cavb downto 0 do

begin

AlphaBlendValue := i;

Application.ProcessMessages;

end

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Form1.Height:=600;

Form1.Width:=800;

end;

procedure TForm1.Button3Click(Sender: TObject);

var i,j: integer;

del:double;

C: array of array of double;

N,S: array of ibool;

a:ibool;

pp,s1,t1,x: byte;

input,output:array of array of TEdit;

begin

p1.Text :='';

p2.Text :='';

p3.Text :='';

p4.Text :='';

pp:=StrToInt(col.Text);

SetLength(input,pp);

SetLength(output,pp);

SetLength(C,pp);

SetLength(P,pp);

SetLength(N,pp);

SetLength(S,pp);

for i:=0 to pp-1 do

begin

SetLength(input[i],pp);

SetLength(output[i],pp);

SetLength(C[i],pp);

end;

for i:=1 to pp do

for j:=1 to pp do

begin

input[i-1,j-1]:=FindComponent(Format('In%d%d',[i,j])) as TEdit;

output[i-1,j-1]:=FindComponent(Format('E%d%d',[i,j])) as TEdit;

if input[i-1,j-1].Text<>'' then C[i-1,j-1]:=StrToFloat(input[i-1,j-1].Text)

else C[i-1,j-1]:=0;

end;

s1 := StrToInt(SSS.Text[2]);

if (s1=1) and (length(SSS.Text)=3) then

s1:=10;

t1 := StrToInt(TTT.Text[2]);

if (t1=1) and (length(TTT.Text)=3) then

t1:=10;

for i:=1 to pp do

begin

S[i-1] := 0;

N[i-1] := 0;

with P[i-1] do

begin

//s := null;

//n := nil;

delta := 0;

end;

S[s1-1]:=1;

with P[s1-1] do

begin

s:=plus;

n:=s1;

end;

repeat

a:=0; {признак расширения S}

for i:=1 to pp do

begin

if (S[i-1]=1) and (N[i-1]=0) then

begin

for j:=1 to pp do

begin

if C[i-1,j-1]<>0 then

begin

if (S[j-1]=0) and (F[i-1,j-1] < C[i-1,j-1]) then

begin

S[j-1] := 1;

with P[j-1] do

begin

s := plus;

n := i;

if i=s1 then delta := C[i-1,j-1] - F[i-1,j-1]

else delta := min(P[i-1].delta,C[i-1,j-1] - F[i-1,j-1]);

end;

a := 1;

end;

if C[j-1,i-1]<>0 then

begin

if (S[j-1]=0) and (F[j-1,i-1]>0) then

begin

S[j-1] := 1;

with P[j-1] do

begin

s := minus;

n := i;

if i=s1 then delta := F[j-1,i-1]

else delta := min(P[i-1].delta,F[j-1,i-1]);

end;

a:=1;

end;

N[i-1] := 1;

end;

if S[t1-1]<>0 then

begin

x:=t1;

del:=P[t1-1].delta;

while x<>s1 do

begin

if P[x-1].s=plus then

F[P[x-1].n-1,x-1]:=F[P[x-1].n-1,x-1]+del

else

F[x-1,P[x-1].n-1]:=F[x-1,P[x-1].n-1]-del;

x:=P[x-1].n

end;

Break;

end;

until a=0;

for i:=1 to pp do

begin

for j:=1 to pp do

begin

if C[i-1,j-1]<>0 then

output[i-1,j-1].Text := FloatToStr(F[i-1,j-1])

else

output[i-1,j-1].Text := '';

end;

procedure TForm1.Button4Click(Sender: TObject);

var s1,ver: byte; // Вершина

begin

p4.Font.Name := 'MS Sans Serif';

ver := StrToInt(p1.Text[2]);

if (ver=1) and (length(p1.Text)=3) then

ver:=10;

s1 := StrToInt(SSS.Text[2]);

if (s1=1) and (length(SSS.Text)=3) then

s1:=10;

if P[ver-1].s=plus then p3.Text := '+'

else p3.Text := '-';

p2.Text := 'x' + IntToStr(P[ver-1].n);

if ver<>s1 then

p4.Text := FloatToStr(P[ver-1].delta)

else

begin

p4.Font.Name :='Symbol';

p4.Text := 'Ґ';

end;

procedure TForm1.Button5Click(Sender: TObject);

var pp,i,j : integer;

output:array of array of TEdit;

begin

pp:=StrToInt(Col.Text);

SetLength(F,pp);

SetLength(output,pp);

for i:=1 to pp do

begin

SetLength(output[i-1],pp);

SetLength(F[i-1],pp);

for j:=1 to pp do

begin

F[i-1,j-1] := 0;

output[i-1,j-1]:=FindComponent(Format('E%d%d',[i,j])) as TEdit;

output[i-1,j-1].Text := '';

end;

end.

2015-12-04

356

Обсуждений (0)

0.00 из 5.00 0 оценок

⇐ Предыдущая 1 2 3 4 5 67

Обсуждение в статье: Описание программного кода

Обсуждений еще не было, будьте первым... ↓↓↓