[Day 19] Given an integer n, please print out the n-layer Yanghui triangle the application of Yanghui triangle

Hits: 0

This article has been included in the column

🌸《100 Cases of Getting Started with Java》🌸

study guide

Preface, column foreword

But the most important thing is to think independently. For all the contents of this column, if you can fully grasp the content of this column, and you can completely write the code yourself, there is definitely no problem with getting started with algorithms.
   The learning of algorithms must not lack a summary. Here I recommend that you check in the knowledge you have learned in the [algorithm community of colleges and universities , so as to consolidate and review it.]
  The only way to learn the algorithm well must be the question sea strategy , and the accumulation of a lot of practice can only cultivate one’s skills. For any topic in the column, I will explain it from four sections: [topic description] [problem-solving ideas] [template code] [code analysis].

1. What is the [Yanghui triangle] ?

When it comes to Yang Hui’s triangle , you must know Yang Hui’s character. He is a famous mathematician in the Southern Song Dynasty, and Yang Hui Triangle is the one who developed it. The Yanghui triangle is a geometric arrangement of binomial coefficients in a triangle. The nature of the Yanghui triangle is very, very important. But most importantly, two properties

  1. No. n n nThe first and last items of the line must be 1 1 1。
  2. No. i i ithe first of the line not a word jThe column corresponds to the sum of the above two elements, and the formula is:
    a [i] [ j ] = a [ i − 1 ] [ j ] + a [ i − 1 ] [ j − 1 ] a[i][j]=a[i-1][j]+a[i-1][j-1] a[i][j]=a[i−1][j]+a[i−1][j−1]

1. 【Example 1】

1. Description of the topic

given an integer n n n , please print out n n n -layer Yanghui triangle ( 1 ≤ n ≤ 1000 ) (1\leq n \leq1000) (1≤n≤1000)。

2. Problem solving ideas

You can simulate printing directly according to the properties mentioned above. It should be noted here that if you directly use the entire two-dimensional array to store the Yang Hui triangle, the storage space level is O ( n 2 ) O(n^2) O ( n2 ), which is very easy to burst space. Since the value of each layer is only related to the previous layer, we can consider using rolling arrays for optimization, two arrays are used alternately, and the space complexity is O(n) O(n) O ( n ) . Another thing to note is that since the accumulated sum increases very fast, after reaching a certain number of layers, the value may explodeint, so we need to use thelongtype.

3. Template code

import java.util.Scanner;

public class Main {
    static int N=1010;
    static long[] a=new long[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        a[1]=1;
        System.out.println(a[1]);
        for (int i = 2; i <=n; i++) {
            long[] b=new long[n+1];
            for (int j = 1; j <=i; j++) {
                b[j]=a[j-1]+a[j];
                System.out.print(b[j]+" ");
            }
            System.out.println();
            a=b;
        }
    }
}

in n n When n is not large, we can also use two-dimensional array storage and use the formula to calculate the Yanghui triangle.

import java.util.Scanner;

public  class Yang Hui's triangle formula { 
     public  static  void  main (String[] args)  {
             //This method can shorten the time complexity, and it is simple, focus on mastering 
            Scanner sc = new Scanner(System.in);
             int n = sc.nextInt ();
             int [][] nums = new  int [n][n];
             for ( int i= 0 ;i<n;i++){
                 long a = ( long ) 1 ;
                 for ( int j= 0 ;j< =i;j++){
                    System.out.print(a+ " " );
                     // a = a*(ij)/(j+1) is the point 
                    //The data is too large and may overflow, use long type 
                    a =a * (ij)/(j+ 1 );
                }
                System.out.println();
            }
        }
}

3. Recommended column

🌌《100 Days of Zero Basic Algorithms》🌌

4. After-school exercises

serial number topic link Difficulty rating
1 Yang Hui Triangle 2

👇 Have questions about learning? 👇

Leave a Reply

Your email address will not be published.