迹忆客 专注技术分享

今天，我们将学习 Java Pascal 的三角形。我们将学习三种方法：组合方法、数组和不使用数组，并了解这些方法的时间和空间复杂度。

帕斯卡三角形

它是二项式系数三角阵列。它是一个数字三角形，其中每个数字都是直接位于其上方的两个数字的总和，不包括全为 1 的边。

例如，1+1 = 2 和 1+3 = 4，如下所示：

用 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 是从集合中选择对象的数量。以下是每个条目的计算的可视化演示：

通过使用这种方法，时间复杂度将为 O(n³)，因为我们为两个循环中的每个条目调用 nCr() 函数。请记住，nCr() 本身使用 for 循环来计算每一行的每个条目，方法是使用 nCr = n! / (r! * (n-r)!) 公式。

我们可以降低这个时间复杂度吗？是的。我们可以使用二维数组来做到这一点，其解决方案如下所示。

在 Java 中使用数组打印帕斯卡三角形

如果我们专注于每个条目，我们可以在前一行的正上方看到两个数字的总和。三角形外的所有数字都是零。

例如，第一行是 0 1 0，其中 1 是帕斯卡三角形的一部分，而 0s 是不可见的。我们也可以说帕斯卡三角形的每一行都夹在两个零之间。

请看以下演示：

这让我们考虑使用二维数组来计算、存储和打印帕斯卡三角形的值。

示例代码：

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 中。

此外，我们将 pascalEntries 和 n 传递给 printPascalTriangle() 方法以将它们打印成三角形。请参阅上面给出的输出。

这里，时间复杂度为 O(n²)。空间复杂度为 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(n²)。