Составьте алгоритм поиска для следующей задачи: на координатной плоскости заданы своими координатами N точек
Составьте алгоритм поиска для следующей задачи: на координатной плоскости заданы своими координатами N точек. Найти две самые удаленные друг от друга точки. Оцените временную сложность алгоритма. Рассмотрите два варианта алгоритма: с полным и с неполным перебором и сравните их.
Формула нахождения длины отрезка по двум точкам:
Алгоритм с полным перебором:
NumberX1:=1;
NumberY1:=1;
NumberX2:=1;
NubmerY2:=2;
for i:=1 to N do
for j:=1 to N do
if sqrt(sqr(X[i] – X[j]) + sqr(Y[i]-Y[j])) > sqrt(sqr(NumberX2-NumberX1) + sqr(NubmerY2-NubmerY1))
then
begin
NumberX1:= X[i];
NumberY1:= Y[i];
NumberX2:= X[j];
NubmerY2:= Y[j];
end;
Алгоритм с неполным перебором:
NumberX1:=1;
NumberY1:=1;
NumberX2:=1;
NubmerY2:=2;
for i:=1 to N do
for j:=i+1 to N do
if sqrt(sqr(X[i] – X[j]) + sqr(Y[i]-Y[j])) > sqrt(sqr(NumberX2-NumberX1) + sqr(NubmerY2-NubmerY1))
then
begin
NumberX1:= X[i];
NumberY1:= Y[i];
NumberX2:= X[j];
NubmerY2:= Y[j];
end;
При полном переборе N2 повторений, а при неполном будет выполнено N(N-1)/2 повторений.