杨辉三角形详解

 

 
 

  

杨辉三角形

前提：每行端点与结尾的数为1。

1. 每个数等于它上方两数之和。

2. 每行数字左右对称，由 1 开始逐渐变大。

3. 第 n 行的数字有 n 项。

4. 前 n 行共[(1 + n) * n] / 2 个数。

5. 第 n 行的 m 个数可表示为 C(n - 1，m - 1)，即为从 n - 1 个不同元素中取 m - 1 个元素的组合数。

6. 第 n 行的第 m 个数和第 n - m + 1个数相等 ，为组合数性质之一。

7. 每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第 n + 1 行的第 i 个数等 8 于第 n 行的第 i - 1 个数和第 i 个数之和，这也是组合数的性质之一。即 C(n + 1, i) = C(n, i) + C(n, i - 1)。

8. (a + b) * n的展开式中的各项系数依次对应杨辉三角的第 (n + 1) 行中的每一项。

9. 将第 2n + 1 行第 1 个数，跟第 2n + 2 行第 3 个数、第 2n + 3 行第 5 个数……连成一线，这些数的和是第 4n + 1 个斐波那契数；将第 2n 行第 2 个数(n > 1)，跟第 2n - 1 行第 4 个数、第 2n - 2 行第 6 个数……这些数之和是第 4n - 2 个斐波那契数。
   

10. 将第 n 行的数字分别乘以10^（m-1），其中m为该数所在的列，再将各项相加的和为11^（n-1）。11⁰ = 1，11¹ = 1 x 10⁰ + 1 × 10¹ = 11，11² = 1 × 10⁰ + 2 x 10¹ + 1 x 10² = 121，11³ = 1 x 10⁰ + 3 × 10¹ + 3 x 10² + 1 x 10³ = 1331，11⁴ = 1 x 10⁰ + 4 x 10¹ + 6 x 10² + 4 x 10³ + 1 x 10⁴ = 14641，11⁵ = 1 x 10⁰ + 5 x 10¹ + 10 x 10² + 10 x 10³ + 5 x 10⁴ + 1 × 10⁵ = 161051。
    

11. 第 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）。
    

12. 斜线上数字的和等于其向左（从左上方到右下方的斜线）或向右拐弯（从右上方到左下方的斜线），拐角上的数字。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。
    

13. 将各行数字左对齐，其右上到左下对角线数字的和等于斐波那契数列的数字。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)），又由于找第一次出现，因此一定在左边，右边可以直接删掉！

性质：

1. 每一斜行从上到下递增
2. 每一横行从中间到两边依次递减

倒序（从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];
    }
};