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