随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

生成n*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

    上面的表格很容易看出规律。就是从左上角第一个格开始（起始为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表示组的索引。这就可以得出一个算法。实现代码如下：
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*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）与之对应的数是其自身。好，我们看看改进的算法的实现：

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表示要计算的蛇形矩阵中最大的数字，对于5*5矩阵来说该数是13
    for (int i = 0; m < number1; i++)
    {
        row = i;
        while (row >= 0)
        {
            col = i - row;
            if (isRow)
            {
                array[row][col] = m;
                //  填充与m对应的另外一个数
                array[n - row - 1][n - col - 1] = number2 - m;
            }
            else
            {
                array[col][row] = m;
                //  填充与m对应的另外一个数
                array[n - col - 1][n - row - 1] = number2 - m;

            }
            m++;
            if(m >= number1) break;
            row--;
        }
        isRow = !isRow;
    }
    return array;
}
   
   上面的算法虽然将循环次数减少了一半，但每次循环的计算量增加了，因此，算法总体效率并没有提高。至于使用哪个算法，可根据实际情况决定。
   如果想输出n=10的数字表格，可以使用int[][] grid = getGrid(10)或int[][] grid1 = getGrid1(10)，会得到同样的结果。输出grid和grid1，看看是不是下面的结果：

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

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

 





《Android开发完全讲义（第2版）》（本书版权已输出到台湾）

http://product.dangdang.com/product.aspx?product_id=22741502



《Android高薪之路：Android程序员面试宝典 》http://book.360buy.com/10970314.html


新浪微博：http://t.sina.com.cn/androidguy   昵称：李宁_Lining

posted on 2009-07-24 11:04 银河使者 阅读(8674) 评论(7)  编辑  收藏 所属分类: java 、algorithm 、 原创

评论

# re: 获得N^2个往返接力数字表格的算法  回复  更多评论   

acm中的蛇形矩阵
2009-07-24 21:05 | 飞翔天使

# re: 生成蛇形矩阵的算法  回复  更多评论    

public class Hello {
 
     public static void main(String[] args) {
         final int N = 6;
         for(int i = 0; i < N; i++) {
             for(int j = 0, m = 0; j < N; j++) {
                 if(j >= i) {
                     boolean b = j % 2 == 0;
                     m = (b ? (j + 1) * (j + 1) : j * j + 1) + (b ? -i : i);
                 } else {
                     boolean b = i % 2 == 0;
                     m = (b ? i * i + 1 : (i + 1) * (i + 1)) + (b ? j : -j);
                 }
                 System.out.printf("%2d ", m);
             }
             System.out.println();
         }
    }
}
2009-07-25 01:30 | 菜菜宝宝

# re: 生成蛇形矩阵的算法  回复  更多评论    

 1  2  9 10 25 26
 4  3  8 11 24 27
 5  6  7 12 23 28
16 15 14 13 22 29
17 18 19 20 21 30
36 35 34 33 32 31
哎，不好意思，看错题了，生成这样子的了。
2009-07-25 01:35 | 菜菜宝宝

# re: 生成n*n蛇形矩阵的改进算法[未登录]  回复  更多评论   

这个问题需要填充N*N个数，所以必须有N*N次操作，从这一层看来，没有改进的余地。你改进的算法只是减少了循环次数，却在每次循环中加倍了操作，还增加了很多判断，我以为，这样速度反而会慢呢。
2009-07-26 10:51 | lanxiazhi

# re: 生成n*n蛇形矩阵的改进算法  回复  更多评论   

@lanxiazhi
测了一个，这两个算法的效率差不多。不过改进后的算法看起来更好点，至少在while后面没那么多计算了，哈。
2009-07-26 11:39 | 银河使者

# re: 生成n*n蛇形矩阵的算法  回复  更多评论   

void shetian(int n)
{ int a[50][50],i,j,k,t;
k=0;
t=1;
while (k<=n*2)
{
for(i=k;i>=0;i--)
for(j=0;j<=k;j++)
if((i+j==k)&&(i<=n-1)&&(j<=n-1))
if(k%2==0) a[j][i]=t++;
else a[i][j]=t++; k++;
}
for(i=0;i<=n-1;i++)
{ for(j=0;j<=n-1;j++)
printf("%d ",a[i][j]);
printf("\n");}
}
初学不知道行不？
2009-08-11 16:51 | 彪子

# re: 生成n*n蛇形矩阵的算法  回复  更多评论   

public class test {
public static void main(String[] args) {
int[][] array = new int[10][10];
for (int row = 0; row < 10; row++) {
for (int col = 0; col < 10; col++) {
if ((col + row) < 10) {
if ( ( col + row + 1 ) % 2 == 1 ) {
array[row][col] = (1+( col + row + 1 ))/2*( col + row + 1 )-col;
array[9-row][9-col] = 101-array[row][col];
} else {

array[row][col] = (1+( col + row ))/2*( col + row )+col+1;
array[9-row][9-col] = 101-array[row][col];
}
}
}
System.out.println();
}

for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
System.out.print(array[i][j]+"\t");
}
System.out.println();
}
}
}
2009-08-12 22:32 | tonny

只有注册用户登录后才能发表评论。
网站导航: