2011-06-06 118 views
4

我要計算在rectangles.It矩形的數目可以使用式如何計算矩形網格中的矩形數量?

(X^2 + X)(Y^2 + Y)/ 4

但它也包括完全平方等來進行1 * 1,2 * 2,3 * 3等。我不想在我的計算中包括那個。我該怎麼做?

回答

5

好吧,你有整數矩形數點(0, 0)(x, 0)(x, y)(0, y)xy爲整數之間也座標。你現在需要從這個總和中刪除完美的正方形。

要計算它,我們來計算方塊的數量1*1:其中明顯有x*y。對於正方形2*2,由於此正方形的寬度,我們有x-1選項用於x座標,而y-1用於這種正方形左下角的y座標:這導致(x-1)*(y-1)正方形。同上,我們將有(x-2)*(y-2)廣場3*3

因此,對於一個給定的i,我們有(x - i + 1) * (y - i + 1)廣場i*i,並i1進行最小的xy(當然如果x是4和y是7 ,我們不能有一個大於4的邊的正方形)。

所以,如果m = min(x, y),我們有:

Sum_Squares = Sum(i = 1, i = m, (x - i + 1) * (y - i + 1)) 
      = Sum(j = 0, j = m - 1, (x - i) * (y - i)) 
      = Sum(j = 0, j = m - 1, x*y - (x+y)*j + j^2) 
      = m*x*y - (x+y)*Sum(j = 0, j = m - 1, j) + Sum(j = 0, j = m - 1, j^2) 
      = m*x*y - (x+y)*Sum(j = 1, j = m - 1, j) + Sum(j = 1, j = m - 1, j^2) 
      = m*x*y - (x+y)*m*(m-1)/2 + (m-1)*m*(2*m-1)/6 

我得到與指數的變化(j = i - 1),並通過著名的公式:

Sum(i = 1, i = n, j) = n*(n + 1)/2 
Sum(i = 1, i = n, j^2) = n*(n + 1)*(2*n + 1)/6 

你只需要刪除此Sum_Squares(x^2+x)(y^2+y)/4,你就完成了!