帕斯卡三角形——公式、模式和例子
陈莎拉
什么是帕斯卡三角形？
帕斯卡三角形是一个三角形的数字阵列，后面跟着特定的模式和与前一行的连接。它是由布莱斯·帕斯卡发明的。这个三角形从第一行的一个元素开始。此后，每行都以“1”开始和结束。
帕斯卡三角形的历史
中国古书《九章算术》中收录了帕斯卡三角形的最早例子之一。此外，它还包含当今三角形中的一些相同模式和特性。
帕斯卡是欧洲研究三角形的几个人之一。在他之前，其他数学家也研究过类似的三角形数字阵列。
帕斯卡三角形的构造
构造帕斯卡三角形很简单。你唯一需要记住的是，行以 1 开始和结束。其余数字的规则如下：
对于任何行 r 和列 c，该数字将是行 r-1 的 c-1 列和 c 列的总和。
在这里，
- r=3,4,5….
- n 和 c = 2,3,4,…r-1。
以下是构建帕斯卡三角形的步骤：
步骤1） 我们先填充两行。
步骤2） 第三行的第二个元素是第二行第一个数字和第二个数字的总和。
步骤3） 第四行以“1”开头。第二个数字是 3，它是 1 加 2 的总和（以蓝色突出显示）。
下图显示如何填充第四行：
步骤4） 第五行将包含五个数字。我们已经从前面的步骤中知道了填充行的模式。
帕斯卡三角公式 – 二项式系数
二项式系数是一个数字，它表示从 n 个元素的集合中选择 k 个元素子集的不同方法。它通常写为“C(n,k)”或“n 选择 k”。
二项式系数定义为
“！”表示“阶乘”。
n!= n.(n-1).(n-2)…3.2.1
例如，
5！ = 5.4.3.2.1
= 120
因此，假设 C(5,3) 或 5 选择 3 = 5! / 3!(5-3)!
= 120/(12)
= 10
方法 1：根据上一行构建帕斯卡三角形
此过程中的步骤与帕斯卡三角形中的步骤相同。假设我们要创建最多七行的帕斯卡三角形。
完成的步骤如下：
步骤1） 最顶行以“1”开始。
步骤2） 对于行“r”，“c”项将是“c-1”和“r-1”行的数字“c”的乘积。
步骤3） 行中第一个和最后一个数字始终为“1”。
我们必须遵循这三个简单的步骤来创建帕斯卡三角形。
C++ 帕斯卡三角形的上一行代码
#include <bits/stdc++.h>
using namespace std;
void printRow(int n)
{
int numbers[n][n];
for (int row = 0; row < n; row++)
{
for (int col = 0; col <= row; col++)
{
if (col == 0 || col == row)
{
numbers[row][col] = 1;
}
else
{
numbers[row][col] = numbers[row - 1][col - 1] + numbers[row - 1][col];
}
cout << numbers[row][col] << "\t";
}
cout << endl;
}
}
int main()
{
int n;
cout << "How many rows: ";
cin >> n;
printRow(n);
}
输出：
How many rows: 7 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
Python 帕斯卡三角公式代码按上一行
def printRow(n):
numbers = [[0 for row in range(n)]
for col in range(n)
]
for row in range(len(numbers)):
for col in range(0, row+1):
if row == col or col == 0:
numbers[row][col] = 1
else:
numbers[row][col] = numbers[row-1][col-1]+numbers[row-1][col]
print(numbers[row][col],end="\t")
print("\n")
n = int(input("How many rows: "))
printRow(n)
帕斯卡三角形示例输出：
How many rows: 7 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1
复杂度分析
A 二维数组 用于实现。假设 N 是帕斯卡三角形的行数。这将需要 N2 单位空间。因此，O 将是空间复杂度（N2).
函数中有两个循环，每个循环运行“N”次。因此，时间复杂度也是 在2) 或平方时间复杂度。
方法 2：通过计算二项式系数构建帕斯卡三角形
我们可以用二项式系数简单地推导出帕斯卡三角形的数字。下图是：
以下是通过计算二项式构建帕斯卡三角形的步骤：
步骤1） 最上面的行为 C(0,0)。使用上面的二项式系数公式，C(0,0) = 1。因为 0! = 1。
步骤2） 对于行“i”，总共有“i”个元素。每个项目将计算 C(n,r)，其中 n 为 i-1。
步骤3） 重复步骤 2，直到得到您想要的帕斯卡三角形的行数。
C++ 用二项式系数编码帕斯卡三角形
#include <iostream>
using namespace std;
int factorial(int n)
{
int result = 1;
for (int i = 1; i <= n; i++)
{
result *= i;
}
return result;
}
int binomialCoefficient(int n, int r)
{
int result = 1;
if (r > n)
{
return -1;
}
result = factorial(n) / (factorial(r) * factorial(n - r));
return result;
}
void printPascalTriangle(int row)
{
for (int i = 0; i <= row; i++)
{
for (int j = 0; j <= i; j++)
{
cout << binomialCoefficient(i, j) << "\t";
}
cout << endl;
}
}
int main()
{
int n;
cout << "Enter row number: ";
cin >> n;
printPascalTriangle(n);
}
输出：
Enter row number: 9 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1
Python 用二项式系数编码帕斯卡三角形
def factorial(n):
result = 1
for i in range(1,n+1):
result*=i
return result
def binomialCoefficient(n,r):
result =1
if r>n:
return None
result = factorial(n) / (factorial(r) * factorial(n - r))
return int(result)
def printPascalTriangle(row):
for i in range(row+1):
for j in range(i+1):
print(binomialCoefficient(i, j), end="\t")
print()
# print(binomialCoefficient(3, 2))
n = int(input("Enter row number: "))
printPascalTriangle(n)
帕斯卡三角形示例输出：
Enter row number: 8 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1
复杂度分析
实现中使用了三个循环。一个循环用于计算二项式系数，另外两个循环用于为所有行创建数字。关于行数，我们有三个循环执行“n”次。因此，总体时间复杂度将为 0(n3).
由于我们不在存储中保存任何数据，因此空间复杂度现在是恒定的。程序计算元素，并将其打印成一行。然后空间复杂度降低到 0(1)。
方法 3：利用修正二项式系数构建帕斯卡三角形
在上一个技巧中，我们已经了解了如何使用二项式系数来计算帕斯卡三角形的每个元素。此方法将从 C. (n, r-1) 确定 C(n,r)。它将使事情简化一个级别。
以下是利用修正二项式系数构建帕斯卡三角形的步骤：
步骤1） 第一行以“1”开头
步骤2） 计算 C(n,r)，其中“n”是行号，“r”是列或元素。将该值赋给变量 C。
步骤3） 计算 C(n,k) 时，结果为 C*(nk)/k。现在，将此值分配给 C。
步骤4） 继续步骤 3，直到“k”到达行尾。每次迭代后，将 K 的值加一。
C++ 用修正二项式系数计算帕斯卡三角形的代码
#include <bits/stdc++.h>
using namespace std;
void printpascalTriangle(int n)
{
for (int row = 1; row <= n; row++)
{
int previous_coef = 1;
for (int col = 1; col <= row; col++)
{
cout << previous_coef << "\t";
previous_coef = previous_coef * (row - col) / col;
}
cout << endl;
}
}
int main()
{
int n;
cout << "How many rows: ";
cin >> n;
printpascalTriangle(n);
}
输出：
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Python 用修正二项式系数计算帕斯卡三角形的代码
def printpascalTriangle(n):
for row in range(1, n+1):
previous_coef = 1
for col in range(1, row+1):
print(previous_coef, end="\t")
previous_coef = int(previous_coef*(row-col)/col)
print()
n = int(input("How many rows: "))
printpascalTriangle(n)
帕斯卡三角模式输出：
How many rows: 5 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
复杂度分析
该实现有两个循环。每个循环最多运行“n”次，其中“n”表示帕斯卡三角形中的行数。因此，时间复杂度为 上2)，平方时间。
至于空间复杂度，我们不需要任何数组来存储。我们只使用一个变量来保存前一个二项式系数。所以，我们只需要一个额外的空间。空间复杂度变为 O（1）.
帕斯卡三角形的应用
以下是帕斯卡三角形的一些应用：
二项式展开式： 我们可以从帕斯卡三角中确定二项式展开的系数。以下是一个例子：
| (x + y)0 | 1 |
| (x + y)1 | 1.x + 1.y |
| (x + y)2 | 1x2 + 2坐标 + 1y2 |
| (x + y)3 | 1x3 + 3x2和+ 3xy2 + 1y3 |
| (x + y)4 | 1x4 + 4x3和+ 6x2y2 + 4xy3 + 1y4 |
计算组合： 我们已经看到帕斯卡三角形的元素相当于二项式系数。例如，如果你有 6 个球，并被要求选择 3 个球，那么 6C3. 或者，你可以从帕斯卡三角形中找到第六行第三个元素的数字。
关于帕斯卡三角形的有趣事实
以下是有关帕斯卡三角形的一些有趣的事实：
- 一行中所有元素的总和始终是 2 的幂。
- 行元素的对角线和生成斐波那契数列。
结语
- 帕斯卡三角形给出了二项式展开式的系数。
- 帕斯卡三角的每一行都以“1”开始和结束。中间值是前一行两个元素的总和。
- 将帕斯卡三角形中的所有元素对角相加，将得到 斐波那契数列.
- 帕斯卡三角形也可以用二项式系数生成。
