基礎練習 楊輝三角形-藍橋杯-Java

問題描述

楊輝三角形又稱Pascal三角形，它的第i+1行是(a+b)i的展開式的系數。　　

它的一個重要性質是：三角形中的每個數字等于它兩肩上的數字相加。

下面給出了楊輝三角形的前4行：　

   1

  1 1

 1 2 1　

1 3 3 1

給出n，輸出它的前n行。

輸入格式

輸入包含一個數n。

輸出格式

輸出楊輝三角形的前n行。每一行從這一行的第一個數開始依次輸出，中間使用一個空格分隔。請不要在前面輸出多餘的空格。

樣例輸入

4

樣例輸出

1

1 1

1 2 1

1 3 3 1

資料規模與約定

1 <= n <= 34。

自身分析:

感覺這道題對于我來說還是有難度的,自身對二維數組陌生..導緻将此題難度無限放大,是以當天隻是開個頭,怎樣思考都沒有思路,直接選擇了先放棄,過些時日再來解答.過了一天,換了一道題   審美課, 這題依然用到了二維數組,沒辦法,隻能去百度搜關于二維數組的相關知識,經過半天時間,終于寫出來了,盡管由于寫的代碼太爛,運作逾時,但結果是出來了,先不談.

回過頭在做這道題,感覺沒有了當時的恐懼感.在仔細分析,找到規律,慢慢就寫出來了.

題目分析:

看題目中的兩個提示點,一個是(a+b)i的展開式的系數,對于這個實在無從下手,另外一個三角形中的每個數字等于它兩肩上的數字相加.就是這個,在看草稿中的二維數組角标,就可以看到規律,每行除了開頭和結尾,其餘角标的值等于目前行-1的相同角标+目前行-1的角标-1.這就是關鍵點,基本該題大概思路就有了.

草稿

源代碼:

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[][] pas = new int[n][];
    
    for (int i = 0; i < pas.length; i++) {
      pas[i] = new int[i+1];// 每行列數等于行數
    }
    
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < i+1; j++) {  
        if(j==0){ // 每行的首元素為1
          pas[i][0] = 1;
        } else if(j==i){ // 每行的尾元素為1
          pas[i][i] = 1;
        }else{
          pas[i][j]=pas[i-1][j]+pas[i-1][j-1]; //此處為規律的展現
        }
      }
    }
    for (int i = 0; i < pas.length; i++) {
      for (int j = 0; j < pas[i].length; j++) {
        System.out.print(pas[i][j]+" ");
      }
      System.out.println();
    }
  }
}      

代碼優化:

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[][] pas = new int[n][];
    
    for (int i = 0; i < n; i++) {
      pas[i] = new int[i+1];
      for (int j = 0; j < i+1; j++) {  
        if(j==0||j==i){
          pas[i][j] = 1;
        }else{
          pas[i][j]=pas[i-1][j]+pas[i-1][j-1];
        }
        System.out.print(pas[i][j]+" ");
      }
      System.out.println();
    }
  }
}      

總結:

寫完後,浏覽了别人的代碼,其中一個可以說思路基本相似,但是代碼比我更精簡,自身代碼備援的原因是對雙重for循環的了解過于死闆,導緻代碼的重複使用,本來一個雙重for循環就可以解決自己卻用了三個才做出來.

對于代碼長度确實減少了,也減少了for循環的周遊,省去了兩次for循環.盡管省去了for循環的次數,對于系統消耗的時間以及占用記憶體的使用,由檢驗并未減少時間以及占用...