【問題描述】

????????下面的圖形是著名的楊輝三角形:

如果我們按從上到下、從左到右的順序把所有數(shù)排成一列，可以得到如下數(shù)列:

????????1,1，1，1，2,1，1，3,3，1，1,4，6,4，1，...

????????給定一個正整數(shù)N，請你輸出數(shù)列中第一次出現(xiàn)Ⅳ是在第幾個數(shù)?

【輸入格式】

????????輸入一個整數(shù)N。

【輸出格式】

????????輸出一個整數(shù)代表答案。

【樣例輸入】

? ? ? ? 6

【樣例輸出】

? ? ? ? 13

?

?【思路與分析】

? ? ? ? 首先，要新建一個數(shù)組以存放楊輝三角中的值。該長度通過題目中所給出的圖示進行計算，此時有一個小竅門。通過觀察可知楊輝三角左右半邊的值為相同的，或者說楊輝三角是中心對稱的。因此，可以先從中間一分為二，選取左半邊或右半邊進行計算。

? ? ? ? 經(jīng)過觀察，不難總結(jié)出規(guī)律：y?= x * (x-1) / 2

????????后續(xù)計算同樣基于該規(guī)律所做。

【代碼】

import java.util.*;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        long N= sc.nextLong();
        //經(jīng)過計算在第44721行的時候，第三列的值將會超過十億
        //所以我們創(chuàng)建44725長度的數(shù)組
        long[] a=new long[44725]; 
        a[0]=1L;	//將數(shù)組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--) {
        		//按照楊輝三角的數(shù)字規(guī)律填充數(shù)組
        		a[j]=a[j]+a[j-1];
                //找到了N，則輸出當前位置，位置 的計算等于 前面的個數(shù) + 當行的位置數(shù) 
        		if(a[j]==N) {  
        			//前面的個數(shù) = (count+1)*count/2  ，當行的個數(shù) = i-j+1
        			System.out.println((count+1)*count/2+i-j+1);
        			return;
        		}
        	}
            //判斷完后，標志位++
        	count++;
        }
        //這是未找到的情況，就是說有些小于10億的數(shù)在44721行之前都還沒有出現(xiàn) ，
        //那么它必然是出現(xiàn)在未顯示出來的第二列的位置上
        System.out.println((N+1)*N/2+2); 
        //所以 位置 = 前面出現(xiàn)的個數(shù) + 2
    }
}

【Q&A】

? ? ? ? 為什么在for循環(huán)中不使用 break 而使用return？

? ? ? ? 答：return在for循環(huán)中的作用為：返回return所返回的值，并不會執(zhí)行下一次循環(huán)。因不能干擾count標志位的運算，因此 使用return代替break。若使用break，在OJ測試時將只有60分，無法拿到滿分。

? ? ? ? 為什么在存入數(shù)組元素時使用 1L 而不是 1？

? ? ? ? 答：L表示long ，long占用8個字節(jié)，表示范圍：-9223372036854775808 ~ 9223372036854775807?
1L其實就是1。

后面跟L一般是指數(shù)據(jù)類型，1L表示1是長整型，如果是1f 表示是float型，若是1 則表示 int 型。文章來源地址http://www.zghlxwxcb.cn/news/detail-434506.html

到了這里，關(guān)于【藍橋杯】歷屆真題 楊輝三角形 （省賽）Java的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！