杨辉三角形详解
文章目录杨辉三角形 杨辉三角形前提:每行端点与结尾的数为1。
杨辉三角形
前提:每行端点与结尾的数为1。
-
每个数等于它上方两数之和。
-
每行数字左右对称,由 1 开始逐渐变大。
-
第 n 行的数字有 n 项。
-
前 n 行共[(1 + n) * n] / 2 个数。
-
第 n 行的 m 个数可表示为 C(n - 1,m - 1),即为从 n - 1 个不同元素中取 m - 1 个元素的组合数。
-
第 n 行的第 m 个数和第 n - m + 1个数相等 ,为组合数性质之一。
-
每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第 n + 1 行的第 i 个数等 8 于第 n 行的第 i - 1 个数和第 i 个数之和,这也是组合数的性质之一。即 C(n + 1, i) = C(n, i) + C(n, i - 1)。
-
(a + b) * n的展开式中的各项系数依次对应杨辉三角的第 (n + 1) 行中的每一项。
-
将第 2n + 1 行第 1 个数,跟第 2n + 2 行第 3 个数、第 2n + 3 行第 5 个数……连成一线,这些数的和是第 4n + 1 个斐波那契数;将第 2n 行第 2 个数(n > 1),跟第 2n - 1 行第 4 个数、第 2n - 2 行第 6 个数……这些数之和是第 4n - 2 个斐波那契数。
-
将第 n 行的数字分别乘以10(m-1),其中m为该数所在的列,再将各项相加的和为11(n-1)。110 = 1,111 = 1 x 100 + 1 × 101 = 11,112 = 1 × 100 + 2 x 101 + 1 x 102 = 121,113 = 1 x 100 + 3 × 101 + 3 x 102 + 1 x 103 = 1331,114 = 1 x 100 + 4 x 101 + 6 x 102 + 4 x 103 + 1 x 104 = 14641,115 = 1 x 100 + 5 x 101 + 10 x 102 + 10 x 103 + 5 x 104 + 1 × 105 = 161051。
-
第 n 行数字的和为2(n-1)。1 = 2(1-1),1 + 1 = 2(2-1),1 + 2 + 1 = 2(3-1),1 + 3 + 3 + 1 = 2(4-1),1 + 4 + 6 + 4 + 1 = 2(5-1),1 + 5 + 10 + 10 + 5 + 1 = 2(6-1)。
-
斜线上数字的和等于其向左(从左上方到右下方的斜线)或向右拐弯(从右上方到左下方的斜线),拐角上的数字。1 + 1 = 2,1 + 1 + 1 = 3,1 + 1 + 1 + 1 = 4,1 + 2 = 3,1 + 2 + 3 = 6,1 + 2 + 3 + 4 = 10,1 + 3 = 4,1 + 3 + 6 = 10,1 + 4 = 5。
-
将各行数字左对齐,其右上到左下对角线数字的和等于斐波那契数列的数字。1,1,1 + 1 = 2,2 + 1 = 3,1 + 3 + 1 = 5,3 + 4 + 1 = 8,1 + 6 + 5 + 1 = 13,4 + 10 + 6 + 1 = 21,1 + 10 + 15 + 7 + 1 = 34,5 + 20 + 21 + 8 + 1 = 55。
例题
第一题
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int main(){
scanf("%d", &n);
int num[50][50];
num[1][1] = 1;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= i; j ++){
if(j == i || j == 1){
num[i][j] = 1;
printf("%d ", num[i][j]);
}
else{
num[i][j] = num[i - 1][j - 1] + num[i - 1][j];
printf("%d ", num[i][j]);
}
}
printf("\n");
}
return 0;
}
第二题
杨辉三角左右对称(C(a, b) == C(a, a-b)),又由于找第一次出现,因此一定在左边,右边可以直接删掉!
性质:
- 每一斜行从上到下递增
- 每一横行从中间到两边依次递减
倒序(从16开始)使用二分查找。
二分端点:l:2k r:max(n, l) n 为查找的数
右端点一定不能比左端点小!
特例:否则当 n = 1 时,会出问题。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n;
//C(a, b) = a!/b!(a-b)! = a * (a-1) .. b个 / b!
LL C(int a, int b){//求第a行第b列的值
LL cnt = 1;
for(int i = a, j = 1; j <= b; i --, j ++){
cnt = cnt * i / j;
if(cnt > n)//大于n没有意义,放在超long long
return cnt;
}
return cnt;
}
bool check(int k){// 二分该斜行,找到大于等于该值的第一个数
int l = 2 * k, r = max(n, l);
while(l < r){
int mid = l + r >> 1;
if(C(mid, k) >= n)
r = mid;
else
l = mid + 1;
}
if(C(r, k) != n)
return false;
printf("%lld", 1ll * (r + 1) * r / 2 + k + 1);//C(r, k)对应的顺序值为:(r + 1) * r / 2 + k + 1
return true;
}
int main(){
scanf("%d", &n);
for(int k = 16; ; k --)
if(check(k))
break;
return 0;
}
第三题
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> num;
for(int i = 0; i < numRows; i ++){
vector<int> a(i + 1);
for(int j = 0; j <= i; j ++){
if(j == 0 || i == j)
a[j] = 1;
else
a[j] = num[i - 1][j - 1] + num[i - 1][j];
}
num.push_back(a);
}
return num;
}
};
第四题
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<vector<int>> num;
for(int i = 0; i <= rowIndex; i ++){
vector<int> a(i + 1);
for(int j = 0; j <= i; j ++){
if(j == 0 || i == j)
a[j] = 1;
else
a[j] = num[i - 1][j - 1] + num[i - 1][j];
}
num.push_back(a);
}
return num[rowIndex];
}
};
更多推荐
所有评论(0)