Здравствуйте Bell, Вы писали:

B>привет всем!

B>есть следующая задачка: имеется окружность некоторого диаметра D, и имеется другая окружность меньшего диаметра d. требуется определить, какое количество окружностей диаметра d можно вписать в окружность с диаметром D.
Ну, готового решения я не знаю. Однако вот несколько мыслей:
1. Можно решить обратную задачу — найти минимальное D/d для N окружностей, такое, что круг диаметра D покрывает все окружности.
2. Как ее решать? Точное аналитическое решение, скорее всего, отсутствует.
3. Для случая большого N можно получить оценку следующим способом:
— берем коэффициент плотной упаковки (окружности заполняют плоскость гексагонально-симметричной сеткой, дырок столько же, сколько окружностей, площадь каждой дырки Sh=(r*r*Srqt(3))-3*1/6PI*r^2=Sqrt(3)*r^2-1/2Pi*r^2=So*(sqrt(3)-PI/2)/PI=So*k, где So — площадь кажной окружности.
— Поскольку каждая окружность занимает (k+1)So, то N окружностей займут N*(Sqrt(3)+PI/2)/PI*So;
— Таперича берем и строим окружность такого диаметра, площади которой будет достаточно:
R^2 = (r^2)*N(k+1);
— итого, R = r * Sqrt(N(k+1)).
— ясен пень, мы оптимисты. Это нижняя оценка диаметра. Насколько мы могли промахнуться? Верхняя оценка требуемой площади получится из следующих соображений: Вдоль большой окружности уместятся примерно R/r окружностей маленьких. Каждая из них может торчать максимум на половину своего диаметра, т.е. "не влезшая площадь" будет равна Sqrt(N(k+1))*PI*r^2/2. Погрешность площади растет как корень из N, а сама площадь — как N. То есть, относительная ошибка ~ N^(-0.5). Уже неплохо.
— Финальное уравнение принимает вид:
R^2=(r^2)(N(k+1))+Rr/2.
решаем его относительно N:
N = ((R/r)^2 — (R/2r))/(k+1)
для отношения R/r равного 10, N получится примерно 90. Погрешность у нас равна одной десятой... нда... То есть в 80 карандашей мы точно запихаем. Для R/r=100, получим примерно 8619 с погрешностью в один, примерно, процент.
Есть еще пара идей, как считать для случая малых отношений.
Ессно, мы тут программеры, так что надо написать программу, которая оптимально размещает окружности и строит диаметр. Уверен, что можно выполнить ее за время N*log(N). В хорошем случае за N.