Нахождение оптимального размера столбца и строки для таблицы с n элементами и заданным диапазоном для ее пропорции

Question

Я ищу оптимальный способ создания таблицы из n элементов, чтобы в идеале не было пустых ячеек, но в то же время пропорция столбцов / строк измерений таблицы становилась как можно ближе к 1.

Конечно, если n - квадратное число, то с тех пор это легко

cols = rows = sqrt( n );

Если n - простое число, также ясно, что будут пустые ячейки, поэтому мой текущий способ справиться с этим:

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

Для всех остальных случаев мой план состоит в том, чтобы получить простые множители n, а затем найти во всех возможных перестановках те, чья комбинация имеет пропорции, наиболее близкие к 1.

Итак, мой вопрос: есть ли лучший способ сделать это? Или, по крайней мере, есть способ не проверять каждую возможную комбинацию основных факторов?

Answer 1

Вот некоторый псевдокод того, как я реализовал нечто подобное:

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++;

Answer 2

Вместо простой факторизации n начните с квадратного корня и найдите следующий больший (или меньший - без разницы) фактор.Эта пара факторов будет ближе всего к квадратному корню и, следовательно, ближе всего к пропорции 1: 1.