Как разложить целое число на два для создания сетки

Question

Учитывая целое число NI, я хочу найти два целых числа A и B, которые удовлетворяют A × B ≥ N при следующих условиях:

1. Разница между A × B и N настолько мала, насколько это возможно.
2. Разница между А и В минимально возможна (приближается к квадрату).

Пример: 23. Возможные решения 3 × 8, 6 × 4, 5 × 56 × 4 является лучшим, поскольку он оставляет только одно пустое пространство в сетке и «менее» прямоугольный, чем 3 × 8.

Другой пример: 21. Решения 3 × 7 и 4 × 6. 3 ×7 является желаемым.

Решение грубой силы легко.Я хотел бы посмотреть, возможно ли разумное решение.

Answer 1

Легко.

В псевдокоде

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. 1. 1008 *

Этобудет намного сложнее, если вы ослабите второе ограничение, но это другой вопрос.

Редактировать: так как кажется, что первое условие более важно, вы должны атаковать проблему немного по-другому.Вы должны указать какой-либо метод для измерения плохости недостаточности квадрата = 2-го условия, потому что даже простые числа могут быть разложены как 1*number, и мы выполняем первое условие.Предположим, у нас есть функция плохости (скажем, 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

Answer 2

Я думаю, это может сработать (ваши условия несколько двусмысленны).это решение чем-то похоже на другое, в основном получается прямоугольная матрица, которая почти квадратная.Вам может потребоваться доказать, что 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)

Другие изменения условийбудет между

Answer 3

A = B = ceil (sqrt N)