Go语言视频零基础入门到精通

javalearner

在描述算法之前，先看看下面的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
   
  

   

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/4/000143000.zip