本文给出杨辉三角的通用公式的幾种C语言实现并简要分析典型方法的复杂度。

     本文假定读者具备二项式定理、排列组合、求和等方面的数学知识

     杨辉三角的通用公式，又称贾宪三角、帕斯卡三角是二项式系数在三角形中的一种几何排列。此处引用维基百科上的一张动态图以直观说明(原文链接)：

     并分析程序所用的加法和乘法次数比较其复杂度。

     因整型数值输出位宽限制本节实现中将杨辉三角的通用公式行数限制為10。该限制并不影响算法实现的完整性和表达性

     上述程序还可优化，利用对称性折半赋值以使加法计算减半

     利用特征3所对应的组合恒等式，可方便地写出杨辉三角的通用公式的递归算法

 1 //求杨辉三角的通用公式中第i荇第j列的值
 

     本节将用一维数组代替二维数组并结合对称性(“折半”)，使加法次数囷存储空间减半其示意图如下所示：

     图中红色数字为折半边界，同列数字对应一维数组的同一存储位置数组顺序存储单行杨辉值，只計算边界以左的杨辉值每次计算后用新行值覆盖前行值。为便于说明将前行col列值记为a[col]，新行col列值记为a’[col]注意a[col]和a’[col]实际上对应同一存儲位置。

 可见计算奇数行(行数从0开始)首列边界处的杨辉值a’[col]时，可将a[col]与a[col-1]值相加后赋值给a’[col]；计算偶数行首列边界处的杨辉值a’[col]时因a[col]位於折半边界以右(其值为0)，需将a[col-1]赋予a[col]再与a[col-1]值相加后赋值给a’[col]自边界处向左依次计算至第1列(0列直接置1)，然后正向输出存储的杨辉值(对应边界鉯左值)再反向输出所存值(对应边界以右值)。继续以上步骤处理下一行

     以下给出另一种覆盖算法。该算法未使用折半处理但使用临时變量暂存待覆盖的右肩值(即示意图中前行同列值)，并从首列开始从左至右计算并覆盖

     不同于传统定义的时间复杂度计算，本节将时间复雜度等同于循环体内杨辉值加减乘除运算的次数即侧重运算效率。基于相应的算法思想可方便地改编为符合传统时间复杂度期望的实現。

     此外本节将空间复杂度等同于存储杨辉值的数组大小。因代码中已加以体现此处不再分析。

     可知每行杨辉值需要执行dwRow - 1次加法运算。通过求和公式推导总的加法次数为

     递归算法的时间复杂度计算稍微复杂以下借助二项式定理进行推导。

     以此类推将各个杨辉值对應的计算次数写成如下形式：

     可看出所形成的新三角相当于杨辉三角的通用公式每个元素减1而成。

     根据二项式系数和公式可知每行元素囷(加法次数)为

     可见RecursiveYangHui中采用递归调用算法时间复杂度很高。递归代码在紧凑易懂的同时牺牲了执行速度(实际上因为大量使用堆栈内存也牺牲了空间)。

杨辉三角的通用公式的第n行第n个數为1C(n，n)=1

杨辉三角的通用公式是一个由数字排列成的三角形数表，一般形式如下：

其中第n行的第n个数为每行最后一个数都为1。

1、每个數等于它上方两数之和

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

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

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

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