本文為原創(chuàng)，如需轉(zhuǎn)載，請注明作者和出處，謝謝！
在描述算法之前，先看看下面的5*5的表格：
| 1 |
3 |
4 |
10 |
11 |
| 2 |
5 |
9 |
12
|
19
|
| 6 |
8 |
13 |
18 |
20 |
| 7 |
14 |
17 |
21 |
24 |
| 15 |
16 |
22 |
23 |
25 |
上面的表格很容易看出規(guī)律。就是從左上角第一個格開始（起始為1），然后延右上角到左下角的斜線。先從下到上，再從上到下。開始按數(shù)字遞增排列。也就是說每一個斜線上分別有如下幾組數(shù)字：
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可以看做是從上到下），再從下到上，很象一條蛇，因此，該數(shù)字表格也可稱為蛇形矩陣。現(xiàn)在要與一個方法（或函數(shù)），方法的參數(shù)是一個int類型，表示n，方法返回一個二維數(shù)組，表示要獲得的往返接力數(shù)字表格。
實際上，這個算法并不復(fù)雜，只需要從分別獲得1至n^2中每個數(shù)字對應(yīng)的二維數(shù)組的坐標(biāo)就可以了。先拿這個5行5列的表格來說，求出上面每組數(shù)組對應(yīng)的坐標(biāo)（起始位置為0）。
第0組
第1組
第2組
第3組
第4組
第5組
第6組
第7組
第8組
|
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
|
(0,0)
(1,0) (0,1)
(0,2) (1,1) (2,0)
(3,0) (2,1) (1,2) (0,3)
(0,4) (1,3) (2,2) (3,1) (4,0)
(4,1) (3,2) (2,3) (1,4)
(2,4) (3,3) (4,2)
(4,3) (3,4)
(4,4)
|
從上面的從標(biāo)可以看出一個規(guī)律。 左上角的半個表格（以對角線分界）的橫坐標(biāo)和縱坐標(biāo)從0開始，每一組增1，直到增至表格的邊界（n - 1），而且是交替的，也就是說，偶數(shù)行是列增，行減小，行+列=組的索引。而右下角的4組數(shù)字雖然行、列也是交替增長的，但遞減的行或列總是從(n - 1)開始（對于本例，是從4開始），而遞增的行或列總是從index - n + 1開始，其中index表示組的索引。這就可以得出一個算法。實現(xiàn)代碼如下：
public static int[][] getGrid(int n)
{
int[][] array = new int[n][n];
int row = 0, col = 0, m = 1;
// 用于控制奇偶組，false表示偶組，true表示奇組
boolean isRow = false;
// i表示當(dāng)前組的索引，從0開始
for (int i = 0; i < (2 * n - 1); i++)
{
row = i;
while (row >= ((i < n) ? 0 : i - n + 1))
{
// 如果處理的是右下角表格中的數(shù)字，行或列最大不能超過n-1
if (row > (n - 1))
row = n - 1;
col = i - row;
if (isRow)
array[row][col] = m;
else // 將row變成列，將col變成行
array[col][row] = m;
m++;
row--;
}
// 切換奇偶組
isRow = !isRow;
}
return array;
}
另一種算法
上面實現(xiàn)的算法需要循環(huán)N*N次才可以生成蛇形矩陣。但仔細分析一下，還可以稍微變換一下這個算法，使循環(huán)次數(shù)減小至N*N/2。我們上學(xué)時曾學(xué)過用高斯的方法計算1+2+3+...+100， 1 + 100 = 101，2 + 99 = 101，...，50+51 = 101，因此，結(jié)果是101 * 50 = 5050。很方便。我們這個算法也可采用類似的方法。仔細觀察上面5*5的數(shù)字表格發(fā)現(xiàn)，算出左上角的矩陣中每一個數(shù)字后，都可以直接獲得右下角度某個位置的數(shù)字。例如在(0,0)位置的1，可以向到(4,4)位置的25，(1,2)位置的9可以得到(3,2)位置的17。我們發(fā)現(xiàn)，每一對數(shù)之和都為26。而且它們坐標(biāo)的關(guān)系是(row,col)，(n - row - 1, n - col - 1)。因此，只要得到左上角的半個矩陣，就可以得出右下角的另外半個矩陣。如果n為奇數(shù)，對角線中間的一個數(shù)（在5*5的矩陣中是13）與之對應(yīng)的數(shù)是其自身。好，我們看看改進的算法的實現(xiàn)：
public static int[][] getGrid1(int n)
{
int[][] array = new int[n][n];
int row = 0, col = 0, m = 1;
int number1 = (n * n / 2 + n * n % 2);
int number2 = n * n + 1;
boolean isRow = false;
// number1表示要計算的蛇形矩陣中最大的數(shù)字，對于5*5矩陣來說該數(shù)是13
for (int i = 0; m < number1; i++)
{
row = i;
while (row >= 0)
{
col = i - row;
if (isRow)
{
array[row][col] = m;
// 填充與m對應(yīng)的另外一個數(shù)
array[n - row - 1][n - col - 1] = number2 - m;
}
else
{
array[col][row] = m;
// 填充與m對應(yīng)的另外一個數(shù)
array[n - col - 1][n - row - 1] = number2 - m;
}
m++;
if(m >= number1) break;
row--;
}
isRow = !isRow;
}
return array;
}
上面的算法雖然將循環(huán)次數(shù)減少了一半，但每次循環(huán)的計算量增加了，因此，算法總體效率并沒有提高。至于使用哪個算法，可根據(jù)實際情況決定。
如果想輸出n=10的數(shù)字表格，可以使用int[][] grid = getGrid(10)或int[][] grid1 = getGrid1(10)，會得到同樣的結(jié)果。輸出grid和grid1，看看是不是下面的結(jié)果：
| 1 |
3 |
4 |
10 |
11 |
21 |
22 |
36 |
37 |
55 |
| 2 |
5 |
9 |
12 |
20 |
23 |
35 |
38 |
54 |
56 |
| 6 |
8 |
13 |
19 |
24 |
34 |
39 |
53 |
57 |
72 |
| 7 |
14 |
18 |
25 |
33 |
40 |
52 |
58 |
71 |
73 |
| 15 |
17 |
26 |
32 |
41 |
51 |
59 |
70 |
74 |
85 |
| 16 |
27 |
31 |
42 |
50 |
60 |
69 |
75 |
84 |
86 |
| 28 |
30 |
43 |
49 |
61 |
68 |
76 |
83 |
87 |
94 |
| 29 |
44 |
48 |
62 |
67 |
77 |
82 |
88 |
93 |
95 |
| 45 |
47 |
63 |
66 |
78 |
81 |
89 |
92 |
96 |
99 |
| 46 |
64 |
65 |
79 |
80 |
90 |
91 |
97 |
98 |
100 |
哪位還有更好的算法，請跟貼。可以使用任何語言實現(xiàn)。
新浪微博：http://t.sina.com.cn/androidguy 昵稱：李寧_Lining