直接输出蛇形矩阵

从风雨潇潇的博客中看到了这样一个题目,原文链接:http://ayeye.blog.sohu.com/300658293.html

题目很简单,输出类似下面的东西,要求是不用数组、向量等数据结构:

直接输出蛇形矩阵
这个题目以前见过,我一直觉得最简单的方法就是用公式,可以直接求出第 (n, m) 个位置的数。(为什么需要数组呢,数组无非就是临时保存计算结果吧。)简单说一下我的思路。
这个题目其实可以在坐标系的第一象限中首先画一个边长为N的正方形(N就是你的矩阵的行数)。然后画两条直线,一条是 y=x,一条是 x+y=N 。这两条线把正方形就分成了4个区域(4个等腰直角三角形)。这4个区域内的数值的方向是固定的,假如分别把这4个区域叫做上、下、左、右,那么:
上三角形中的数都是从左到右递增的;
右三角形中的数都是从上到下递增的;
下三角形中的数都是从右到左递增的;
左三角形中的数都是从下到上递增的。
这4个三角形的区域可以用一对不等式来表示,比如上三角形可以表示为:

x<=y
x+y>=N

那么这样理解就简单了。(这样说可能稍微有点不直观,朋友请你直接在纸上画一画,就一目了然了,非常的简单。)
可以首先计算出每个拐角(右上、右下、左下、左上)的值,例如左上拐角(其实就是x+y=N这条直线在y=x左侧的部分):

f(n,m) = 4 * m * (N - m)

这里m=n。
其他几个拐角的计算公式分别为:

直接输出蛇形矩阵
f(n,m) = 2 * n * (2 * m + 1) + N
f(n,m) = (2 * n + 1) * (2 * N - 2 * n - 1)
f(n,m) = 2 * (2 * n + 1) * (m + 1) - N
直接输出蛇形矩阵

有了这几个拐角的值,想要知道任何一个区域中的任何一个位置的值也就可以计算了,而且计算的方式有很多种,例如计算上三角形区域中的数,可以以左上拐角为基准(增加对应的偏移,也就是m-n+1),也可以以右上拐角作为基准,两种方式是等价的。那么程序就可以这样写(python的):

直接输出蛇形矩阵
def f(n, m):
    if   m >= n and m + n < N: # top
        v = 4 * n * (N-n) + m - n + 1
    elif m <= n and m + n < N: # left
        v = 4 * (m+1) * (N-m-1) + m - n + 1
    elif m <= n and m + n >= N: # down
        v = (2 * N - 2 * n - 1) * (2 * n + 1) + n - m 
    elif m >= n and m + n >= N: # right
        v = (N-1-m) * (4 * m + 1) + N + n 
    else:
        raise Exception("Unknown area: {},{}".format(n,m))
    return v
for n in range(0, N):
    for m in range(0, N):
        print("{0:3d}".format(f(n, m)), end= )
    print()
直接输出蛇形矩阵

输出类似这样(用N=8做实验):

直接输出蛇形矩阵

希望我没有老眼昏花把东西写错了(-:

直接输出蛇形矩阵

上一篇:CRM 2011 Plugin 知识的总结加代码解释


下一篇:表的多条记录合并成一条记录