【問題描述】

成都創新互聯公司主營嵊泗網站建設的網絡公司,主營網站建設方案,重慶App定制開發,嵊泗h5小程序開發搭建,嵊泗網站營銷推廣歡迎嵊泗等地區企業咨詢

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

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

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

給定一個正整數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 型。

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站題目：【藍橋杯】歷屆真題楊輝三角形（省賽）Java-創新互聯
URL網址：http://www.2m8n56k.cn/article38/hodsp.html

成都網站建設公司_創新互聯，為您提供網站改版、網站排名、定制開發、品牌網站建設、外貿網站建設、網站設計

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：[email protected]。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯