здравствуйте, многоуважаемые. задача следующая.

есть круг R = 225 нужно на нем разместить как можно больше кругов радиуса r = 25 существует ли алгоритм для решения этой задачи? буду очень благодарен за любые идеи или ссылки

http://lasi.lynchburg.edu/peterson_km/public/Gov2010/foxy2/pdfs/2DProof.pdf рисунок здесь

задан 24 Дек '13 23:14

10|600 символов нужно символов осталось
0

Я так понимаю, что круги радиуса 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

Спасибо большое!

(25 Дек '13 23:31) рапира
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,314

задан
24 Дек '13 23:14

показан
1037 раз

обновлен
25 Дек '13 23:31

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru