【蓝桥杯】历届真题 杨辉三角形 (省赛)Java

这篇具有很好参考价值的文章主要介绍了【蓝桥杯】历届真题 杨辉三角形 (省赛)Java。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【问题描述】

        下面的图形是著名的杨辉三角形:

【蓝桥杯】历届真题 杨辉三角形 (省赛)Java

如果我们按从上到下、从左到右的顺序把所有数排成一列,可以得到如下数列:

        1,1,1,1,2,1,1,3,3,1,1,4,6,4,1,...

        给定一个正整数N,请你输出数列中第一次出现Ⅳ是在第几个数?

【输入格式】

        输入一个整数N。

【输出格式】

        输出一个整数代表答案。

【样例输入】

        6

【样例输出】

        13

 【蓝桥杯】历届真题 杨辉三角形 (省赛)Java

 【思路与分析

        首先,要新建一个数组以存放杨辉三角中的值。该长度通过题目中所给出的图示进行计算,此时有一个小窍门。通过观察可知杨辉三角左右半边的值为相同的,或者说杨辉三角是中心对称的。因此,可以先从中间一分为二,选取左半边或右半边进行计算。

【蓝桥杯】历届真题 杨辉三角形 (省赛)Java

        经过观察,不难总结出规律:y = x * (x-1) / 2

        后续计算同样基于该规律所做。

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        long N= sc.nextLong();
        //经过计算在第44721行的时候,第三列的值将会超过十亿
        //所以我们创建44725长度的数组
        long[] a=new long[44725]; 
        a[0]=1L;	//将数组0位置存入一个长整形
        if(N==1) { //当N==1,直接输出1
        	System.out.println(1);
					return;
        }
        //声明一个标志位
        int count=1;

        for(int i=1;i<44725;i++) {
        	for(int j=i;j>=1;j--) {
        		//按照杨辉三角的数字规律填充数组
        		a[j]=a[j]+a[j-1];
                //找到了N,则输出当前位置,位置 的计算等于 前面的个数 + 当行的位置数 
        		if(a[j]==N) {  
        			//前面的个数 = (count+1)*count/2  ,当行的个数 = i-j+1
        			System.out.println((count+1)*count/2+i-j+1);
        			return;
        		}
        	}
            //判断完后,标志位++
        	count++;
        }
        //这是未找到的情况,就是说有些小于10亿的数在44721行之前都还没有出现 ,
        //那么它必然是出现在未显示出来的第二列的位置上
        System.out.println((N+1)*N/2+2); 
        //所以 位置 = 前面出现的个数 + 2
    }
}

Q&A

        为什么在for循环中不使用 break 而使用return?

        答:return在for循环中的作用为:返回return所返回的值,并不会执行下一次循环。因不能干扰count标志位的运算,因此 使用return代替break。若使用break,在OJ测试时将只有60分,无法拿到满分。

        为什么在存入数组元素时使用 1L 而不是 1?

        答:L表示long ,long占用8个字节,表示范围:-9223372036854775808 ~ 9223372036854775807 
1L其实就是1

后面跟L一般是指数据类型,1L表示1是长整型,如果是1f 表示是float型,若是1 则表示 int 型。文章来源地址https://www.toymoban.com/news/detail-434506.html

到了这里,关于【蓝桥杯】历届真题 杨辉三角形 (省赛)Java的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数字三角形+包子凑数(蓝桥杯JAVA解法)

    题目描述 上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和(路径上的每一步只可沿左斜线向下或右斜线向下走)。 输入描述 输入的第一行包含一个整数 N (1≤N≤

    2024年02月01日
    浏览(37)
  • 蓝桥杯官网填空题(三角形的面积)

    题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 已知三角形三个顶点在直角坐标系下的坐标分别为: ```txt (2.3, 2.5) (6.4, 3.1) (5.1, 7.2) ```txt 求该三角形的面积。 注意,要提交的是一个小数形式表示的浮点数。 要求精确到小数后 3 位

    2024年02月09日
    浏览(49)
  • 蓝桥 卷“兔”来袭编程竞赛专场-03破解三角形密码 题解

    挑战介绍 三角形密码指的是将一串字符串按照正直角三角形的形状排列,传递的信息隐藏在每一行的最后一个字符,然后将所有的行的最后一个字符依次连接,就是需要传递的信息。 例如加密后的字符串是:我们爱的是蓝色的心桥 将加密字符串按照正直角三角形填充后如下

    2023年04月16日
    浏览(36)
  • java打印各种三角形~(**版)

    文章目录 1、正等腰三角形 2、倒等腰三角形 3、菱形 4、左下直角三角形 5、右下直角三角形 6、左上直角三角形 7、右上直角三角形 8、数字版三角形  

    2024年02月07日
    浏览(46)
  • C/C++字符三角形 2020年12月电子学会青少年软件编程(C/C++)等级考试一级真题答案解析

    目录 C/C++字符三角形 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 2020年12月 C/C++编程等级考试一级编程题 给定一个字符,用它构造一个底边长5个字符,高3个字符的等腰字符三角形。 输入描述: 输入只有一行

    2024年02月08日
    浏览(65)
  • Java用for循环打印三角形菱形

    目录   一、打印矩形  二、打印直角三角形 1.直角三角形  2.打印九九乘法表  三、打印等腰三角形  四、打印平行四边形  五、打印菱形  六、打印两个直角三角形 1.打印两个直角三角形  2.打印倒着的两个直角三角形 七、打印“蝴蝶”   一、打印矩形 运行结果:  二、

    2024年04月25日
    浏览(37)
  • 力扣120. 三角形最小路径和(Java 动态规划)

    Problem: 120. 三角形最小路径和 Problem:64. 最小路径和 本题目可以看作是在上述题目的基础上改编而来,具体的思路: 1.记录一个int类型的大小的 n 乘 n n乘n n 乘 n 的数组(其中 n n n 为数组triangle的行数)用于记录 每一个当前阶段的最小路径和 2.大体上可以依据题意得出动态转移

    2024年01月22日
    浏览(41)
  • 【Java版oj】day27不用加减乘除做加法、三角形

    目录  一、不用加减乘除做加法 (1)原题再现 (2)问题分析 (3)完整代码  二、三角形 (1)原题再现 (2)问题分析 (3)完整代码 不用加减乘除做加法__牛客网 写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。 输入 1,2 输出 3 输入 0,0

    2023年04月16日
    浏览(59)
  • css实现圆角三角形,圆角三角形的实现

    今天给大家带来一个如何实现圆角三角形的方案,这个方案虽然可以实现,但是也是借助拼凑等方式来实现的,假如想一个div来实现圆角三角形,还是比较困难的。之前文章讲了如何实现对话框,里面介绍了三角形的实现方式。今天讲讲如何实现圆角三角形。 想要生成一个带

    2024年02月09日
    浏览(50)
  • 用python写九九乘法表(左上三角、左下三角、右上三角、右下三角、正三角形、倒三角形格式)

    1.左上三角格式:   2.左下三角格式:   3.右上三角格式:     4.右下角格式:     5.倒三角格式:      

    2024年02月11日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包