здравствуйте, многоуважаемые. задача следующая. есть круг R = 225 нужно на нем разместить как можно больше кругов радиуса r = 25 существует ли алгоритм для решения этой задачи? буду очень благодарен за любые идеи или ссылки http://lasi.lynchburg.edu/peterson_km/public/Gov2010/foxy2/pdfs/2DProof.pdf рисунок здесь задан 24 Дек '13 23:14 рапира |
Я так понимаю, что круги радиуса 25 размещаются не на круге радиуса 225, а вокруг него. Такая задача имеет довольно простое решение, хотя в комбинаторной геометрии бывают и очень сложные задачи на оптимальные упаковки и т.п., где точные решения во многих случаях не известны. Здесь нужно сделать так: рассмотреть круг радиуса $%r$%, касающийся большого круга радиуса $%R$%, и из центра $%O$% большого круга провести касательные к кругу маленькому. При этом получится какой-то угол, значение которого выражается через тригонометрические функции. Зная этот угол, например, в градусах, мы делим на него число 360 и округляем до ближайшего целого в сторону уменьшения. Это и даёт максимальное значение для числа маленьких кругов. Например, если угол равен 20 градусам, то можно разместить 18 кругов, а если угол равен 7 градусам, то 360/7=51,... и поэтому 51 круг разместить можно, а 52 уже нет. Формула для вычисления угла выводится просто. Пусть $%O_1$% -- центр маленького круга, касающегося большого. Расстояние $%OO_1$% равно $%R+r$%. Если $%A$% и $%B$% -- точки касания лучей с началом $%O$%, то нас интересует угол $%AOB$%. Он равен $%2\alpha$%, где $%\sin\alpha=O_1A:O_1O=r/(R+r)$%. Угол теперь выражается через арксинус, и если его выражать в радианах, то на него надо поделить полный угол $%2\pi$%. Получится такое значение -- с учётом взятия целой части: $$\left\lfloor\frac{\pi}{\arcsin\frac{r}{r+R}}\right\rfloor.$$ В данной задаче $%r/(r+R)=1/10$%. Значение арксинуса можно приближённо узнать из таблиц, или посчитать на калькуляторе. Оно здесь чуть больше 1/10, и поэтому частное окажется чуть меньше $%10\pi$%. Вычисления показывают, что это $%31,363...$%. Отсюда следует, что максимальное число кругов будет равно $%31$%. В заметке по ссылке проводятся почему-то не касательные, а другие линии. Это приводит к близким, но менее точным оценкам. отвечен 25 Дек '13 0:50 falcao Спасибо большое!
(25 Дек '13 23:31)
рапира
|