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