有这样一道智力题,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。