当前位置：首页 > news >正文

C语言：实现杨辉三角的种方法

news 2025/6/21 10:37:43

一.杨辉三角的数学原理

杨辉三角的定义：二项式系数在三角形中的几何排列

二.基础二维数组法


#include <stdio.h>
#define N 10void printPascalTriangle(int n) {int triangle[N][N];// 初始化第一列和对角线为1for (int i = 0; i < n; i++) {triangle[i][0] = 1;triangle[i][i] = 1;}// 计算中间元素for (int i = 2; i < n; i++) {for (int j = 1; j < i; j++) {triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];}}// 打印三角形for (int i = 0; i < n; i++) {// 打印前导空格for (int k = 0; k < n - i - 1; k++) {printf(" ");}for (int j = 0; j <= i; j++) {printf("%d ", triangle[i][j]);}printf("\n");}
}int main() {printPascalTriangle(10);return 0;
}

使用二维数组存储每个元素
第一列和对角线元素都为1
其他元素等于上一行同列和前一列元素之和
简单直观，但空间复杂度为O(n²)

三.优化空间的一维数组法

#include <stdio.h>
#define N 10void printPascalTriangle(int n) {int row[N];for (int i = 0; i < n; i++) {// 从后往前计算避免覆盖row[i] = 1;for (int j = i - 1; j > 0; j--) {row[j] = row[j] + row[j-1];}// 打印前导空格for (int k = 0; k < n - i - 1; k++) {printf(" ");}// 打印当前行for (int j = 0; j <= i; j++) {printf("%d ", row[j]);}printf("\n");}
}int main() {printPascalTriangle(10);return 0;
}

只使用一维数组，空间复杂度降为O(n)
从后往前计算避免覆盖前一次的结果
更高效的内存使用，但逻辑稍复杂

四.递归实现

#include <stdio.h>int pascalValue(int row, int col) {if (col == 0 || col == row) {return 1;}return pascalValue(row - 1, col - 1) + pascalValue(row - 1, col);
}void printPascalTriangle(int n) {for (int i = 0; i < n; i++) {// 打印前导空格for (int k = 0; k < n - i - 1; k++) {printf(" ");}for (int j = 0; j <= i; j++) {printf("%d ", pascalValue(i, j));}printf("\n");}
}int main() {printPascalTriangle(10);return 0;
}

使用递归计算每个位置的值
代码简洁，符合数学定义
效率较低，有大量重复计算
时间复杂度为O(2ⁿ)

五.组合数公式法

#include <stdio.h>int factorial(int n) {if (n == 0) return 1;return n * factorial(n - 1);
}int combination(int n, int k) {return factorial(n) / (factorial(k) * factorial(n - k));
}void printPascalTriangle(int n) {for (int i = 0; i < n; i++) {// 打印前导空格for (int k = 0; k < n - i - 1; k++) {printf(" ");}for (int j = 0; j <= i; j++) {printf("%d ", combination(i, j));}printf("\n");}
}int main() {printPascalTriangle(10);return 0;
}

利用组合数公式C(n,k) = n!/(k!(n-k)!)
数学意义明确
计算阶乘容易溢出，效率不高
适合理论理解，实际应用有限

六.动态规划优化

#include <stdio.h>
#define N 10void printPascalTriangle(int n) {int triangle[N][N];for (int i = 0; i < n; i++) {// 打印前导空格for (int k = 0; k < n - i - 1; k++) {printf(" ");}for (int j = 0; j <= i; j++) {// 第一列和对角线为1if (j == 0 || j == i) {triangle[i][j] = 1;} else {triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];}printf("%d ", triangle[i][j]);}printf("\n");}
}int main() {printPascalTriangle(10);return 0;
}

结合了方法一和方法二的优点
边计算边打印，减少内存访问
代码结构更紧凑
仍然使用二维数组，但计算和输出合并

七.使用指针的方法

#include <stdio.h>
#include <stdlib.h>void printPascalTriangle(int n) {int **triangle = (int **)malloc(n * sizeof(int *));for (int i = 0; i < n; i++) {triangle[i] = (int *)malloc((i + 1) * sizeof(int));triangle[i][0] = 1;triangle[i][i] = 1;for (int j = 1; j < i; j++) {triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];}// 打印前导空格for (int k = 0; k < n - i - 1; k++) {printf(" ");}for (int j = 0; j <= i; j++) {printf("%d ", triangle[i][j]);}printf("\n");}// 释放内存for (int i = 0; i < n; i++) {free(triangle[i]);}free(triangle);
}int main() {printPascalTriangle(10);return 0;
}