如何分解两个整数以进行网格创建

Question

给定整数NI想要找到满足A×B≥N的两个整数A和B,条件如下:

1. A×B和N之间的差异尽可能低.
2. A和B之间的差异尽可能低(接近正方形).

示例:23.可能的解决方案3×8,6×4,5×5.6×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*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