java - 矩形网格中正方形网格的最小数量[JAVA]

Question

我一直在研究需要将矩形网格 (M*N) 拆分为最小数量的正方形网格的问题，让我通过一个示例给出我的想法。

让我们考虑 8*5 网格。我们可以取出的第一个最大元素是 5*5，稍后我们可以取出 3*5 的最大矩形是 3*3，之后它是 2*3，我们可以将其拆分为我需要的 2 1*1 网格一个更好的算法，时间复杂度更低，因为上面提到的算法需要更多的时间....谢谢你..

这是给定问题陈述的视觉效果..

Answer 1

这道题相当于求两个数的GCD(最大公约数)。

这就是我们如何通过可视化示例来找到对 (200x117) 的 GCD

所以，我们能做的就是使用经典的Euclid algorithm :

如果我们有一个矩形大小 (a,b) 和 a >= b -> 创建 a/b 正方形大小 (b, b) 并解决矩形大小 (b, a % b) 的子问题并继续直到我们到达 (x, 0)

伪代码

void gcd(int a, int b){
     if(b == 0)
        return;
     print a/b squares with size b x b;
     gcd(b, a % b);
}

时间复杂度应该是O(log max(a,b))

所以，对于情况 (5,4) ，首先，我们创建一个正方形 (4,4) -> 如果 (4,1) 还剩什么 -> 创建 4 个正方形大小 (1,1) -> (1, 0) -> 返回;