Новини‎ > ‎

Інформатика








Побудова графіка функції (delfi)









{алгоритм Флойда-Уоршелла}
program Floyd_Uorshell;
//uses crt;
const maxV=1000;
type matr=array[1..maxV, 1..maxV] of integer;
var i, j, n, inf: integer;
GR: matr;
{алгоритм Флойда-Уоршелла}
Procedure FU(D: matr; V: integer);
var i,j,k: integer;
begin
inf:=1000000;
for i:=1 to V do D[i, i]:=0;

for k:=1 to V do
for i:=1 to V do
for j:=1 to V do
if (D[i, k]<>0) and (D[k, j]<>0) and (i<>j) then
if (D[i, k]+D[k, j]<D[i, j]) or (D[i, j]=0) then
D[i, j]:=D[i, k]+D[k, j];

for i:=1 to V do
begin
for j:=1 to V do
write(D[i, j]:4);
writeln; ;
end;
end;
{главное блок программы}
begin
//clrscr;
write('Количество вершин в графе > '); readln(n);
writeln('Введите матрицу весов ребер:');
for i:=1 to n do
for j:=1 to n do
begin
write('GR[', i, '][', j, '] > ');
read(GR[i, j]);
end;
writeln('Матрица кратчайших путей:');
FU(GR, n);
end.


Код алгоритма Дейкстры
const V=6; inf=100000;
type vektor=array[1..V] of integer;
var start: integer;
const GR: array[1..V, 1..V] of integer=(
(0, 1, 4, 0, 2, 0),
(0, 0, 0, 9, 0, 0),
(4, 0, 0, 7, 0, 0),
(0, 9, 7, 0, 0, 2),
(0, 0, 0, 0, 0, 8),
(0, 0, 0, 0, 0, 0));
{алгоритм Дейкстры}
procedure Dijkstra( st: integer);
var count, index, i, u, m, min: integer;GR:array[1..V, 1..V] of integer;
distance: vektor;
visited: array[1..V] of boolean;
begin
m:=st;
for i:=1 to V do
begin
distance[i]:=inf; visited[i]:=false;
end;
distance[st]:=0;
for count:=1 to V-1 do
begin
min:=inf;
for i:=1 to V do
if (not visited[i]) and (distance[i]<=min) then
begin
min:=distance[i]; index:=i;
end;
u:=index;
visited[u]:=true;
for i:=1 to V do
if (not visited[i]) and (GR[u, i]<>0) and (distance[u]<>inf) and
(distance[u]+GR[u, i]<distance[i]) then
distance[i]:=distance[u]+GR[u, i];
end;
write('Стоимость пути из начальной вершины до остальных:'); writeln;
for i:=1 to V do
if distance[i]<>inf then
writeln(m,' > ', i,' = ', distance[i])
else writeln(m,' > ', i,' = ', 'маршрут недоступен');
end;
{основной блок программы}
begin

write('Начальная вершина >> '); read(start);
Dijkstra( start);
end.

Поиск в ширину (обход по уровням). Теория графов.

uses crt;
const n=4;
type
MassivInt=array[1..n, 1..n] of integer;
MassivBool=array[1..n] of boolean;
var
i, j, start: integer;
visited: MassivBool;
{матрица смежности графа}
const GM: MassivInt = (
(0, 1, 1, 0),
(0, 0, 1, 1),
(1, 0, 0, 1),
(0, 1, 0, 0));
{поиск в ширину}
procedure BFS(visited: MassivBool; _unit: integer);
var
queue: array[1..n] of integer;
count, head: integer;
begin
for i:=1 to n do queue[i]:=0;
count:=0; head:=0;
count:=count+1;
queue[count]:=_unit;
visited[_unit]:=true;
while head<count do
begin
head:=head+1;
_unit:=queue[head];
write(_unit, ' ');
for i:=1 to n do
begin
if (GM[_unit, i]<>0) and (not visited[i]) then
begin
count:=count+1;
queue[count]:=i;
visited[i]:=true;
end;
end;
end;
end;
{основной блок программы}
begin
clrscr;
write('Стартовая вершина >> '); read(start);
writeln('Матрица смежности графа: ');
for i:=1 to n do
begin
visited[i]:=false;
for j:=1 to n do
write(' ', GM[i, j]);
writeln;
end;
write('Порядок обхода: ');
BFS(visited, start);
end.

Пошук у глибину
uses crt;
const
n=5;
var
i, j, start: integer;
visited: array[1..n] of boolean;
const graph: array[1..n,1..n] of byte =
((0, 1, 0, 0, 1),
(1, 0, 1, 1, 0),
(0, 1, 0, 0, 1),
(0, 1, 0, 0, 1),
(1, 0, 1, 1, 0));
{поиск в глубину}
procedure DFS(st: integer);
var r: integer;
begin
write(st:2);
visited[st]:=true;
for r:=1 to n do
if (graph[st, r]<>0) and (not visited[r]) then
DFS(r);
end;
{основной блок программы}
begin
clrscr;
writeln('Матрица смежности:');
for i:=1 to n do
begin
visited[i]:=false;
for j:=1 to n do
write(graph[i, j],' ');
writeln;
end;
write('Стартовая вершина >> '); read(start);
writeln('Результат обхода'); DFS(start);
end.
ċ
30_osn-vz-progr.rar
(9004k)
Татьяна Федоровна,
14 сент. 2016 г., 12:23
Ċ
Татьяна Федоровна,
5 сент. 2016 г., 12:09
Ċ
Татьяна Федоровна,
5 сент. 2016 г., 12:00
Comments