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

【问题描述】

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

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

        1,1112,113,311,46,41...

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

【输入格式】

        输入一个整数N。

【输出格式】

        输出一个整数代表答案。

【样例输入】

        6

【样例输出】

        13

 

 【思路与分析】

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

        经过观察不难总结出规律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 型。