带给定整数区域和整数边的最小定界矩形

Question

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

完成此操作的最佳方法是什么？

找出A的主要因素，然后以某种方式将它们结合起来试图平衡W和H？寻找具有最接近A区域的整数边的两个正方形，然后以某种方式在它们之间进行插值？任何其他方法，我没有想到？

Answer 1

你绝对吨需要找到：

• ，是不是比的sqrt（A）大于A的最大因素，
• ，是不是比的sqrt（A）

少A的最小的因素两者的产品永远是A，所以这些因素都是你w和h

当然，你只需要寻找其中的一个，因为一旦你有w刚才设置h = A / w

Answer 2

这里的东西顶掉了我的头，

开始w=1; h=A;

然后遍历w，增加了它。在每增加w后，请尝试减少h，只要w*h>A。 另外，您需要一些启发式功能来确定w/h组合的大小。我们称之为size(x,y)。

在每一步中你必须检查是否size(w,h)<size(bestW,bestH)，其中bestW和bestH是w和h你遇到到目前为止的最佳值。

至于的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; 
    } 
}