如何将整数分解为两个整数以创建网格

容易的。

伪码

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

我认为这可能有效(你的情况有些模棱两可)。这个解与另一个解有点相似,在基本上产生了近似正方形的矩形矩阵。 你可能需要证明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)

其他条件的变化将介于

A = B = ceil (sqrt N)