Alogrithm：巴斯卡三角形

巴斯卡三角形（Pascal's Triangle）是一个由数字排列成的三角形，每一行的数字是由前一行的两个相邻数字相加得到的。巴斯卡三角形的每一行对应着二项式展开式的系数。具体如下图所示：

巴斯卡三角形的性质

第 0 行只有一个数字 1。
第 1 行是 1 1。
第 2 行是 1 2 1。
第 3 行是 1 3 3 1。
第 4 行是 1 4 6 4 1。
以此类推。

规律：

三角形中的每个数字是由其上方两个数字之和得来的，边缘的数字始终是 1。

C 语言实现

这里提供两种方式：一种是通过二维数组构建，另一种是通过递推公式计算。

1. 使用二维数组

#include <stdio.h>// 函数用来打印巴斯卡三角形
void printPascal(int n) {// 创建一个二维数组，n 是行数int arr[n][n];// 填充巴斯卡三角形for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {if (j == 0 || j == i) {arr[i][j] = 1;  // 边缘的数字是 1} else {arr[i][j] = arr[i-1][j-1] + arr[i-1][j];  // 其他数字是上方两个数字之和}}}// 打印巴斯卡三角形for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {printf("%d ", arr[i][j]);}printf("\n");}
}int main() {int n;printf("Enter the number of rows for Pascal's Triangle: ");scanf("%d", &n);printf("Pascal's Triangle with %d rows:\n", n);printPascal(n);return 0;
}

示例运行：

Enter the number of rows for Pascal's Triangle: 5
Pascal's Triangle with 5 rows:
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1

2. 使用递推公式（组合数）

巴斯卡三角形中的每个数字实际上就是组合数 C(n,k)，其中 C(n,k) 是从 n 个元素中选取 k 个元素的组合数，公式为：

我们可以直接用递推公式来计算每个数字。

#include <stdio.h>// 计算组合数 C(n, k)
int combination(int n, int k) {if (k == 0 || k == n) {return 1;} else {return combination(n - 1, k - 1) + combination(n - 1, k);}
}// 打印巴斯卡三角形
void printPascal(int n) {for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {printf("%d ", combination(i, j));  // 打印每个组合数}printf("\n");}
}int main() {int n;printf("Enter the number of rows for Pascal's Triangle: ");scanf("%d", &n);printf("Pascal's Triangle with %d rows:\n", n);printPascal(n);return 0;
}