10*10的正方形里,最多可以放多少个直径为1的圆?不是100个!

算法相关 徐 自远 1133℃

为什么不是

100个

昨天文章发出后,后台也收到了许多留言,大家也针对末尾的题目,给出了不同的答案。

五花八门的答案,究竟哪一个才是正确的呢?现在就让小天来给大家揭晓吧。

答案是106个。

在昨天的题目中,我们故意放了下图,其实就是想看看大家能否试着突破定势思维。

大家想想。一个硬币最多能和几个硬币相邻?

六个 ,那如歌一个格子放一个硬币,那是占几个呢?

四个,这也意味着有大量的空间被浪费了。

所以,重新排列后,这样就有105个圆了。

然后聪明的你是不是发现还有空隙?那就将它利用起来!

这样安排就又多了个10排的,神奇的又插了一个进去。

那么,还能不能再用什么神奇的方法再搞一个进去呢?

不好意思,不可能了…强扭的瓜不甜,强塞的圆不……


我们现在来用数学证明不能放下107个圆呢?有两种思路

  • 1、把正方形看做一个框,把圆看成光滑的小球,然后你取一个球,使劲压,看看能不能压进去。

当然现实中是没有绝对光滑小球的,实际没法做这个实验。

但数学上可以定义小球与小球,小球与方框之间的势能,然后用各种算法降低势能,看看最小值能不能降到零即可。

  • 2、取n个小球,然后放进一个方框,方框使劲收缩,收缩到无法再收缩为止。

最终结果就是最优平面圆堆积,这种方法比上一种要复杂一些。

但是数学家一般喜欢研究第二个,因为至少对于正方形等圆嵌入来说,解决了第二个也就解决了第一个。对于矩形才会用第一种方法。

但这个思路说得轻巧,可数学上怎么定义使劲收缩呢?

Talk is cheap, Show me the code!

https://bura.brunel.ac.uk/bitstream/2438/7455/1/FulltextThesis.pdf

这本书整理了这方面的研究成果,第72页讨论了圆塞入正方形,后面还有更难的不相等图形塞进不规则边框。

书中没给结果,算法都是伪代码,不用完全看懂公式也能复现。

运算时间要有心理准备,一次差不多要跑半个小时。

计算结果表明106个直径为1的圆能放进边长9.996960840529825的正方形

但是如果要放置107个直径为1的圆就要边长10.09975184413619的正方形

所以确实10*10的正方形只能塞下106个直径为1的圆。

注意有轻微的形变,比如右下那个没对齐,上边框第五个圆脱离了边框,但是只有0.4%,整体上和原来差不多。

最后,附上全部的绘图代码:

所以,你现在知道它为什么只能塞进106个圆了吗?

 

 

10*10的正方形里,最多可以放多少个直径为1的圆?不是100个!http://t.bytedance.com/YC38uK/

转载请注明:徐自远的乱七八糟小站 » 10*10的正方形里,最多可以放多少个直径为1的圆?不是100个!

喜欢 (0)

苏ICP备18041234号-1 bei_an 苏公网安备 32021402001397号