栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【蓝桥杯】蛇形填数 - Java版解析

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【蓝桥杯】蛇形填数 - Java版解析

文章目录
  • 问题
  • 解析
  • 代码(第一种)
  • 优化(第二种)

问题

如下图所示,小明用从1 开始的正整数“蛇形”填充无限大的矩阵。

容易看出矩阵第二行第二列中的数是5。请你计算矩阵中第20 行第20 列的数是多少?

2020年第十一届蓝桥杯省赛真题——蛇形填数

解析

第一种
直接按照题目思路,开一个大的数组,然后按照题目逻辑去数到n,参照代码方式

第二种
为了方便理解,我们来转化下矩阵形状如下

假设行号为k,行列相同的行列我们假设为n,第n行n列的数值为ans

通过观察我们可以看出以下规律

  1. 第n行第n列的数据是隔一行出现一次,和行号k=2n-1
  2. 每行的数字数是和行号k相同的,即第一行一个数,第二号两个数…
  3. 每行的最大值和行号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。
  4. 第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
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/977924.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号