C语言学习（帕斯卡三角）
C语言学习（帕斯卡三角）
关于帕斯卡三角，不做过多论述，可以先查看百度百科以及leetcode。我将演示几种常用方法打印帕斯卡三角。相较于官方题解我会写的更加易懂，便于读者学习。
解法1，使用数组存储每一列（如果你没有学习过组合数学，这是一种常用解法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int main() {
int pascal[MAX][MAX] = {0}; // 初始化二维数组，用于存储帕斯卡三角的每一行
int rows, i, j;
printf("Enter the number of rows: ");
scanf("%d", &rows);
// 计算并存储帕斯卡三角的每一行
for (i = 0; i < rows; i++) {
pascal[i][0] = 1; // 每行的第一个数是1
pascal[i][i] = 1; // 每行的最后一个数是1
for (j = 1; j < i; j++) {
pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]; // 每个数是上一行相邻两数之和
}
}
// 打印帕斯卡三角
for (i = 0; i < rows; i++) {
// 打印前导空格，使三角形居中
for (j = 0; j < rows - i; j++) {
printf(" ");
}
// 打印每行的数字
for (j = 0; j <= i; j++) {
printf("%4d", pascal[i][j]);
}
printf("\n");
}
return 0;
}另附leetcode的官方题解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
int** c = malloc(numRows * sizeof(int*));
*returnSize = numRows;
*returnColumnSizes = malloc(numRows * sizeof(int));
for (int i = 0; i < numRows; i++) {
(*returnColumnSizes)[i] = i + 1;
c[i] = malloc((i + 1) * sizeof(int));
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++) {
// 左上方的数 + 正上方的数
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
}
}
return c;
}
/* 作者：灵茶山艾府
链接：https://leetcode.cn/problems/pascals-triangle/solutions/2784222/jian-dan-ti-jian-dan-zuo-pythonjavaccgoj-z596/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 */解法2，使用二项式系数公式单独计算每一个值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 函数声明
int binomialCoeff(int n, int k);
int main() {
int rows, coef;
// 获取用户输入的行数
printf("Enter the number of rows: ");
scanf("%d", &rows);
// 打印帕斯卡三角形
for (int i = 0; i < rows; i++) {
// 打印空格以对齐三角形
for (int space = 1; space <= rows - i; space++)
printf(" ");
// 计算并打印每一行的二项式系数
for (int j = 0; j <= i; j++) {
coef = binomialCoeff(i, j);
printf("%4d", coef);
}
printf("\n");
}
return 0;
}
// 函数定义：计算二项式系数 C(n, k)
int binomialCoeff(int n, int k) {
int res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}解法3，基于解法2，我们也许还可以用递归来写
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// 函数声明
void printPascalTriangle(int rows, int row);
int binomialCoeff(int n, int k);
int main() {
int rows;
// 获取用户输入的行数
printf("Enter the number of rows: ");
scanf("%d", &rows);
// 从第0行开始打印
printPascalTriangle(rows, 0);
return 0;
}
// 使用递归打印帕斯卡三角形
void printPascalTriangle(int rows, int row) {
// 递归的基本情况：当行数超过输入的行数时停止
if (row >= rows)
return;
// 打印空格以对齐三角形
for (int space = 0; space < rows - row - 1; space++) {
printf(" ");
}
// 计算并打印每一行的二项式系数
for (int j = 0; j <= row; j++) {
printf("%4d", binomialCoeff(row, j));
}
printf("\n");
// 递归打印下一行
printPascalTriangle(rows, row + 1);
}
// 函数定义：计算二项式系数 C(n, k)
int binomialCoeff(int n, int k) {
int res = 1;
if (k > n - k)
k = n - k;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
