【藍(lán)橋杯】歷屆真題楊輝三角形（省賽）Java-創(chuàng)新互聯(lián)

【問(wèn)題描述】

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

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

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

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

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

【輸入格式】

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

【輸出格式】

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

【樣例輸入】

? 6

【樣例輸出】

? 13

【思路與分析】

? 首先，要新建一個(gè)數(shù)組以存放楊輝三角中的值。該長(zhǎng)度通過(guò)題目中所給出的圖示進(jìn)行計(jì)算，此時(shí)有一個(gè)小竅門(mén)。通過(guò)觀(guān)察可知楊輝三角左右半邊的值為相同的，或者說(shuō)楊輝三角是中心對(duì)稱(chēng)的。因此，可以先從中間一分為二，選取左半邊或右半邊進(jìn)行計(jì)算。

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

后續(xù)計(jì)算同樣基于該規(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)過(guò)計(jì)算在第44721行的時(shí)候，第三列的值將會(huì)超過(guò)十億
        //所以我們創(chuàng)建44725長(zhǎng)度的數(shù)組
        long[] a=new long[44725]; 
        a[0]=1L;	//將數(shù)組0位置存入一個(gè)長(zhǎng)整形
        if(N==1) { //當(dāng)N==1,直接輸出1
        	System.out.println(1);
					return;
        }
        //聲明一個(gè)標(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)前位置，位置 的計(jì)算等于 前面的個(gè)數(shù) + 當(dāng)行的位置數(shù) 
        		if(a[j]==N) {  
        			//前面的個(gè)數(shù) = (count+1)*count/2  ，當(dāng)行的個(gè)數(shù) = i-j+1
        			System.out.println((count+1)*count/2+i-j+1);
        			return;
        		}
        	}
            //判斷完后，標(biāo)志位++
        	count++;
        }
        //這是未找到的情況，就是說(shuō)有些小于10億的數(shù)在44721行之前都還沒(méi)有出現(xiàn) ，
        //那么它必然是出現(xiàn)在未顯示出來(lái)的第二列的位置上
        System.out.println((N+1)*N/2+2); 
        //所以 位置 = 前面出現(xiàn)的個(gè)數(shù) + 2
    }
}

【Q&A】

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

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

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

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

后面跟L一般是指數(shù)據(jù)類(lèi)型，1L表示1是長(zhǎng)整型，如果是1f 表示是float型，若是1 則表示 int 型。

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

網(wǎng)站題目：【藍(lán)橋杯】歷屆真題楊輝三角形（省賽）Java-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://muchs.cn/article38/hodsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、網(wǎng)站排名、定制開(kāi)發(fā)、品牌網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

綿陽(yáng)服務(wù)器托管