algorithm - Construct Rectangle 算法如何工作？

Question

我正在研究一个脑筋急转弯问题，并且我有正确的解决方案，但我想澄清它是如何工作的。更具体地说，为什么这里需要面积的平方根，解每次递减什么值直到面积模 w == 0？是否有使用面积平方根的几何原理？

解决方法:

public int[] constructRectangle(int area) {
    int w = (int)Math.sqrt(area);
    while (area%w!=0) w--;
    return new int[]{area/w, w};
}

问题:

构造矩形添加到列表

对于网络开发人员来说，知道如何设计网页的大小非常重要。那么，给定一个特定的矩形网页面积，你现在的工作是设计一个矩形网页，其长度 L 和宽度 W 满足以下要求:

1. 您设计的矩形网页的面积必须等于给定的目标面积。

2. 宽度W不能大于长度L，即L >= W。

3. 长度L和宽度W之间的差异应尽可能小。

您需要依次输出您设计的网页的长度L和宽度W。

例子:

输入:4

输出:[2, 2]

解释:目标区域为4，所有可能的构造方式为[1,4]、[2,2]、[4,1]。但是根据需求2，[1,4]是非法的；根据要求 3，[4,1] 与 [2,2] 相比不是最优的。所以长度L为2，宽度W为2。

Answer 1

int w = (int)Math.sqrt(area);

找到最接近 area 的 sqrt 的整数 w

while (area%w!=0) w--;

递减w，直到它分成区域，没有余数。

return new int[]{area/w, w};

如果w分成area无余数，那么高度一定是area/w。

从 area 的平方根开始意味着您的矩形的高度和宽度将尽可能接近。

当然，如果您的面积是质数，那么您最终会得到 w = 1 h = area。