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