楊輝三角形詳解

 

 
 

  

楊輝三角形

前提：每行端點與結尾的數為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];
    }
};