有多少块可以被包装成一个圈？ [英] How many squares can be packed into a circle?

问题描述

多少尺寸的平方的在的×的在的可包装成方圆的研究的一圈？

How many squares of size a×a can be packed into a circle of radius R?

我不需要的溶液。我只是需要某种开始的想法。

I don't need a solution. I just need some kind of a starting idea.

推荐答案

我写这么长的回答道歉。我的做法是先从理论上的最大值和最低保证。当你处理这个问题，你可以使用这些值来确定如何好，你使用任何算法。如果你能想到更好的最小的，那么你可以使用这个来代替。

I apologise for writing such a long answer. My approach is to start with a theoretical maximum and a guaranteed minimum. When you approach the problem, you can use these values to determine how good any algorithm you use is. If you can think of a better minimum then you can use that instead.

我们可以通过简单地利用圆的面积定义为问题的上限

We can define an upper limit for the problem by simply using the area of the circle

Upper Limit = floor( (PI * (r pow 2)) / (L * L) )

其中，L是您正在包装且r是要包装的平方成圆的半径的二次方的宽度或高度。我们相信这是一个上限，因为一）我们必须有一个独立的箱数和b），我们可以不占用更多的空间比圆的面积。 （正式证明将工作某处沿着假设我们有一个比此更框，然后方框的面积的总和将大于该圆的面积更大的线）。

Where L is the width or height of the squares you are packing and r is the radius of the circle you are packing the squares into. We are sure this is an upper limit because a) we must have a discrete number of boxes and b) we cannot take up more space than the area of the circle. (A formal proof would work somewhere along the lines of assume we had one more box than this, then the sum of the area of the boxes would be greater than the area of the circle).

因此​​，与在手的上限，我们现在可以采取的存在各界的任何解决方案，并把它称为最小的解决方案。

So with an upper limit in hand, we can now take any solution that exists for all circles and call it a minimum solution.

那么，让我们考虑一个解决方案，通过采取一看我们能适应圆内最大的广场存在各界。

So, let's consider a solution that exists for all circles by taking a look at the largest square we can fit inside the circle.

您可以适应圈内最大的广场对perimiter 4分，并有一个宽度和长度的sqrt（2）*半径（通过使用毕达哥拉斯定理并使用半径为短边的长度）

The largest square you can fit inside the circle has 4 points on the perimiter, and has a width and length of sqrt(2) * radius (by using pythagoras' theorem and using the radius for the length of the shorter edges)

所以，我们注意到的第一件事情是，如果的sqrt（2）*半径小于你的平方大小，那么你就不能在圈内适合任何广场，因为毕竟，这是你能适应最大的广场。

So the first thing we note is that if sqrt(2) * radius is less than the dimension of your squares, then you cannot fit any squares in the circle, because afterall, this is the largest square you can fit.

现在我们可以做一个简单的计算来划分这个大正方形分成正方形的规则网格使用您指定的L，这将给我们至少有一个解决问题的办法。所以，你必须sqaures这个最大的正方形内的网格。广场，你可以融入这个这个网格中的一行数为

Now we can do a straightforward computation to divide this large square into a regular grid of squares using the L you specified, which will give us at least one solution to the problem. So you have a grid of sqaures inside this maximum square. The number of squares you can fit into one row of this this grid is

floor((sqrt(2) * radius)/ L)

所以这个最小的解决方案宣称可以有至少

And so this minimum solution asserts that you can have at least

Lower Limit = floor((sqrt(2) * radius)/ L) pow 2

在圆内正方形的数量。

number of squares inside the circle.

所以，如果你迷路了，所有我所做的就是我能适应圈子里面，然后收拾尽可能多的方块地进入里面的规则网格最大的广场，给我至少有一个解决方案。

So in case you got lost, all I did was take the largest square I could fit inside the circle and then pack as many squares as possible into a regular grid inside that, to give me at least one solution.

如果你得到一个答案，在0这个阶段，你不能在圆内适合任何方块。

If you get an answer at 0 for this stage then you cannot fit any squares inside the circle.

现在手持theoreitical最大和降到最低，你就可以开始尝试任何类型的启发式算法你喜欢包装广场。一个简单的算法是只拆圈成排，适合许多sqaures，你可以到每一行。然后，你可以把这个最小为准则，以确保您想出了一个更好的解决方案。如果你想花更多的处理能力寻找一个更好的解决方案，您使用的理论作为指导你是理论上最好的距离。

Now armed with a theoreitical maximum and an absolute minimum, you can start trying any sort of heuristic algorithm you like for packing squares. A simple algorithm would be to just split the circle up into rows and fit as many sqaures as you can into each row. You can then take this minimum as a guideline to ensure that you came up with a better solution. If you want to spend more processing power looking for a better solution, you use the theoretical as a guideline for how close you are to the theoretical best.

如果你关心这个，你可以制定出什么最大和覆盖的最小理论率最低的算法我idenfied给你。最大的广场总占地面积一个固定比例（π/ 4或约78.5％的圈子，我认为内部区域）。因此，理论上的最大最小值为78.5％覆盖。而最小的非平凡（即非零）理论上的最小是当你只能容纳1万最大的广场，这恰好最大的广场，你可以当你正在收拾的方块是1大于一半的宽度和高度内适合在圈内。基本上你占用内广场刚刚超过25％，与1挤满广场，这意味着你会得到20％左右的近似覆盖

And if you care about this, you could work out what the maximum and minimum theoretical percentage of cover the minimum algorithm I idenfied gives you. The largest square always covers a fixed ratio (pi/4 or about 78.5% of the internal area of the circle I think). So the maximum theoretical minimum is 78.5% cover. And the minimum non-trivial (ie. non zero) theoretical minimum is when you can only fit 1 square inside the largest square, which happens when the squares you are packing are 1 larger than half the width and height of the largest square you can fit in the circle. Basically you take up just over 25% of the inner square with 1 packed square, which means you get an approximate cover of about 20%

这篇关于有多少块可以被包装成一个圈？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！