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

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

Конечно, если n является квадратным числом, тогда это легко

cols = rows = sqrt( n );

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

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

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

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


matrix language-agnostic prime-factoring
person Quasimondo    schedule 20.07.2010    source источник

Ответы (2)


arrow_upward
0
arrow_downward

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

person Jerry Coffin    schedule 20.07.2010
comment
Это похоже на то, что я делаю, если n простое число. Но в определенном диапазоне пропорций мне важнее, чтобы не было пустых ячеек, чем чтобы таблица была квадратной. Я не уверен, что таким образом я всегда буду получать наилучшие возможные размеры. - person Quasimondo; 20.07.2010
comment
@Quasimondo: поскольку вы находите факторы размера, вы получите ноль пустых ячеек. Поскольку эти факторы ближе всего к квадратному корню, они дают вам пропорцию, ближайшую к 1: 1, не оставляя пустых ячеек. - person Jerry Coffin; 20.07.2010
comment
О, я неправильно понял раньше. Да, теперь я понимаю. Да, это звучит как хороший способ. - person Quasimondo; 20.07.2010

arrow_upward
0
arrow_downward

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

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++;
person Jacob G    schedule 20.07.2010