矩形網格中矩形網格的最小數量[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我剛剛更新了答案。 –

回答