基本概念
这是一个杨辉三角。
记 \(a_{i,j}\) 为第 \(i\) 行第 \(j\) 列的数。
\(a_{i,j} = a_{i-1,j-1} + a_{i-1,j}\)
示例代码
#include <bits/stdc++.h>
using namespace std;
int n;
int a[105][105];int main(){scanf("%d",&n); //输入行数for(int i=1;i<=n;i++){a[i][1]=1;a[i][i]=1;for(int j=2;j<i;j++){a[i][j]=a[i-1][j-1]+a[i-1][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){printf("%d ",a[i][j]);}printf("\n");}return 0;
}
杨辉三角与组合数学的关系
记 \(a_{n,m}\) 为从 \(n\) 个数中选 \(m\) 个数的方案数,即 \(C_{n}^{m}\)。
显然,\(C_{n}^{m}=C_{n-1}^{m-1}+C_{n-1}^{m}\)。因为可以选择 \(n\) 或不选择。
可用于预处理组合数。
示例代码
#include <bits/stdc++.h>
#define mod 20123
using namespace std;
int n,m;
int a[105][105];int C(int n,int m){for(int i=0;i<=n;i++){ //nfor(int j=0;j<=m;j++){if(i<j) a[i][j]=0;else if(j==0) a[i][j]=1;else if(j==1) a[i][j]=i;else if(i==0) a[i][j]=0;else a[i][j]=(a[i-1][j-1]+a[i-1][j])%mod;}}return a[n][m];
}
int main(){scanf("%d%d",&n,&m);printf("从%d个数中选择%d个数共有%d种选法",n,m,C(n,m));return 0;
}
杨辉三角与二项式展开
众所周知,\((a+b)^{n} = C_{n}^{0} a^{n} + C_{n}^{1} a^{n-1} b + \dots + C_{n}^{n} b^{n}\)
记杨辉三角第一层高度为 \(0\),则杨辉三角第 \(n\) 层的所有数刚好等于 \(C_{n}^{0} \ C_{n}^{1} \ \dots \ C_{n}^{n}\)
同样可以预处理。
杨辉三角与网格图中的最短路径
这是一个网格图,途中每个点标的数是从 \((1,1)\) 点道现在这个点的最短路径有多少条。
可以发现,第 \(n\) 行标的数,就是杨辉三角的第 \(n\) 条斜列(从 \(1\) 开始计数)。
杨辉三角与斐波那契数列
1 1
1 1
1 1 2
1 2 3
1 3 1 5
1 4 3 8
... ...
将杨辉三角的每一斜列隔两行错一次位之后,每一行的和组成的数列即为斐波那契数列。
顺便纠正一下一些误区:斐波那契的汉语拼音是 fei bo na qi
。
写在后面
先写到这里吧,以后有时间再更新