随笔 - 51, 文章 - 1, 评论 - 41, 引用 - 0
数据加载中……

数方块

      有这样一道智力题,4*4的方块(见图)中包含有多少个子方块,

这个道题简单,但比较繁琐。如果细心的话会得出这样的结果:

1*116

2*29

3*34

4*41

总共:30



      如果将问题泛化,问N*M的矩阵包含多少个子矩阵。这个结果就不像上题那么直观,能数出来。这样数也不符合编程的思维方式。其实这类问题类似于遍历问题,即遍历某个集合的每个元素,然后进行操作。这个问题是遍历所有的矩阵,执行累加操作。这类问题需要考虑两个方面:迭代项和迭代范围。

  1. 迭代项:一般为元素的键值,它用来区分元素。它包含一个或多个元素的属性。这个问题中可以找出“高”、“宽”和“位置”作为键值。“高”和“宽”记为“h”和“w”。“位置”可以转换为左上角方块的位置,有两个坐标记为“x”和“y”。这样<h,w,x,y>就代表一个矩阵。问题则对这四个量迭代。

  2. 迭代范围:可以通过确定键值的取值范围和接受函数来确定。接受函数指判断键值是否合法的函数。在这个问题中,“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。









posted on 2011-01-04 22:45 lemene 阅读(435) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理