Как максимизировать размеры сетки с учетом количества элементов

Question

У меня есть n элементы как вход и функция make_grid(n), которые будут вычислять размеры сетки, которая будет содержать элементы. Предположим, что n = 12, тогда функция должна вычислить, что ширина равна 4, а высота 3, а не 1 и 12 или около того. Точно так же, n = 24 должен возвращать 6 и 4.

Я пытался использовать ceil(sqrt(n)), чтобы получить одно измерение, но это не общий случай вообще, и играть со случаями (п даже sqrt(n) == ceil(sqrt(n))) не работал.

Edit: Finding the optimum column and row size for a table with n elements and a given range for its proportion Я уже вижу этот вопрос, но кодирование бросает меня для п = 24 размерностей 5 и 5. Любая помощь?

Answer 1

подход заключается в следующем:

Возьмет целое число n как вход функции. Цель состоит в том, чтобы получить «самую квадратную» таблицу. Как пояснил @John, мы должны вычислить sqrt(n), чтобы получить представление о размерах. С другой стороны, мы должны вычислить все делители n, чтобы сделать выбор ближайших делителей до sqrt(n).

Как выбрать ближайшее низкое значение? мы можем использовать этот совет (Python): finding index of an item closest to the value in a list that's not entirely sorted и получить индекс ближайшего значения в списке делителей, скажем hIndex. Тогда другое измерение можно рассчитать, разделив n на divisors[hIndex] или с помощью нового индекса wIndex = hIndex + 1 и получить divisors[wIndex].

код Питон это (обратите внимание, что я использовал аль ленивые вычисления, чтобы найти делители):

import numbers 
from math import sqrt 

def get_dimensions(n): 
    tempSqrt = sqrt(n) 
    divisors = [] 
    currentDiv = 1 
    for currentDiv in range(n): 
     if n % float(currentDiv + 1) == 0: 
     divisors.append(currentDiv+1) 
    #print divisors this is to ensure that we're choosing well 
    hIndex = min(range(len(divisors)), key=lambda i: abs(divisors[i]-sqrt(n))) 
    wIndex = hIndex + 1 

    return divisors[hIndex], divisors[wIndex] 

Answer 2

Вы ищете номера, которые делят n равномерно, поэтому вам нужно будет вычислить коэффициенты n и взять два, которые наиболее близки к . Один из них будет самым большим фактором, меньшим или равным sqrt(n) (назовите это f), а другой будет n/f.

Однако вы получите странно выглядящие решетки для многих чисел, например, 74 или любого простого числа.

Answer 3

Вы ищете алгоритмы целочисленной факторизации.

Проверить здесь: Efficiently finding all divisors of a number

И здесь: http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms

Тогда просто выбрать пару факторов, которые лучше всего соответствует вашим целям.