生成n*n蛇形矩阵的算法

本文为原创，如需转载，请注明作者和出处，谢谢！

在描述算法之前，先看看下面的5*5的表格：

     上面的表格很容易看出规律。就是从左上角第一个格开始（起始为1），然后延右上角到左下角的斜线。先从下到上，再从上到下。开始按数字递增排列。也就是说每一个斜线上分别有如下几组数字：

1    2 3     4 5 6       7 8 9 10      11 12 13 14 15          16 17 18 19      20 21 22      23 24       25

    由于是先从上到下（1可以看做是从上到下），再从下到上，很象一条蛇，因此，该数字表格也可称为蛇形矩阵。现在要与一个方法（或函数），方法的参数是一个int类型，表示n，方法返回一个二维数组，表示要获得的往返接力数字表格。

    实际上，这个算法并不复杂，只需要从分别获得1至n^2中每个数字对应的二维数组的坐标就可以了。先拿这个5行5列的表格来说，求出上面每组数组对应的坐标（起始位置为0）。

    从上面的从标可以看出一个规律。  左上角的半个表格（以对角线分界）的横坐标和纵坐标从0开始，每一组增1，直到增至表格的边界（n - 1），而且是交替的，也就是说，偶数行是列增，行减小，行+列=组的索引。而右下角的4组数字虽然行、列也是交替增长的，但递减的行或列总是从(n - 1)开始（对于本例，是从4开始），而递增的行或列总是从index - n + 1开始，其中index表示组的索引。这就可以得出一个算法。实现代码如下：

   另外一种算法

   上面实现的算法需要循环N*N次才可以生成蛇形矩阵。但仔细分析一下，还可以变换一种方法来完成这个算法，使循环次数减小至N*N/2。我 们上学时曾学过用高斯的方法计算1+2+3+...+100，   1 + 100 = 101，2 + 99 = 101，...，50+51 = 101，因此，结果是101 * 50 = 5050。很方便。我们这个算法也可采用类似的方法。仔细观察上面5*5的数字表格发现，算出左上角的矩阵中每一个数字后，都可以直接获得右下角度某个位 置的数字。例如在(0,0)位置的1，可以得到(4,4)位置的25，(1,2)位置的9可以得到(3,2)位置的17。我们发现，每一对数之和都为 26。而且它们坐标的关系是(row,col)，(n - row - 1, n - col - 1)。因此，只要得到左上角的半个矩阵，就可以得出右下角的另外半个矩阵。如果n为奇数，对角线中间的一个数（在5*5的矩阵中是13）与之对应的数是其 自身。好，我们看看改进的算法的实现：

   虽然上面的算法将循环次数减小一倍，但运输量增加，因此，在效率上与第一种长法相当，读者可以选用其中任何一种算法。

   如果想输出n=10的数字表格，可以使用int[][] grid = getGrid(10)或int[][] grid1 = getGrid1(10)，会得到同样的结果。输出grid和grid1，看看是不是下面的结果：

哪位还有更好的算法，请跟贴。可以使用任何语言实现。