geometry - 具有给定整数面积和整数边的最小周长矩形

Question

给定一个整数面积 A，如何找到一个矩形的整数边 w 和 h，使得 w*h = A 并且 w+h 尽可能小？我宁愿算法简单而不是高效（尽管在合理的效率范围内）。

实现这一目标的最佳方法是什么？

找出 A 的主要因素，然后以某种方式将它们组合起来以平衡 w 和 h？找到面积最接近 A 的整数边的两个正方形，然后以某种方式在它们之间进行插值？还有其他我没有想到的方法吗？

Answer 1

你只需要找到：

• A 中不大于 sqrt(A) 的最大因子，以及
• 不小于 sqrt(A) 的 A 的最小因子

两者的乘积总是 A，所以这些因素是你的w和h

当然你只需要搜索其中一个，因为一旦你w设置好了h = A / w

Answer 2

这是我头顶上的东西，

从...开始w=1; h=A;

然后迭代w，增加它。每次增加后，w尽量减少h。w*h>A此外，您将需要某种确定 aw/h 组合大小的启发式函数。让我们称之为size(x,y)。

在每个步骤中，您都必须检查 if size(w,h)<size(bestW,bestH)、 wherebestW和是迄今为止您遇到的bestH最佳值。wh

就实施size(x,y)而言，您可以return x+y或return Math.abs(x-y)

因为你只需要不断增加w，直到w>=h并且最初h=A我猜想复杂性在某个地方O(A/2) <= true complexity <= O(2A)

现在来一些伪代码：

w=1;
h=A;

bestW=w;
bestH=h;

while(2*w<=A){
    w++;
    while(w*h>A) {
        h--;
    }
    if(w*h==A && size(w,h)<size(bestW,bestH)){
        bestW=w;
        bestH=h;
    }
}