矩形网格中矩形网格的最小数量[JAVA]

我一直在研究需要将矩形网格（M * N）分割成最小数量的正方形网格的问题，并让我给出一个想法一个例子..矩形网格中矩形网格的最小数量[JAVA]

让我们考虑8 * 5网格。我们可以取出的第一个最大元素是5 * 5它将在3 * 5之后被忽略，我们可以取出的最大矩形是3 * 3后来它是2 * 3，我们可以将其分割为2 1 * 1我需要的网格用更少的时间复杂度为上述算法更好的算法需要更多的时间....感谢问候..

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

2016-06-07 SmashCode

很酷。感谢分享。 –

这种方法和逻辑对我来说听起来确实...要找到最少的数字，您将必须从最小尺寸开始，并重复剩余尺寸。你在这里期待什么？ – NoobEditor

我需要循环优化。我遇到的实际问题是我得到2个数组1和m，1个n我需要使用4个循环有没有什么方法可以进行循环优化来提高我的性能，并且有助于伪代码或代码，我们感谢 – SmashCode

这个问题就相当于找到两个数字的GCD（最大公约数）。

这是我们视觉的一个例子，如何找到对GCD（200x117）

所以，我们所能做的就是采用了经典的Euclid algorithm：

如果我们有一个矩形大小(a,b) and 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） - > return，

2016-06-07 06:14:47

有可能是一个情况，其中b是一个权力，那么我们可以将那个网格分成那些我们没有达到的网格的n个权力（1,1）如果我错了，请纠正我。谢谢你的时间 – SmashCode

我得到了一个案例，其中a = 5和b = 4给定约束的任何可能的解释.. – SmashCode

@SmashCode我刚刚更新了答案。 –

回答