生成n*n蛇形矩阵的算法 - 编程入门网

另一种算法

上面实现的算法需要循环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; }

上面的算法虽然将循环次数减少了一半，但每次循环的计算量增加了，因此，算法总体效率并没有提高。

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!