Математическая задачка

← →
SP (2009-09-14 16:55) [0]

При реализации одного алгоритма связанного с волновім поиском маршрута, у меня возникло затруднение.
Для более лучшего понимания, суть проблемы у меня получилось описать в математическом виде... Получилась такая задачка:

На координатной плоскости проведены 2 круга с радиусом R с центрами в точках с целочисленными координатами. Каково максимальное значение числа N, при котором для всех случаев расположения этих кругов с расстоянием между центрами не превышающим N существует хотя бы одна точка с целочисленными координатами принадлежащая обоим кругам?

Но я так и не смог пока ее решить.
Так как здесь на форуме обитает большое кол-во умных людей, может вы постараетесь мне в этом помочь?
PS Тем более что пятничных задачек уже давно нет....

← →
SP (2009-09-14 16:57) [1]

М-да. с пятничными задачками ошибся... Все-таки увидет топик МВО... Но тем не менее в последние годы это редкость...

← →
Дуп (2009-09-14 18:01) [2]

> МВО.

Стыдно товарищ. МВо. :)

← →
MBo © (2009-09-14 18:33) [3]

Вообще, как мне кажется ,проблематично даже просто найти количество целых точек в пересечении кругов.
Для количества точек в одном круге есть формула, но она не замкнутая, сумма ряда:
http://mathworld.wolfram.com/GausssCircleProblem.html

← →
SP (2009-09-14 18:55) [4]

Ну вообще на самом деле смысл таков.
Есть квадратно гнездовое поле (потому и целочисленные координаты). И есть некая штуковина, которая может прыгать с одной ячейки в другую но на расстояние не более R.

известно что растояние между некими двумя ячейками L.
Вот нужно определить может ли эта штуковина гарантированно допрыгать из одной ячейки в другую за 2 прыжка.

← →
MBo © (2009-09-14 18:59) [5]

>известно что растояние между некими двумя ячейками L.
расстояния евклидовы или манхэттенские (сумма модулей разниц координат) ?

← →
SP (2009-09-14 19:03) [6]

расстояния евклидовы...

← →
Дуп (2009-09-14 19:04) [7]

> MBo © (14.09.09 18:59) [5]

Раз круги, то скорее всего про Евклида речь.

← →
MBo © (2009-09-15 05:30) [8]

>Дуп (14.09.09 19:04) [7]
Ну да. Из-за ходов по клеточному полю сомнения были.

>может ли эта штуковина гарантированно допрыгать из одной ячейки в другую за 2 прыжка

А если просто целочисленное окружение средней точки рассматривать?

Немного подумал и вот что получилось.
Возьмём сетку, ось Х направлена вправо, ось Y вверх.
Сответсвенно напрвление вправо =0 градусов, а вверх = 90 градусов.
Точку отсчёта помечаем в центр одной из клеток сетки.
Проводим круг радиуса R.
Отмечаем клетки входящие в круг (получившуюся фигуру назовём псевдокруг).
Создаём второй псевдокруг совпадающий с первым.
Сдвигаем псевдокруг2 вправо, пока не будут потеряны общие клетки.
Делаем шаг назад, находим растояние N1.
Сдвиг:
. Сдвигаем псевдокруг2 вверх до потери общих точек.
. Делаем шаг назад (1 вниз)
. Если оказались в той же точке, сдвигаем влево.
. Запоминаем Ni
. Если центр пседокруга2 оказался над центром псевдокруга1, то прекращаем Сдвиг, иначе повторяем сдвиг.
Находим минимальный Ni (N=min(N1,...Ni,...))

Примечания:
1. Представленый алгоритм сдвига содержит ошибки
2. В двух словах: Берём два круга, максимально раздвигаем их в различных направлениях. Запоминаем полученые растояния и находим минимальное из них.
3. С учётом [4] центр круга находится в центре одной из клеток. Как следствие, псевдокруги получаются семетричными относительно вертикали и горизонтали. Т.е. результаты полученые для одной четвертики верны и для остальных 3х. Более того четвертинка семетрична относительно оси в 45 грудусов. Поэтому достаточно проверить только первые 45 градусов.

← →
Achpile (2009-09-15 13:01) [10]

если сказано, что хотя бы одна, то возможно N=2R
тогда общая точка (R; 0) к примеру... если, конечно R - тоже целое...

← →
SP (2009-09-15 16:05) [11]

> если сказано, что хотя бы одна, то возможно N=2R
> тогда общая точка (R; 0) к примеру... если, конечно R -
> тоже целое...

R может быть любым... не обязательно целым.

для мелких значений R значение N становится очевидным:
R=1 N=2
R=1.42 N=2*sqrt(2)
R=2.24 N=3*sqrt(2)

А вот чем дальше, тем труднее это вычислить
в идеале хотелось бы получить некую формулу зависимости N от R
но учитывая то что точное решение возможно будет очень трудно найти, можно попробовать найти приблизительные решения... т.е. не максимальное значение N, а хотя бы близкое к максимальному...

Например можно уверенно сказать, что двойной прыжок гарантирован для N=2*R-2*sqrt(2)
но на глаз заметно, что такое решение не самое лучшее, а для мелких значений R - вообще неприемлимо.

Численное моделирование
procedure SelSort(var A, B: array of Double; l, r: Integer); var i, j, min: Integer; t: Double; begin for i := l to r - 1 do begin min := i; for j := i + 1 to r do if A[j] < A[min] then min := j; t := A[i]; A[i] := A[min]; A[min] := t; t := B[i]; B[i] := B[min]; B[min] := t; end; end; procedure TForm2.Button31Click(Sender: TObject); var N, NN, dx, dy, dx2, dy2, Cnt: Integer; r, s: Double; rr, ss: array of Double; begin N := 10; NN := N * (N + 1) div 2; SetLength(rr, NN); SetLength(ss, NN); Cnt := 0; for dy := 0 to N - 1 do for dx := 0 to dy do begin r := Hypot(dx, dy)/2; dx2 := Round(dx/2); dy2 := Round(dy/2); s := Max(Hypot(dx2, dy2), Hypot(dx - dx2, dy - dy2)); rr[Cnt] := r; ss[Cnt] := s; Inc(Cnt); Memo1.Lines.Add(Format("%d: %d %f %f",[dy, dx, r, s])); end; Memo1.Lines.Add("-----------"); SelSort(rr, ss, 0, NN - 1); for dx := 0 to NN - 1 do begin Memo1.Lines.Add(Format("%f %f",[rr[dx], ss[dx]])); Series2.AddXY(rr[dx], ss[dx]); end; end;

Математическая задачка Найти похожие ветки