有這樣一道智力題，4*4的方塊（見圖）中包含有多少個(gè)子方塊，
-
這個(gè)道題簡單，但比較繁瑣。如果細(xì)心的話會(huì)得出這樣的結(jié)果：
1*1：16個(gè)
2*2：9個(gè)
3*3：4個(gè)
4*4：1個(gè)
總共：30個(gè)
如果將問題泛化，問N*M的矩陣包含多少個(gè)子矩陣。這個(gè)結(jié)果就不像上題那么直觀，能數(shù)出來。這樣數(shù)也不符合編程的思維方式。其實(shí)這類問題類似于遍歷問題，即遍歷某個(gè)集合的每個(gè)元素，然后進(jìn)行操作。這個(gè)問題是遍歷所有的矩陣，執(zhí)行累加操作。這類問題需要考慮兩個(gè)方面：迭代項(xiàng)和迭代范圍。
-
迭代項(xiàng)：一般為元素的鍵值，它用來區(qū)分元素。它包含一個(gè)或多個(gè)元素的屬性。這個(gè)問題中可以找出“高”、“寬”和“位置”作為鍵值。“高”和“寬”記為“h”和“w”。“位置”可以轉(zhuǎn)換為左上角方塊的位置，有兩個(gè)坐標(biāo)記為“x”和“y”。這樣<h,w,x,y>就代表一個(gè)矩陣。問題則對這四個(gè)量迭代。
-
迭代范圍：可以通過確定鍵值的取值范圍和接受函數(shù)來確定。接受函數(shù)指判斷鍵值是否合法的函數(shù)。在這個(gè)問題中，“h”和“w”的取值范圍是[1,N]和[1,M]。由于矩陣的左上角方塊的位置加高加寬，不能超出N*M這個(gè)大矩陣，因此“x”和“y”的取值范圍是[0,N-h]和[0,M-w]（坐標(biāo)從0開始）。當(dāng)然“x”和“y”的取值范圍也可以是[1,N]和[1,M]。然后在接受函數(shù)中排除不合法的值。
當(dāng)有了迭代項(xiàng)和迭代范圍，則可以編寫循環(huán)遍歷每一個(gè)元素，然后累加。這問題的結(jié)果為M*N(M+1)*(N+1)/4。