Список використаної літератури. 1. Г.А.Гайна навчальний посібник з дисципліни «Методи оптимізації:алгоритми,приклади,задачі»К.:КНУБА,2005.-144с

1. Г.А.Гайна навчальний посібник з дисципліни «Методи оптимізації:алгоритми,приклади,задачі»К.:КНУБА,2005.-144с.

2. Культин Н. Б. Программирование в Turbo Pascal 7.0 – Спб.: БХВ – Санкт-Петербург, 1999 – 240 с.

Додаток 1.

Текст програми

unit Unit1;

interface

uses

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

Dialogs, Grids, StdCtrls, Buttons, Menus, ExtCtrls;

const

maxn = 20;

inf = maxint div 2;

type

TForm1 = class(TForm)

G: TStringGrid;

Label1: TLabel;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

GroupBox1: TGroupBox;

G1: TStringGrid;

G2: TStringGrid;

GroupBox2: TGroupBox;

Label3: TLabel;

Edit1: TEdit;

BitBtn3: TBitBtn;

Panel1: TPanel;

SpeedButton1: TSpeedButton;

BitBtn1: TBitBtn;

BitBtn2: TBitBtn;

Memo1: TMemo;

procedure FormCreate(Sender: TObject);

procedure BitBtn3Click(Sender: TObject);

procedure init(sender: tobject);

procedure floyd;

procedure N3Click(Sender: TObject);

procedure Clear(Sender: TObject);

procedure N2Click(Sender: TObject);

procedure path(i, j: integer);

procedure N6Click(Sender: TObject);

procedure N5Click(Sender: TObject);

private

d, a: array [1..maxn, 1..maxn] of integer;

p: array [1..maxn, 1..maxn] of integer;

n: longint;

str: string;

public

{ Public declarations }

end;

var

Form1: TForm1;

implementa

procedure TForm1.FormCreate(Sender: TObject);

var i,j: longint;

begin

for i:=1 to G.ColCount do

for j:=1 to G.ColCount do begin

G.Cells[i,j]:=' ';

G2.Cells[i,j]:=' ' end;

G.Cells[0,0]:='G';

G1.Cells[0,0]:='G*';

G2.Cells[0,0]:='G`';

for i:=1 to 10 do begin

G.Cells[0,i]:=IntToStr(i);

G1.Cells[0,i]:=IntToStr(i);

G2.Cells[0,i]:=IntToStr(i);

G.Cells[i,0]:=IntToStr(i);

G1.Cells[i,0]:=IntToStr(i);

G2.Cells[i,0]:=IntToStr(i);

//Cells[i,i]:='0';

end; //for

end; //procedure

procedure TForm1.BitBtn3Click(Sender: TObject);

begin

n:=StrToInt(Edit1.Text);

if (n>0) and (n<=10) then begin

G.Enabled:=True;

G2.Enabled:=True;

BitBtn2.Enabled:=true end

else

MessageDlg('Невірні дані',MtError,[mbOk],0);

end;

procedure TForm1.init(sender: tobject);

var

i, j, x, y, nn, z: longint;

begin

N2.Enabled:=true;

for i:= 1 to maxn do

for j:= 1 to maxn do

a[i, j]:= inf;

for i:= 1 to maxn do

a[i, i]:= 0;

fillchar(d, sizeof(d), 0);

fillchar(p, sizeof(p), 0);

n:=StrToInt(Edit1.Text);

for i:=1 to n do

for j:=1 to n do

if G.Cells[i,j][1] in ['0'..'9'] then

a[i,j]:=StrToInt(G.Cells[i,j]);

floyd;

end;

// реалізація алгоритму Флойда

procedure TForm1.floyd;

var

k, i, j: integer;

begin

for i:= 1 to n do

for j:= 1 to n do

begin

p[i, j]:= i;

d[i, j]:= a[i, j];

end;

for k:= 1 to n do

for i:= 1 to n do

for j:= 1 to n do

if d[i, j] > d[i, k] + d[k, j] then

begin

d[i, j]:= d[i, k] + d[k, j];

p[i, j]:= k;

end

for i:=1 to n do

for j:=1 to n do begin

if p[i,j]=i then p[i,j]:=0;

G1.Cells[i,j]:=IntToStr(p[i,j]);

if d[i,j]>=1000 then G2.Cells[i,j]:='#' else

G2.Cells[i,j]:=IntToStr(d[i,j]) end;

for i:=1 to n do

for j:=1 to n do

if (p[i,j]=0) and (g.Cells[i,j][1] in ['1'..'9']) then

memo1.Lines.Add(IntToStr(j)+'-->'+IntToStr(i));

memo1.Lines.Add('Всі шляхи, що не перетинаються по ребрам');

memo1.Lines.Add('

for i:=1 to n do

for j:=1 to n do begin

str:='';

if G2.Cells[i,j][1] in ['1'..'9'] then begin

path(j,i);

memo1.Lines.Add(IntToStr(i)+'-->'+str+IntToStr(j)); end; end;

end;

procedure TForm1.N3Click(Sender: TObject);

begin

close;

end;

procedure TForm1.Clear(Sender: TObject);

var i,j: longint;

begin

for i:=1 to G.ColCount do

for j:=1 to G.ColCount do begin

G.Cells[i,j]:=' ';

G1.Cells[i,j]:=' ';

G2.Cells[i,j]:=' ' end;

memo1.Lines.Clear;

memo1.Lines.Add('Bсі шляхи, що не перетинаються по вершинам:');

memo1.Lines.Add(

end;

procedure TForm1.N2Click(Sender: TObject);

var f: textFile;

i,j: integer;

begin

SaveDlg.Show;

assignFile(f, SaveDlg.LEdit1.Text);

ReWrite(f);

Writeln(f);

Writeln(f,'Таблиця суміжності графа G');

for i:=1 to n do begin

for j:=1 to n do

write(f,G.Cells[i,j],' ');

writeln(f) end;

Writeln(f);

Writeln(f,'Найкоротші шляхи графа G');

for i:=1 to n do begin

for j:=1 to n do

write(f,G2.Cells[i,j],' ');

writeln(f) end;

CloseFile(f);

end;

procedure TForm1.path(i, j: integer);

var k: integer;

begin

k:= P[i,j];

if k=0 then exit;

path(i,k);

str:=str+' '+IntToStr(k)+'-->';

path(k,j);

end;

procedure TForm1.N6Click(Sender: TObject);

begin

AboutBox.Show;

end;

procedure TForm1.N5Click(Sender: TObject);

begin

form3.show;

end;

end.

Дата добавления: 2015-08-31