Среднее расстояние между двумя точками в...

и задачки для интервью.
User avatar
perasperaadastra
Уже с Приветом
Posts: 20128
Joined: 21 Feb 2009 22:55
Location: Лох Онтарио

Среднее расстояние между двумя точками в...

Post by perasperaadastra » 05 Jul 2016 23:57

Предлагаю головоломку.

Дан единичный квадрат (сторона = 1). Каково среднее расстояние между двумя случайными точками внутри квадрата? Все точки внутри квадрата равновероятны.

User avatar
Uzito
Уже с Приветом
Posts: 5099
Joined: 06 Feb 2002 10:01
Location: NJ, USA

Re: Среднее расстояние между двумя точками в...

Post by Uzito » 06 Jul 2016 00:03

http://mathworld.wolfram.com/SquareLinePicking.html" onclick="window.open(this.href);return false;

User avatar
perasperaadastra
Уже с Приветом
Posts: 20128
Joined: 21 Feb 2009 22:55
Location: Лох Онтарио

Re: Среднее расстояние между двумя точками в...

Post by perasperaadastra » 06 Jul 2016 01:46

Если честно, аналитическое решение изяществом не отличается. Интересно, есть ли более наглядный приблизительный способ?

User avatar
venco
Уже с Приветом
Posts: 1991
Joined: 10 Nov 2004 00:34
Location: MD

Re: Среднее расстояние между двумя точками в...

Post by venco » 07 Jul 2016 23:39

Приближённо можно так:
разбиваем квадрат на 4 равных, с вероятностью 1/4 точки попадут в один под-квадрат, с вероятностью 1/4 в противоположные, и с вероятностью 1/2 - в соседние.
Дальше, в первом приближении среднее расстояние между случайными точками из разных под-квадратов можно представить как sqrt(Avg^2+d^2), где Avg - среднее расстояние точек в одном под-квадрате, а d - расстояние между под-квадратами.
Получается уравнение:
Avg=1/4*Avg/2 + 1/4*sqrt(1/2+Avg^2/4) + 1/2*sqrt(1/4+Avg^2/4)
Сводим его к би-квадратному и получаем решение:
Avg = sqrt(3/5 + 7/(5 sqrt(6)))/2 ~= 0.5412
Не сильно отличается от точного 0.5214

User avatar
perasperaadastra
Уже с Приветом
Posts: 20128
Joined: 21 Feb 2009 22:55
Location: Лох Онтарио

Re: Среднее расстояние между двумя точками в...

Post by perasperaadastra » 08 Jul 2016 02:19

Хороший метод! :great:

Я попробовал по-другому: разбил квадрат на 16 ячеек и считал среднее расстояние между центрами ячеек (если две точки попадают в одну ячейку, расстояние = 0). К сожалению, при таком количестве ячеек ошибка слишком велика (я получил среднее расстояние 0.47). Вручную считать больше 16 клеток сложно, поэтому попробую позже автоматизировать подсчет. Интересно, сколько клеток понадобится для точного второго знака после запятой?

User avatar
venco
Уже с Приветом
Posts: 1991
Joined: 10 Nov 2004 00:34
Location: MD

Re: Среднее расстояние между двумя точками в...

Post by venco » 08 Jul 2016 04:18

К сожалению, этот метод не подходит для вычислений вручную если делить на меньшие квадраты. В уравнении получается слишком много разных корней, и его можно решить только численно.
При разбиении на 9 квадратов получается 0.5320, на 16 - 0.5280.

User avatar
perasperaadastra
Уже с Приветом
Posts: 20128
Joined: 21 Feb 2009 22:55
Location: Лох Онтарио

Re: Среднее расстояние между двумя точками в...

Post by perasperaadastra » 08 Jul 2016 05:48

Я имел в виду чисто численный метод, когда точки могут находиться только в центре клеток внутри квадрата. В принципе, тоже самое, что делать симуляцию по произвольным точкам...

Code: Select all

int m = 10; 						// квадратный корень от числа клеток в квадрате 
double dist = 0;					// среднее расстояние

for (int i = 1; i <= m; i++) {									// коорд x1
  for (int j = 1; j <= m; j++) {								// коорд y1
    for (int k = 1; k <= m; k++) {							// коорд x2
      for (int l = 1; l <= m; l++) {						// коорд y2
        dist = dist + sqrt(sq(k-i)+sq(l-j))/(m*m*m*m);	// расстояние между (x1,y1) и (x2, y2)
      }
    }
  }
}
dist = dist / m; 				// нормирование
print (dist);
Для 100 клеток: 0.5187
Для 400 клеток: 0.5208
Для 900 клеток: 0.5211
Для 10,000 клеток: 0.5214

Return to “Головоломки”