首頁猿問為 N 個單元格的網格找到最佳行和列

為 N 個單元格的網格找到最佳行和列

JavaScript

holdtom 2023-03-10 13:48:29

我正在嘗試創建一個網格，該網格必須具有足夠的行和列以適應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有沒有其他方法可以優化我的網格以獲得盡可能少的額外單元格？我覺得我的嘗試不是最佳的。

查看完整描述

2 回答

莫回無

TA貢獻1865條經驗獲得超7個贊

對于偶數 length m，我們可以很容易地說：

cols = m / 2

rows = 2

對于奇數長度m，我們需要分解m。幸運的是，只需要一個非平凡的（1 或m）因子就足夠了。通過以下算法：

for(var i = 3; i * i < m; i += 2){

if(m % i == 0)

return i;

}

return -1;

如果結果是-1，它將是質數，因此，最終結果將是：

cols = (m+1)/2

rows = 2

否則，如果我們調用 factor k，結果將是：

cols = m / k

row = k

您可以在以下內容中找到最終結果：

function factor(m){

// if m is even

if(m % 2 == 0)

return [2, m/2]

for(var i = 3; i * i < m; i += 2){

// m is odd and not prim

if(m % i == 0)

return [i, m/i];

}

// m is odd prime

return [2, (m+1)/2];

}

console.log(factor(8));

console.log(factor(10));

console.log(factor(11));

console.log(factor(15));

此功能的結果已優化（根據您的定義）。因為余數對于非素數為零，而1對于素數則為零。

反對回復 2023-03-10

繁華開滿天機

TA貢獻1816條經驗獲得超4個贊

假設這些數字永遠不會大到天文數字，您可以只檢查每個數字從平方根開始的擬合程度，并在給定評估函數的情況下跟蹤最佳數字，該評估函數既考慮了余數又考慮了方差。所以像：

function optimizeRectangle(N) {

let bestRectangle = null;

let best_evaluation = Infinity;

let start_row = Math.floor(Math.sqrt(N));

// Maximum aspect ratio of 3:1

for (let offset = 0; offset < start_row / 2; offset++) {

let row = start_row - offset;

let col = Math.ceil(N/row);

let remainder = row * col - N;

let evaluation = remainder + offset; // or some other function of remainder and offset

if (evaluation < best_evaluation) {

best_evaluation = evaluation;

best_rectangle = [row, col];

}

return best_rectangle;

}

請注意，我實際上并沒有運行這段代碼，所以如果沒有運行，請將其視為偽代碼。

反對回復 2023-03-10

2 回答
0 關注
135 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

為 N 個單元格的網格找到最佳行和列

為 N 個單元格的網格找到最佳行和列

2 回答

添加回答