Java 中的帕斯卡三角形
今天,我们将学习 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(n3),因为我们为两个循环中的每个条目调用 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(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)。