屏幕最大平方的计算

Question

可能重复： 将正方形打包成矩形

我需要计算出最有效的方块大小来填充屏幕，

如果你看下面的图片，有不同的屏幕大小和平方计数。我需要一个算法来计算x轴平方计数和y轴平方计数，这将最有效地填充屏幕(最小空面积将在填充平方后留下)。

我看了下面的帖子，但答案并不能解决我的问题。

将正方形打包成矩形

1 -平方计数可以更改(3-5-10等等)

2 -屏幕大小可以是不同的

例如，

• 在1280 x 800和15平方？
• 八百乘四百八十，十二平方？
• 在600x1024和9平方？
• 720x1280和45平方？

**我需要一个计算正方形宽度(高度和宽度相同)的算法**

如果您查看图像3和图像3-1之间的差异，您将看到图像3-1使用屏幕更有效果，因为没有使用的区域较少。

图像3

​

或者这也许是一个更好的填充方法：

图像3-1

​

​

如果您查看图像4和图像4-1之间的差异，您将看到图像4-1使用屏幕的效果更高，因为未使用的区域较少。

图像4

​

​

** 4.图像必须如下所示，因为屏幕上的未使用区域较少**

图像4-1

​

Answer 1

我相信你所说的“有效”是面积越大的方块越好。

让：

A:X轴平方计数

B:y轴平方计数

正方形的大小(一侧的长度)

W:屏幕宽度

H:屏幕高度

C:要放置的方格数

然后我们就有了

a * s <= w
b * s <= h
a * b >= c

有了这些不等式，就有可能找到s的上界。第四个例子，其中c= 20，w= 1280，h= 800。

a * s <= 1280
b * s <= 800
a * b >= 20

A*b= (1280 / s) * (800 / s) >= 20 -> s^2 <= (1280*800) / 20 ->s <= 226，27

有了s的上界，我们可以估计a和b as；

A*s <= 1280 ->a ~= 5,6568 b*s <= 800 -->b ~= 3,53

对于这些值，不等式a*b >= 20不成立。

但a和b都必须是整数。然后，我们尝试了a和b可以得到的4种可能性：

a = 5, b = 3 // round down both
a = 5, b = 4 // one down, one up
a = 6, b = 3 // one down, one up
a = 6, b = 4 // round up both

由于a*b >= 20，第一和第三种情况被排除为有效的答案。选择a= 5，b=4作为下一步的答案，因为它们的乘积更接近所需的平方数。

Answer 2

您要寻找的是显示的宽度和高度之间的最大共同因素。

由于大多数显示器的比例为4:3或16:9，所以最大的共同因素将给出您可以用来填充显示区域的最大平方。

在您的400 x 400像素显示，最大的共同因素是400，一个方块将填补显示。

在您的1280 X 800像素显示，最大的共同因素是160。你需要40个正方形(8x5)来填充显示器。

如果您想要计算所有显示大小的最大公共因子，答案是1。每个像素都是正方形。您应该为要支持的每个显示大小计算一个单独的最大公共因子。