2. Усовершенствовать алгоритм объединения степеней. Доказать, что Ao(IuA)N-2 = AuA^2u…uA^(N-1)
3. Усовершенствовать алгоритм Уоршалла следующим образом.
Рассмотрим выражение Cx,y:=Cx,y or Cx,z and Cz,y из алгоритма Уоршал-ла. Здесь Cx,y может изменить значение с ложного на истинное только в том случае, если истинны Cx,z и Cz,y . Поэтому, если Cx,z ложно, то Cx,y значение не изменит и нет смысла в поиске пары (z,y).
Программно реализовать усовершенствованный алгоритм Уоршалла.
unit disc_3_2;
interface
const MAX=15;
type
matr=array [1..MAX,1..MAX] of boolean;
var n:byte;
procedure uaos(a:matr; n:byte; var ed:matr); {улучшенный алгоритм объединения степеней}
var i,j,k:byte; tmp:matr;
begin
create_1_matr(ed,n);
superposition(a,n,ed);
for i:=1 to n do
for j:=1 to n do
tmp[i,j]:=ed[i,j];
for k:=2 to n-1 do
obedinenie(tmp,n,ed);
superposition(a,n,ed);
end;
procedure uau(a:matr; n:byte; var c:matr); {улучшенный алгоритм Уоршала}
var x,y,z:byte;
begin
for x:=1 to n do
for y:=1 to n do
c[x,y]:=a[x,y];
for z:=1 to n do
for x:=1 to n do
for y:=1 to n do
if not c[x,y] then
c[x,y]:=c[x,z] and c[z,y];
end;
for z:=1 to n do
for x:=1 to n do
if (z <> x) and c[x,z] then
for y:=1 to n do
c[x,y]:= c[x,y] or c[z,y];
procedure aos(a:matr; n:byte; var c:matr); { алгоритм объединения степеней}
var i,j,k:byte; tmp:matr;
begin
for i:=1 to n do
for j:=1 to n do
c[i,j]:=a[i,j];
for k:=2 to n-1 do
begin
superposition(a,n,tmp);
obedinenie(tmp,n,c);
end;
end;
procedure au(a:matr; n:byte; var c:matr); { алгоритм Уоршалла}
var x,y,z:byte;
begin
for x:=1 to n do
for y:=1 to n do
c[x,y]:=a[x,y];
for z:=1 to n do
for x:=1 to n do
for y:=1 to n do
c[x,y]:=c[x,y] or c[x,z] and c[z,y];
end;
Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.