- 问题
- 解析
- 代码(第一种)
- 优化(第二种)
如下图所示,小明用从1 开始的正整数“蛇形”填充无限大的矩阵。
容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20 行第20 列的数是多少?
解析2020年第十一届蓝桥杯省赛真题——蛇形填数
第一种
直接按照题目思路,开一个大的数组,然后按照题目逻辑去数到n,参照代码方式
第二种
为了方便理解,我们来转化下矩阵形状如下
假设行号为k,行列相同的行列我们假设为n,第n行n列的数值为ans
通过观察我们可以看出以下规律
- 第n行第n列的数据是隔一行出现一次,和行号k=2n-1
- 每行的数字数是和行号k相同的,即第一行一个数,第二号两个数…
- 每行的最大值和行号k呈等差数列求和的关系,例如1=1,3=1+2,6=1+2+3… max=1+2+...+k,由等差数列求和公式Sn=n*a1+n(n-1)d/2,所以,max=k(k+1)/2。
- 第n行第n列的值为前一行最大值加n,所以ans=(k-1)(k-1+1)/2+n,ans=2n(n-1)+1。
额,这样分析完好像不用代码了,算了写在优化吧。
代码(第一种)public static void main(String[] args) {
int[][] matrix = new int[100][100];
int cnt = 0,n=20;
matrix[1][1] = ++cnt;
int col = 1, row = 1; //col代表列坐标,row代表行坐标
while(matrix[n][n] == 0) {
matrix[row][++col] = ++cnt; //向右
while(col > 1) { //右上到左下
matrix[++row][--col] = ++cnt;
}
matrix[++row][col] = ++cnt; //向下
while(row > 1) { //左下到右上
matrix[--row][++col] = ++cnt;
}
}
System.out.println(matrix[n][n]);
}
优化(第二种)
public static void main(String[] args) {
int n=20,ans;
ans=2*n*(n-1)+1;
System.out.println(ans);//761
}



