覆盖大小为 n x m 的矩形网格所需的最小正方形数

Question

问题陈述是找到最小的正方形数量其边是 2 的幂 需要覆盖一个大小为 n 乘以 m 的矩形网格。

我写了下面的代码：

ll solve(ll n,ll m)
{
    if(n==0||m==0)
        return 0;
    else if(n%2==0&&m%2==0)
        return solve(n/2,m/2); 
    else if(n%2==0&&m%2==1)
        return (solve(n/ 2,m/ 2));
    else if(n%2==1&&m%2==0)
        return (solve(n/ 2,m/ 2)); 
    else
        return (n+m-1+solve(n/2,m/2)); 
}

建议我，因为它给出了错误的答案。

Answer 1

W.l.o.g。我们说 n>=m 并选择 m 的形式为 2^x。（如果 m 是任意的 <= n 也仅意味着我们将相同的方法应用于大小为 n 倍 m-2^x 的第二个矩形，其中 x=int_floor(ld(m)) 和ld 当然是以 2 为底的日志。）

以下代码段应计算所需的方块数。

countSquares(m,n,x) :
  if n == 0 : return 0
  if n == 1 : return m
  if n/2^x >= 1 : 
    return m/2^x + countSquares(m,n-2^x,x-1)
  else
    countSquares(m,n,x-1)

第三个中的return如果：m/2^x总是一个自然数，因为m的开头形式是2^x，任何2^(x-(x-i)) 仍然是自然数。

如果我们只对下限感兴趣。我会假设选择一个大小为 a 乘以 b 的矩形，其中 a:=2^x - 1 和 b:=2^y -1 应该导致大约 ld(a) 乘以 ld(b) 的方块数。

将代码片段扩展到任意 m 似乎涉及第二次递归：

partitionAndCount(n,m) :
  if n < m : swap(n,m)

  var x = floor(ld(m))
  var mRes = m - 2^x

  if mRes == 0 : return countSquares(2^x,n,x-1)
  if mRes == 1 : n + return countSquares(2^x,n,x-1)
  return partitionAndCount(n,mRes) + countSquares(2^x,n,x-1)

覆盖大小为 n x m 的矩形网格所需的最小正方形数

Minimum number of squares required to cover a rectangular grid of size n by m

algorithm

recursion

geometry

computational-geometry