Tam giác Pascal Java

Tóm lược. Trong ví dụ lập trình này, chúng ta sẽ học ba cách khác nhau để in tam giác pascal trong Java

Phương pháp 1. Tam giác Pascal sử dụng tổ hợp

Mỗi hàng trong tam giác Pascal là các hệ số của khai triển nhị thức i. e. (hàng-1)C(cột-1)

Chúng ta có thể dễ dàng tính toán giá trị của (hàng-1)C(cột-1) trong Java và tạo tam giác pascal

Tất cả những gì chúng ta cần làm là xác định một hàm sẽ trả về giá trị của (hàng-1)C(cột-1) cho giá trị tương ứng của hàng và cột

Đây là cách triển khai phương thức trong Java

import java.util.Scanner;
 
class Main {
  public static void main(String[] args) {
 
    Scanner in = new Scanner(System.in);
    System.out.print("Enter value of n: ");
    int n = in.nextInt();
 
    for(int i=0; i<n; i++){
      for(int k=1; k<n-i; k++){
        System.out.print(" ");
      }
      for(int j=0; j<=i; j++){
        System.out.print(nCr(i,j)+" ");
      }
      System.out.println();
    }
    
  }
  //Function to return the value of nCr
  private static int nCr(int n, int r){
    if(n<r || n==0)
      return 1;
 
    int num = 1, den = 1;
    for(int i=r; i>=1; i--){
      num = num * n--;
      den = den * i;
    }
    return num/den;
  }
}

đầu ra

Độ phức tạp về thời gian của phương pháp này là O(n3) bởi vì, đối với mỗi số hạng bên trong 2 vòng lặp, chúng ta đang gọi một hàm kết hợp mà chính hàm này sử dụng vòng lặp for để tính giá trị của nCr

Chúng ta có thể giảm độ phức tạp của chương trình này bằng cách sử dụng mảng 2D

Phương pháp 2. Tam giác Pascal sử dụng Mảng

Nếu chúng ta để ý kỹ tam giác, chúng ta sẽ thấy rằng mỗi mục trong tam giác Pascal là tổng của hai giá trị của hàng trước đó

Do đó, chúng ta có thể sử dụng mảng 2D để tính toán và lưu trữ giá trị của từng thuật ngữ từ các giá trị được tạo trước đó và sau đó xuất mảng sẽ chứa các giá trị của tam giác pascal

import java.util.Scanner;
 
class Main {
  public static void main(String[] args) {
 
    Scanner in = new Scanner(System.in);
    System.out.print("Enter value of n: ");
    int n = in.nextInt();
 
    int ncr[][] = new int[n][n];
 
    ncr[0][0] = 1;  //First element is always 1
 
    //start from 2nd row i.e from i=1
    for(int i=1; i<n; i++){
      //First element of each row is always 1
      ncr[i][0] = 1; 
      for(int j=1; j<=i; j++){
        ncr[i][j] = ncr[i-1][j-1] + ncr[i-1][j];
      }
    }
 
    //Output the array
    for(int i=0; i<n; i++){
      //Output the blank space
      for(int k=0; k<n-i; k++){
        System.out.print(" ");
      }
      for(int j=0; j<=i; j++){
        System.out.print(ncr[i][j]+" ");
      }
      System.out.println();
    }
 
  }
}

đầu ra

Độ phức tạp về thời gian và không gian của phương pháp này lần lượt là O(n2) và O(n)

Độ phức tạp của không gian là do sử dụng một mảng bổ sung

Chúng ta có thể giảm độ phức tạp về không gian của chương trình này bằng cách không sử dụng mảng

Phương pháp 3. Tam giác Pascal không có mảng

Công thức cho mỗi số hạng của tam giác Pascal ngoại trừ phần tử đầu tiên và cuối cùng của mỗi hàng (luôn luôn là 1) là t=t*(i-j +1)/j

trong đó 'i' đại diện cho hàng, 'j' đại diện cho cột và 't' đại diện cho giá trị thuật ngữ cuối cùng

Tất cả những gì chúng ta cần làm là kiểm tra chỉ số hàng và cột của mỗi thuật ngữ bên trong vòng lặp lồng nhau. Nếu nó là hàng đầu tiên hoặc cột đầu tiên (i. e. if(j==0 || i==j)) chúng tôi sẽ chỉ xuất 1 nếu không chúng tôi sẽ xuất giá trị của t*(i-j +1)/j

Đây là cách triển khai phương thức trong Java

import java.util.Scanner;
 
class Main {
  public static void main(String[] args) {
 
    Scanner in = new Scanner(System.in);
    System.out.print("Enter value of n: ");
    int n = in.nextInt();
 
    int t=1;
 
    for(int i=0; i<n; i++){
      //Output the blank space
      for(int k=0; k<n-i; k++){
        System.out.print(" ");
      }
      for(int j=0; j<=i; j++){
        if(j==0 || i==j)
          t = 1;
        else
          t=t*(i-j +1)/j;
        
        System.out.print(t+" ");
      }
      System.out.println();
    }
 
  }
}

đầu ra

Độ phức tạp về thời gian và không gian của chương trình trên lần lượt là O(n2) và O(1)

Trong hướng dẫn này, chúng ta đã học với các ví dụ về các cách khác nhau để in tam giác Pascal bằng ngôn ngữ lập trình Java

Công thức tam giác Pascal là gì?

Tam giác Floyd trong Java là gì?

Công thức tính diện tích tam giác trong Java là gì?

Vấn đề tam giác trong Java là gì?