標籤：

C/C++演算法生活趣味數學

如何在一個正方形畫n個相同半徑的最大的圓？

12-03

我們在小的時候一定知道在一個正方形里，畫一個最大的圓，那麼那個圓的直徑必定是正方形的邊長圓心則為對角線的交點，如果畫4個圓，那麼圓直徑必定為正方形邊長的一半，圓心則為對角線上距離端點√2*邊長/4的所有4個點上。
那麼如果我們將這類題目泛化，如果要畫2個？3個？5個？6個？甚至更高？則有什麼方法可以求解呢？

查了下叫 Circle packing in a square , 算是一定程度上被解決了吧

當然想來也有逆問題 Square Packing In A Circle....

再想想...呃...三角形...正方形...圓...我們一次性提出來了9個難題呢!!!

其中正方形塞進正方形最簡單,圓形塞進圓形最難......

==================================================

$1sim 5$ 的情況還是不難解的,有興趣可以試試

$n^2$ 時的平凡解不說了,此時正方形邊長為n,空間利用率 $[d({n^2}) = frac{{{n^2}pi }}{{{{(2n)}^2}}} = frac{pi }{4} approx 78.5\% ]$

$n=2$ 時的圖形有兩個對稱軸,不過顯然不選倆半徑之和當邊長...

易得邊長就是 $2+sqrt{2}$ ,空間利用率 $[d(2) = frac{{2pi }}{{{{(2 + sqrt 2 )}^2}}} = 53.9\% ]$

$n=3$ 還是兩種對稱性,不過這個就要都試一下才知道哪個更小了

(偷偷測得)這個比較小,算出來此時邊長 ${displaystyle 2+{frac {sqrt {2}}{2}}+{frac {sqrt {6}}{2}}}$

$[d(3) = frac{{3pi }}{{{{left( {frac{{sqrt 2 }}{2} + frac{{sqrt 6 }}{2} + 2} ight)}^2}}} approx 78.5\% ]$

========================================

然後到這邊你可能想,是不是先最密堆積然後求最小外接正方形...

恭喜你答錯了...n=7是這樣的....

Nevermind...我也猜錯了...這有點反直覺...其中一個圓居然有如此大的活動空間...

再次說明直覺算個鳥.....接下來的第10,第11個都是非對稱的...

n很大的時候就退化(???)為平面密堆積問題.

============================================

詳見:Packing problems

感覺Mathworld不是被牆了就是伺服器掛了:Circle Packing -- from Wolfram MathWorld

有Springer許可權的話可以看看這本:New Approaches to Circle Packing in a Square

如果足夠多的話差不多是個最密堆積的問題，不過對於N很小的時候可能作用就不太大了。平面上的最密堆積是交錯著讓中心連線是正三角形，然後可以考慮幾種變種：

第一行剛好緊密地排進N個，第二行N-1個，第三行N個……直到排不下
第一行和第二行都是N個，恰好讓第一行和第二行都排滿，然後直到排不下
在1或者2的基礎上縮小圓的半徑，但不增加每行圓的數量，從而減少每行的間距，來額外擠進一行
前面採用1的排列，最後一行改變排列方式，排進N個，中心連線是正方形

應該可以編程序算出每種情況下圓的半徑以及總共的圓的數量

推薦閱讀：

※兩個正四面體拼在一起組成的形狀算不算正六面體？
※如果有數學之神，祂會有什麼能力？
※為什麼直徑為一萬億單位的圓和卡特蘭數有關係？
※證明一定可以找到兩個位置，將黑白珠子各自平分。？
※一道王者榮耀腦力風暴求解題思路？

TAG:生活 | 演算法 | 趣味數學 | C/C++ |