matrix - 为具有 n 个元素及其比例的给定范围的表找到最佳列和行大小

Question

我正在寻找一种从 n 个元素创建表格的最佳方法，以便理想情况下没有空单元格，但同时表格维度列/行的比例变得尽可能接近 1。

当然，如果 n 是一个平方数，那么从那时起就很容易了

cols = rows = sqrt( n );

如果 n 是一个素数，很明显会有空单元格，所以我目前处理这个问题的方法是：

rows = floor( sqrt(n) );
cols = ceil( n / rows  );

对于所有其他情况，我的计划是获取 n 的主要因素，然后搜索所有可能的排列，以寻找其组合比例最接近 1 的排列。

所以我的问题是：有没有更好的方法来做到这一点？或者至少有一种方法不必测试主要因素的所有可能组合？

Answer 1

不是对 进行素数分解，而是n从平方根开始，然后找到下一个更大（或更小——没有区别）的因子。这对因素将最接近平方根，因此最接近 1:1 的比例。

Answer 2

这是我如何实现类似的一些伪代码：

int rowCount;
int colCount;

double tempSQR = SquareRoot(cellCount);
int maxRowCount = RoundAwayFromZero(tempSQR);

if(tempSQR == maxRowCount)
{
   rowCount = maxRowCount;
   colCount = rowCount;
}
else if(cellCount is Even)
{
   rowCount = Min(cellCount/2, maxRowCount);
   colCount = RoundAwayFromZero(cellCount/rowCount);
}
else if(cellCount> 1)
{
   rowCount = Min((cellCount+ 1)/2, maxRowCount);
   colCount = RoundAwayFromZero((cellCount+ 1)/rowCount);
}

if(rowCount * colCount < cellCount)
    rowCount++;