Главная » Помощь в учебе » Школьные знания, ответы и решения школьных заданий » Информатика

Составьте алгоритм поиска для следующей задачи: на координатной плоскости заданы своими координатами N точек

Нашли ошибку? Напишите нам
0.0/5, Голосов: 0

Учебник по Информатике 9 класс Семакин

Составьте алгоритм поиска для следующей задачи: на координатной плоскости заданы своими координатами 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 повторений.