How to decompose an integer in two for grid creation
Учитывая целое число N, я хочу найти два целых числа A и B, которые удовлетворяют A × B ≥ N при следующих условиях:
- Разница между A × B и N настолько мала, насколько это возможно.
- Разница между A и B настолько мала, насколько это возможно (приближается к квадрату).
Пример: 23. Возможные решения 3 × 8, 6 × 4, 5 × 5. 6 × 4 - лучшее, так как оно оставляет только одно пустое пространство в сетке и «меньше» прямоугольника, чем 3 × 8.
Другой пример: 21. Решения 3 × 7 и 4 × 6. 3 × 7 - желаемое.
Решение грубой силы это легко. Я хотел бы посмотреть, возможно ли разумное решение.
3 ответа
Легко.
В псевдокоде
a = b = floor(sqrt(N))
if (a * b >= N) return (a, b)
a += 1
if (a * b >= N) return (a, b)
return (a, b+1)
и он всегда завершается, расстояние между a и b не более 1.
Будет намного сложнее, если вы ослабите второе ограничение , но это уже другой вопрос.
Редактировать: поскольку кажется, что первое условие более важно, вы должны атаковать проблему
немного иначе. Вы должны указать какой-то метод для измерения плохости недостаточной квадратности = 2-е условие, потому что даже простые числа можно разложить на множители как 1*число, и мы выполняем первое условие. Предположим, у нас есть функция плохости (скажем, a >= b && a <= 2 * b), затем разложите на множители N и попробуйте разные комбинации, чтобы найти лучшую. Если нет достаточно хороших, попробуйте N+1 и так далее.
Edit2: немного подумав, я пришел к этому решению на Python:
from math import sqrt
def isok(a, b):
"""accept difference of five - 2nd rule"""
return a <= b + 5
def improve(a, b, N):
"""improve result:
if a == b:
(a+1)*(b-1) = a^2 - 1 < a*a
otherwise (a - 1 >= b as a is always larger)
(a+1)*(b-1) = a*b - a + b - 1 =< a*b
On each iteration new a*b will be less,
continue until we can, or 2nd condition is still met
"""
while (a+1) * (b-1) >= N and isok(a+1, b-1):
a, b = a + 1, b - 1
return (a, b)
def decomposite(N):
a = int(sqrt(N))
b = a
# N is square, result is ok
if a * b >= N:
return (a, b)
a += 1
if a * b >= N:
return improve(a, b, N)
return improve(a, b+1, N)
def test(N):
(a, b) = decomposite(N)
print "%d decomposed as %d * %d = %d" % (N, a, b, a*b)
[test(x) for x in [99, 100, 101, 20, 21, 22, 23]]
которое выводит
99 decomposed as 11 * 9 = 99
100 decomposed as 10 * 10 = 100
101 decomposed as 13 * 8 = 104
20 decomposed as 5 * 4 = 20
21 decomposed as 7 * 3 = 21
22 decomposed as 6 * 4 = 24
23 decomposed as 6 * 4 = 24
Я думаю, что это может сработать (ваши условия несколько двусмысленны). это решение чем-то похоже на другое, в основном дает прямоугольную матрицу, которая почти квадратная. вам может потребоваться доказать, что A+2 не является оптимальным условием
A0 = B0 = ceil (sqrt N)
A1 = A0+1
B1 = B0-1
if A0*B0-N > A1*B1-N: return (A1,B1)
return (A0,B0)
это решение, если первое условие является доминирующим (и второе условие не используется)
A0 = B0 = ceil (sqrt N)
if A0*B0==N: return (A0,B0)
return (N,1)
Другие варианты условий будут промежуточными