杨辉三角讲解

一、背景（阅读时可略过）

（1）杨辉其人

杨辉，字谦光，杭州人，中国南宋时期杰出的数学家和数学教育家。他是世界上第一个排出丰富的纵横图和讨论其构成规律的数学家。著有《详解九章算法》、《日用算法》、《乘除通变本末》、《田亩比类乘除捷法》、《续古摘奇算法》。 杨辉的数学研究与教育工作的重点是在改进筹算计算技术方面，有的还编成了歌诀，如九归口诀。

（2）杨辉三角的发现

杨辉三角不是杨辉首先发现的，而是杨辉之前约200年的贾宪创造的。在杨辉1261年所著的《详解九章算法》一书中，辑录了三角形数表，称之为“开方作法本源”图，并说它“出释锁算书，贾宪用此术”。杨辉三角的发现渊源于高次方程的数值解法。

二、性质

（1）除第一个以外任意一个数等于肩上两数之和

（2）外侧全部是1

（3）自然数序列

（4）三角形数：n(n+1)/2

（5）四面体数：1/6n(n+1)(n+2)

（6）2的次方数：2^(n-1）

（7）斐波那契数列

（8）组合数：（n从零开始）C(n,0)an+C(n，1)a(n-1)b+C(n，2)a(n-2)b2+...+C(n，n-1)ab(n-1)+bn

（9）二项展开式

……

三、经典算法思想

根据上述杨辉三角的性质，我们可以推出其中三种基本思想：

四、相关题型

（均取自洛谷，讲解中部分语句为引用）

（1）P5732 杨辉三角

F1：打表输出（不再赘述）

F2：枚举法（两肩上的数的和等于这个数）

F3：递推思想（两肩上的数的和等于这个数）

（2）P8749 杨辉三角形

F1：打暴力（20分）

F2：二分查找（AC？）

若使用二分查找解决此题：

杨辉三角特性↓

①分析：

按照对角线顺序分析，在原图第n行，且位于第m条对角线上的数，为 C（n,m）​，如图（图中的n指的是层数减一）。根据数位于的层数和对角线数可以计算数是第几个。例如：C(n,m) 就是位于第n层第m个对角线的数， (n+1)*n/2+m+1就是该数字对应的位置。

②二分查找：

按对角线顺序遍历，可以利用单调性进行二分。每一个对角线开头的元素都符合C(2k,k)条件，且对角线上，后面的数一定大于前面的数。注：k为任意常数。本题中的数据最大为10^9，C（32,16）已经大于10^9，所以下面的代码中我们只需要枚举0—16即可。

for(int i=16; i>=0; i--) {
	if(C(2*i,i)<=n) { //遍历对角线开头，因为后面的数一定比开头大
		long long mid,l=i,r=1000000005;
		while(l<r) { //二分查找该对角线下的对应答案
			mid=(l+r+1)>>1;
			long long t=C(mid,i);
			if(t==n) {
				cout<<(mid+1)*mid/2+i+1;//计算第mid层，第i条对角线数据是第几个  Tips:杨辉三角最上层是第0层
				return 0;
			} else if(n>t) {
				l=mid;
			} else {
				r=mid-1;
			}
		}
	}
}

五、总结

我们可以看到，在杨辉三角为背景的题中，大多运用了杨辉三角自身的特性和规律，所以在做数学这类题型时应先找到其规律，对其进行分析后再用所推公式作答。