文章目录
前言
杨辉三角，是二项式系数在三角形中的一种几何排列。如下图所示，
杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。
本文将通过以下几个方面来实现杨辉三角：
1.用二维数组实现杨辉三角；
2.用一维数组实现杨辉三角；
2.1用两个一维数组实现杨辉三角；
2.2用一个一维数组实现杨辉三角；
3.不使用数组实现杨辉三角（使用for循环实现）
一、用二维数组实现杨辉三角
使用二维数组实现杨辉三角，也就是说，将杨辉三角看成是二维数组，有对应的行数和列数，例如，第1行第1列代表数1，第5行第2列代表4，如下图所示。
这里我们使用动态内存取申请二维数组，而二维数组可以看作是竖向的指针数组去指向横向的一维数组：
具体的实现过程如下代码所示：
void YangHui2(const int n) //利用二维数组去实现杨辉三角
{
//二维数组可以看作是竖向的指针数组去指向横向的一维数组
int** p = (int**)malloc(n * sizeof(int*)); //先申请竖的指针
for (int i = 0; i < n; i++) //再用竖的指针去指向横向的数组
{
p[i] = (int*)malloc(n * sizeof(int));
}
assert(p != NULL); //断言
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
//特殊处理，防止数组越界
if (j == 0 || i == j) //每一行的第一个值和最后一个值均为1
{
p[i][j] = 1;
}
else //其他的均是公式：当前值 = 上一行本列的值 + 上一行上一列的值
{
p[i][j] = p[i - 1][j] + p[i - 1][j - 1]; //此处不需要考虑数组越界问题，因为越界问题已经特殊处理
}
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= i; j++)
{
printf("%-5d", p[i][j]); //打印杨辉三角
}
printf("\n");
}
for (int i = 0; i < n; i++)
{
free(p[i]);//用malloc，一定要释放
}
free(p); //利用malloc后，释放指针p
}
这里打印10行杨辉三角，运行结果如下：（如果想要打印等腰三角形形式的，可自行细调输出格式，这里对格式不作要求）
二、用一维数组实现杨辉三角
1.用两个一维数组实现杨辉三角
此过程利用两个一维数组arr[]和brr[]，利用一个数组arr[]按照杨辉三角的规律进行下一行的计算，计算的值保存在另一个数组brr[]中，最后再将brr[]的值赋给数组arr[]，打印arr[]即可。
注意一点的就是初始将数组arr[]和brr[]的值全部赋值为1，这样方便计算。
具体的实现过程如下代码所示：
void YangHui1_2(const int n) //一维数组实现杨辉三角(用两个一维数组)
{
int* arr = (int*)malloc(n * sizeof(int));
int* brr = (int*)malloc(n * sizeof(int)); //申请brr是为了存放arr中计算的值，最后再将值赋给arr即可
assert(arr != NULL && brr != NULL); //断言指针不为空
for (int i = 0; i < n; i++) //将arr和brr的值全部赋值为1
{
arr[i] = 1; //将数组arr的值全部赋为1，是为了便于对数组进行操作
brr[i] = 1; //将数组brr的值全部赋为1，是为了便于对数组进行操作
}
for (int i = 0; i < n; i++) //外层循环处理第i行的数据
{
//这里内层j是从1开始，也就是第一列(j==0)不需要处理，因为都是1
for (int j = 1; j < i; j++) //内部循环处理每一层的数据
{
//这里不需要考虑数组越界问题，由于列数j是从第2列开始的，所以不存在越界问题
//利用公式不会超出第一列，最多到第一列，也就是brr[1] = arr[1] + arr[0];
brr[j] = arr[j] + arr[j - 1]; //利用公式处理完每一层的数据，存放在brr中
}
//以下利用for循环将brr的值重新赋给arr，并打印arr
for (int k = 0; k <= i; k++)
{
arr[k] = brr[k]; //将计算的值再重新赋给arr
printf("%-5d", arr[k]); //打印arr
}
printf("\n");
}
free(arr); //利用malloc后，要进行释放
free(brr);
}
这里打印10行杨辉三角，运行结果如下：
2.用一个一维数组实现杨辉三角
利用一个一维数组，此方法是一维数组的第一个值赋值为1，剩余赋值为0，然后从后向前按照杨辉三角的规律推断前面的值。
这里需要注意边界、特殊值的处理，防止数组越界。
具体的实现过程如下代码所示：
void YangHui1_1(const int n) //一维数组实现杨辉三角(只用一个一维数组)
{
//int* arr = (int*)malloc(n * sizeof(int)); //动态申请一个一维数组arr
//利用calloc动态申请n*sizeof(int)大小空间之后，会将里面的值全部初始化为0
int* arr = (int*)calloc(n, sizeof(int)); //注意此处为什么要用calloc，而不用malloc
/*
【注】此处用calloc，注意calloc和malloc的区别
calloc：在内存的动态存储区中分配n个长度为sizeof(int)的连续空间，
不同点：calloc在动态分配完内存后，自动初始化该内存空间为【零】，而malloc不初始化，里边数据是随机的垃圾数据
*/
assert(arr != NULL); //断言
arr[0] = 1; //将数组的第一个值赋值为1
for (int i = 0; i < n; i++) //此层循环是处理第i行的数据，也就是控制层数
{
//此方法是一维数组的第一个值赋值为1，剩余赋值为0，然后从后向前推
for (int j = i; j >= 1; j--)
{
//若从后向前处理，当i=0时，不需要处理（循环进不去），当i=1时，也就是第2行，只需处理一个值
/*
1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
1 2 1 0 0 0 0 0 0
1 3 3 1 0 0 0 0 0
*/
//第一列不需要处理，从后向前，也即j>=1是退出条件
arr[j] = arr[j] + arr[j - 1]; //当前值 == 当前值（初始均为0）+ 上一个位置的值
}
for (int k = 0; k <= i; k++) //小于等于i是因为第i行只需要打印i个值
{
printf("%-5d", arr[k]);
}
printf("\n");
}
free(arr); //利用malloc后，要释放指针arr
}
这里打印10行杨辉三角，运行结果如下：
三、不用数组实现杨辉三角
不用数组实现杨辉三角，这里利用for循环实现：
第一个数是1；
第二个数是：1*(n - 1)/1；
第三个数是：1*(n - 1)/1 * (n - 2 )/2；
第四个数是：1*(n - 1)/1 * (n - 2 )/2 * (n - 3)/3
根据规律得到计算公式：tmp = tmp * (i - (j - 1))/(j - 1); //用到上一个值*(i - (j - 1))/(j - 1)
具体的实现过程如下代码所示：
int YangHui(const int n) //不用数组实现杨辉三角，利用for循环直接实现杨辉三角
{
//第n行：第一个数是1；第二个数是：1*(n - 1)/1；第三个数是：1*(n - 1)/1 * (n - 2 )/2；
// 第四个数是：1*(n - 1)/1 * (n - 2 )/2 * (n - 3)/3
//tmp = tmp * (i - (j - 1))/(j - 1); //用到上一个值*(i - (j - 1))/(j - 1)
if (n < 0)
{
return -1;
}
int tmp = 0; //先申请一个变量tmp
for (int i = 1; i <= n; i++) //此处是从第一行开始，处理每一层的数据
{
for (int j = 1; j <= i; j++) //注意此处是从下标1开始的，也就是第一列的列下标均为1
{
if (j == 1) //每一行的第一个值特殊处理，其它的值均用公式，从后向前推导
{
tmp = 1; //第一列的值均为1，第一列作为特殊列处理
}
else
{
tmp = tmp * (i - (j - 1)) / (j - 1); //公式
}
printf("%-5d", tmp);
}
printf("\n");
}
}
这里打印10行杨辉三角，运行结果如下：