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

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

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

Изменить: Поиск оптимального размера столбца и строки для таблицы с n элементами и заданным диапазоном для его пропорции Я уже вижу этот вопрос, но код выдает мне для n = 24 измерения 5 и 5. Любой помощь?


python maximize
person Alejandro Sazo    schedule 03.06.2013    source источник

Ответы (3)


arrow_upward
1
arrow_downward

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

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

person John    schedule 03.06.2013
comment
Действительно, вы правы. В случаях, когда числа, множители которых находятся далеко друг от друга, таблица будет слишком длинной или высокой. Я буду использовать числа, которые остаются в каком-то экранном соотношении, так что это не проблема. Однако я подумаю факторами и srqt(n) идеей. - person Alejandro Sazo; 04.06.2013
comment
Допустим, n = 50, а floor(qrt(50)) = 7, но 7 не является фактором D: - person Alejandro Sazo; 04.06.2013
comment
Ты прав. Это не. Хотя я не это предлагал. Множители 50 — это 1, 2, 5, 10, 25 и 50. Таким образом, два ближайших множителя к sqrt(50) — это 5 и 10, что дает вам сетку 5 x 10 или 10 x 5. - person John; 04.06.2013
comment
ОК, я понимаю вашу точку зрения, я должен хорошо прочитать ответ, прежде чем что-либо спрашивать. Спасибо за ваше терпение, я понял ваше решение. - person Alejandro Sazo; 04.06.2013
comment
Я не знаю, хорошо ли это сказано по-английски, но на самом деле я смотрю не на множители n, я смотрю на делители n - person Alejandro Sazo; 04.06.2013

arrow_upward
1
arrow_downward

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

Проверьте здесь: Эффективный поиск всех делителей числа

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

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

person paddy    schedule 03.06.2013

arrow_upward
0
arrow_downward

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

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

Как выбрать ближайшее минимальное значение? мы можем использовать этот совет (Python): thats-not-entirely-sort">нахождение индекса элемента, ближайшего к значению в не полностью отсортированном списке, и получение индекса ближайшего значения в списке делителей, скажем, hIndex. Затем можно рассчитать другое измерение, разделив n на divisors[hIndex] или используя новый индекс wIndex = hIndex + 1 и получив divisors[wIndex].

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

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]
person Alejandro Sazo    schedule 04.06.2013