本文为原创,如需转载,请注明作者和出处,谢谢! 在描述算法之前,先看看下面的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 |
上面的表格很容易看出规律。就是从左上角第一个格开始(起始为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组
第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)
|
从上面的从标可以看出一个规律。 左上角的半个表格(以对角线分界)的横坐标和纵坐标从0开始,每一组增1,直到增至表格的边界(n - 1),而且是交替的,也就是说,偶数行是列增,行减小,行+列=组的索引。而右下角的4组数字虽然行、列也是交替增长的,但递减的行或列总是从(n - 1)开始(对于本例,是从4开始),而递增的行或列总是从index - n + 1开始,其中index表示组的索引。这就可以得出一个算法。实现代码(Java版)如下:
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表示当前组的索引,从0开始
for (int i = 0; i < (2 * n - 1); i++)
{
row = i;
while (row >= ((i < n) ? 0 : i - n + 1))
{
// 如果处理的是右下角表格中的数字,行或列最大不能超过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;
}
如果想输出n=10的数字表格,可以使用int[][] grid = getGrid(10);,输出这个grid,看看是不是下面的结果:
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 |
哪位还有更好的算法,请跟贴。可以使用任何语言实现。
本文转自银河使者博客园博客,原文链接http://www.cnblogs.com/nokiaguy/archive/2009/07/24/1530139.html如需转载请自行联系原作者
银河使者