Java 中的帕斯卡三角形

Mehvish Ashiq 2023年1月30日 2022年4月27日
  1. 帕斯卡三角形
  2. 用 Java 編寫帕斯卡三角形程式的方法
Java 中的帕斯卡三角形

今天,我們將學習 Java Pascal 的三角形。我們將學習三種方法:組合方法、陣列和不使用陣列,並瞭解這些方法的時間和空間複雜度。

帕斯卡三角形

它是二項式係數三角陣列。它是一個數字三角形,其中每個數字都是直接位於其上方的兩個數字的總和,不包括全為 1 的邊。

例如,1+1 = 21+3 = 4,如下所示:

java 帕斯卡三角 - 帕斯卡三角

用 Java 編寫帕斯卡三角形程式的方法

在這裡,我們將學習使用 Java 程式設計列印帕斯卡三角形的三種方法。

  • 使用組合(組合是一個統計概念)用於 Java 帕斯卡的三角形
  • 使用陣列列印帕斯卡三角形
  • 不使用陣列列印帕斯卡三角形

讓我們更深入地研究上面列出的每種方法。

在 Java 中使用組合列印帕斯卡三角形

示例程式碼:

//pascalTriangle class
public class pascalTriangle {

    /*
    n number of lines of Pascal's triangle
    */
    static void printPascalTriangle(int n){

        for(int line = 0; line < n; line++){
            for(int k = 1; k < n-line; k++)
                System.out.print(" ");
            for(int j = 0; j <= line; j++)
                System.out.print(nCr(line,j) + " ");
            System.out.println();
        }
    }

    //calculates each entry of every line in Pascal's triangle
    static int nCr(int n, int r){

        int numerator = 1, denominator = 1;
        if(n < r || n == 0)
            return 1;

        for(int i = r; i >= 1; i--){
            numerator = numerator * n--;
            denominator = denominator * i;
        }
        return (numerator/denominator);
    }

    //main method
    public static void main(String args[]){
        int numberOfLines = 5;
        printPascalTriangle(numberOfLines);
    }
}

輸出:

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

我們使用組合使用 Java 程式設計列印帕斯卡三角形。在 main 方法中,我們獲取 numberOfLines 並將其傳遞給 printPascalTriangle() 方法以列印三角形。

printPascalTriangle() 方法進一步呼叫 nCr() 方法來計算每一行中的每個條目。每個行號等於條目數。

例如,第 1 行有一個條目 1,第 2 行有兩個條目 1 1,第 3 行有三個條目 1 2 1

在這裡,每個條目都是在 nCr() 方法中使用以下公式計算的:

nCr = n! / (r! * (n-r)!)

這裡,nCr 是組合的數量,n 是集合中物件的總數,r 是從集合中選擇物件的數量。以下是每個條目的計算的視覺化演示:

java 帕斯卡三角 - 入口計算

通過使用這種方法,時間複雜度將為 O(n3),因為我們為兩個迴圈中的每個條目呼叫 nCr() 函式。請記住,nCr() 本身使用 for 迴圈來計算每一行的每個條目,方法是使用 nCr = n! / (r! * (n-r)!) 公式。

我們可以降低這個時間複雜度嗎?是的。我們可以使用二維陣列來做到這一點,其解決方案如下所示。

在 Java 中使用陣列列印帕斯卡三角形

如果我們專注於每個條目,我們可以在前一行的正上方看到兩個數字的總和。三角形外的所有數字都是零。

例如,第一行是 0 1 0,其中 1 是帕斯卡三角形的一部分,而 0s 是不可見的。我們也可以說帕斯卡三角形的每一行都夾在兩個零之間。

請看以下演示:

java pascal 的三角形 - 每個條目是前兩個數字的總和

這讓我們考慮使用二維陣列來計算、儲存和列印帕斯卡三角形的值。

示例程式碼:

public class pascalTriangle {

    //calculate all entries of Pascal's triangle
    static int[][] calPascalTriangleEntries(int n){
        //create 2D array of n size
        int ncrArray[][] = new int[n][n];

        //the first entry will always be 1
        ncrArray[0][0] = 1;

        //starting from the second row
        for(int i=1; i<n; i++){
            //the first entry of each row is always 1
            ncrArray[i][0] = 1;
            for(int j=1; j<=i; j++)
                ncrArray[i][j] = ncrArray[i-1][j-1] + ncrArray[i-1][j];
        }
        return ncrArray;
    }

    //print pascal's triangle
    static void printPascalTriangle(int pascalEntries[][], int n){
        //prints lines
        for(int i=0; i<n; i++){
            //print spaces
            for(int k=0; k<n-i; k++)
                System.out.print(" ");
            //prints entries
            for(int j=0; j<=i; j++)
                System.out.print(pascalEntries[i][j]+" ");
            System.out.println();
        }
    }

    //main method
    public static void main(String[] args) {
        int n = 5; //number of lines
        int pascalEntries[][] = calPascalTriangleEntries(n);
        printPascalTriangle(pascalEntries, n);

    }
}

輸出:

     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

在這裡,main 方法獲取行數並將其儲存在 n 變數中,該變數傳遞給 calPascalTriangleEntries() 方法以計算帕斯卡三角形的每一行的條目。它返回一個包含所有條目的陣列,我們將其儲存在 pascalEntries 中。

此外,我們將 pascalEntriesn 傳遞給 printPascalTriangle() 方法以將它們列印成三角形。請參閱上面給出的輸出。

這裡,時間複雜度為 O(n2)。空間複雜度為 O(n),因為我們使用了一個額外的陣列。

我們可以使用以下不使用陣列的解決方案來最小化空間複雜度。

在 Java 中不使用陣列列印 Pascal 的三角形

示例程式碼:

public class pascalTriangle {
    public static void main(String[] args) {
        int n = 5;
        int pascalEntry = 1;

        for(int line=0; line<n; line++){
            //Output the blank space
            for(int k=0; k<n-line; k++)
                System.out.print(" ");

            for(int column=0; column<=line; column++){
                if(column==0 || line==column)
                    pascalEntry = 1;
                else
                    pascalEntry = pascalEntry * (line-column + 1)/column;
                System.out.print(pascalEntry+" ");
            }
            System.out.println();
        }
    }
}

輸出:

     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

這個 main 方法使用以下公式來計算帕斯卡三角形中每一行的每個條目:

pascalEntry = pascalEntry * (line - column + 1) / column

這個解決方案很簡單。我們只需要處理巢狀 for 迴圈中每個 pascalEntry 的行(單獨的行)和列索引。

這裡,空間複雜度為 O(1),時間複雜度為 O(n2)。

Mehvish Ashiq avatar Mehvish Ashiq avatar

Mehvish Ashiq is a former Java Programmer and a Data Science enthusiast who leverages her expertise to help others to learn and grow by creating interesting, useful, and reader-friendly content in Computer Programming, Data Science, and Technology.

LinkedIn GitHub Facebook

相關文章 - Java Math