一个圆圈可以包装多少个正方形？
一个半径为 R 的圆可以包装多少个大小为 a × a的 正方形？ __
我不需要解决方案。我只需要一个初步的想法。
回答：
很抱歉写这么长的答案。我的方法是从理论最大值和保证最小值开始。解决问题时，可以使用这些值来确定所使用的算法的质量。如果您能想到一个更好的最小值，那么可以使用该最小值。
我们可以简单地使用圆的面积来定义问题的上限
Upper Limit = floor( (PI * (r pow 2)) / (L * L) )其中L是要打包的正方形的宽度或高度，r是要打包正方形的圆的半径。我们确定这是一个上限，因为a）我们必须有离散数量的盒子，b）我们不能占用比圆的面积更多的空间。（形式上的证明将在假设我们有一个比这个多的盒子的地方起作用，然后盒子的面积之和将大于圆的面积）。
因此，有了上限，我们现在可以采用所有圈子存在的任何解决方案，并将其称为最小解决方案。
因此，让我们通过考虑我们可以放入圆内的最大正方形，来考虑一种适用于所有圆的解决方案。
您可以在圆内拟合的最大正方形在准分子上有4个点，其宽度和长度为sqrt(2) * radius（通过使用毕达哥拉斯定理，并使用半径作为较短边的长度）
因此，我们要注意的第一件事是，如果sqrt(2) * radius小于正方形的尺寸，则您无法拟合圆中的任何正方形，因为毕竟这是您可以拟合的最大正方形。
现在我们可以进行简单的计算，使用您指定的L将这个大正方形划分为规则的正方形网格，这将为我们提供至少一个解决问题的方法。因此，在此最大正方形内有一个正方形的栅格。可以放入此网格的一行中的正方形的数量是
floor((sqrt(2) * radius)/ L)因此，此最小解决方案断言您至少可以拥有
Lower Limit = floor((sqrt(2) * radius)/ L) pow 2圆内的平方数。
因此，如果您迷路了，我所要做的就是取一个我可以放入圆内的最大正方形，然后将尽可能多的正方形装入内部的规则网格中，以便给我至少一个解决方案。
如果您在此阶段得到的答案是0，则您无法在圆内拟合任何正方形。
现在有了理论上的最大值和绝对最小值，您可以开始尝试使用任何一种喜欢的用于打包平方的启发式算法。一种简单的算法是将圆分成几行，并在每一行中尽可能多地拟合正方形。然后，您可以将此最小值作为指导，以确保您提出了更好的解决方案。如果您想花费更多的处理能力来寻找更好的解决方案，则可以使用理论值作为您与理论值的接近程度的指导。
而且，如果您对此有所关注，则可以算出我确定的最小算法所能提供的最大和最小理论百分比。最大的正方形始终覆盖固定比例（pi /
4或我认为是圆的内部面积的大约78.5％）。因此，最大理论最小值为78.5％的覆盖率。最小非平凡（即非零）理论最小值是当您只能在最大正方形内容纳1个正方形时发生的情况，当您打包的正方形大于最大正方形的宽度和高度的一半时，就会发生这种情况适合圈子。基本上，您会用1个压缩正方形占据25％的内部正方形，这意味着您可以获得大约20％的覆盖率
以上是 一个圆圈可以包装多少个正方形？ 的全部内容， 来源链接： utcz.com/qa/435293.html
