【問題描述】

成都創(chuàng)新互聯(lián)公司主營嵊泗網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,重慶App定制開發(fā),嵊泗h5小程序開發(fā)搭建,嵊泗網(wǎng)站營銷推廣歡迎嵊泗等地區(qū)企業(yè)咨詢

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

如果我們按從上到下、從左到右的順序把所有數(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ìn)行計算，此時有一個小竅門。通過觀察可知楊輝三角左右半邊的值為相同的，或者說楊輝三角是中心對稱的。因此，可以先從中間一分為二，選取左半邊或右半邊進(jìn)行計算。

? 經(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) { //當(dāng)N==1,直接輸出1
        	System.out.println(1);
					return;
        }
        //聲明一個標(biāo)志位
        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，則輸出當(dāng)前位置，位置 的計算等于 前面的個數(shù) + 當(dāng)行的位置數(shù) 
        		if(a[j]==N) {  
        			//前面的個數(shù) = (count+1)*count/2  ，當(dāng)行的個數(shù) = i-j+1
        			System.out.println((count+1)*count/2+i-j+1);
        			return;
        		}
        	}
            //判斷完后，標(biāo)志位++
        	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標(biāo)志位的運算，因此 使用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 型。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：【藍(lán)橋杯】歷屆真題楊輝三角形（省賽）Java-創(chuàng)新互聯(lián)
鏈接地址：http://weahome.cn/article/hodsp.html