A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 乔兵 高级黑马   /  2013-10-9 07:27  /  2729 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 乔兵 于 2013-10-9 07:28 编辑

在描述算法之前,先看看下面的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表示组的索引。这就可以得出一个算法。实现代码如下:
  1. public static int[][] getGrid(int n)
  2. {
  3.     int[][] array = new int[n][n];
  4.     int row = 0, col = 0, m = 1;
  5.     //  用于控制奇偶组,false表示偶组,true表示奇组
  6.     boolean isRow = false;
  7.     //  i表示当前组的索引,从0开始
  8.     for (int i = 0; i < (2 * n - 1); i++)
  9.     {
  10.         row = i;
  11.         while (row >= ((i < n) ? 0 : i - n + 1))
  12.         {
  13.             //  如果处理的是右下角表格中的数字,行或列最大不能超过n-1
  14.             if (row > (n - 1))
  15.                 row = n - 1;
  16.             col = i - row;
  17.             if (isRow)
  18.                 array[row][col] = m;
  19.             else  //  将row变成列,将col变成行
  20.                 array[col][row] = m;
  21.             m++;
  22.             row--;
  23.         }
  24.         //  切换奇偶组
  25.         isRow = !isRow;
  26.     }
  27.     return array;
  28. }
复制代码
另一种算法

   上面实现的算法需要循环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)与之对应的数是其自身。好,我们看看改进的算法的实现:
  1. public static int[][] getGrid1(int n)
  2. {
  3.     int[][] array = new int[n][n];
  4.     int row = 0, col = 0, m = 1;
  5.     int number1 =  (n * n / 2 + n * n % 2);
  6.     int number2 = n * n + 1;        
  7.     boolean isRow = false;
  8.     //  number1表示要计算的蛇形矩阵中最大的数字,对于5*5矩阵来说该数是13
  9.     for (int i = 0; m < number1; i++)
  10.     {
  11.         row = i;
  12.         while (row >= 0)
  13.         {
  14.             col = i - row;
  15.             if (isRow)
  16.             {
  17.                 array[row][col] = m;
  18.                 //  填充与m对应的另外一个数
  19.                 array[n - row - 1][n - col - 1] = number2 - m;
  20.             }
  21.             else
  22.             {
  23.                 array[col][row] = m;
  24.                 //  填充与m对应的另外一个数
  25.                 array[n - col - 1][n - row - 1] = number2 - m;

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

            
13410112122363755
25912202335385456
681319243439535772
7141825334052587173
15172632415159707485
16273142506069758486
28304349616876838794
29444862677782889395
45476366788189929699
466465798090919798100

(转自blogjava)

1 个回复

倒序浏览
楼主,这个是入学测试吗
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马