为 N 个单元格的网格找到最佳行和列

Question

我正在尝试创建一个网格，该网格必须具有足够的行和列以适应length单元格的数量。这里有些例子：

- Length: 8: 2 rows x 4 cols
- Length: 9: 3 rows x 3 cols
- Length: 10: 5 rows x 2 cols
- Length: 11: 4 rows x 3 cols (with one extra)

我想出了一个解决方案，使用平方根，它给了我一个非常接近的解决方案：

var cols = Math.ceil(Math.sqrt(length));
var rows = Math.ceil(length / cols);

可以有额外的单元格（比如素数），但我更喜欢尽可能地减少它们。这种方法的问题是，当可能有更优化的解决方案时，我得到的是空单元格：

- Length: 8: returns 3 x 3, but 2 x 4 has 0 remainders
- Length: 10: returns 4 x 3, but 5 x 2 has 0 remainders
- Length: 15: returns 4 x 4, but 5 x 3 has 0 remainders

有没有其他方法可以优化我的网格以获得尽可能少的额外单元格？我觉得我的尝试不是最佳的。

Answer 1

对于偶数 length m，我们可以很容易地说：cols = m / 2rows = 2对于奇数长度m，我们需要分解m。幸运的是，只需要一个非平凡的（1 或m）因子就足够了。通过以下算法：for(var i = 3; i * i < m; i += 2){&nbsp; &nbsp; if(m % i == 0)&nbsp; &nbsp; &nbsp; &nbsp; return i;}return -1;如果结果是-1，它将是质数，因此，最终结果将是：cols = (m+1)/2rows = 2否则，如果我们调用 factor k，结果将是：cols = m / krow = k您可以在以下内容中找到最终结果：function factor(m){&nbsp; &nbsp;// if m is even&nbsp; &nbsp;if(m % 2 == 0)&nbsp; &nbsp; &nbsp; &nbsp;return [2, m/2]&nbsp; &nbsp;&nbsp; &nbsp;for(var i = 3; i * i < m; i += 2){&nbsp; &nbsp; &nbsp; &nbsp; // m is odd and not prim&nbsp; &nbsp; &nbsp; &nbsp; if(m % i == 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return [i, m/i];&nbsp; &nbsp;}&nbsp; &nbsp;// m is odd prime&nbsp; &nbsp;return [2, (m+1)/2];}&nbsp;console.log(factor(8));console.log(factor(10));console.log(factor(11));console.log(factor(15));此功能的结果已优化（根据您的定义）。因为余数对于非素数为零，而1对于素数则为零。

Answer 2

假设这些数字永远不会大到天文数字，您可以只检查每个数字从平方根开始的拟合程度，并在给定评估函数的情况下跟踪最佳数字，该评估函数既考虑了余数又考虑了方差。所以像：function optimizeRectangle(N) {&nbsp; let bestRectangle = null;&nbsp; let best_evaluation = Infinity;&nbsp; let start_row = Math.floor(Math.sqrt(N));&nbsp; // Maximum aspect ratio of 3:1&nbsp; for (let offset = 0; offset < start_row / 2; offset++) {&nbsp; &nbsp; let row = start_row - offset;&nbsp; &nbsp; let col = Math.ceil(N/row);&nbsp; &nbsp; let remainder = row * col - N;&nbsp; &nbsp; let evaluation = remainder + offset; // or some other function of remainder and offset&nbsp; &nbsp; if (evaluation < best_evaluation) {&nbsp; &nbsp; &nbsp; best_evaluation = evaluation;&nbsp; &nbsp; &nbsp; best_rectangle = [row, col];&nbsp; &nbsp; }&nbsp; }&nbsp; return best_rectangle;}请注意，我实际上并没有运行这段代码，所以如果没有运行，请将其视为伪代码。