问题标题: 酷町堂：杨辉三角填数规律

【真香定律】

打脸 啪！

杨辉三角 

所属类别 :

拓扑

杨辉三角形，又称贾宪三角形，帕斯卡三角形，是二项式系数在三角形中的一种几何排列。

简介

杨辉三角形，又称贾宪三角形，帕斯卡三角形，是二项式系数在三角形中的一种几何排列。在我国南宋数学家杨辉所著的《详解九章算术》（1261年)一书中用如图的三角形解释二项和的乘方规律。杨辉三角形

历史

北宋人贾宪约1050年首先使用“贾宪三角”进行高次开方运算。

杨辉，字谦光，南宋时期杭州人。在他1261年所著的《详解九章算法》一书中，辑录了如上所示的三角形数表，称之为“开方作法本源”图，并说明此表引自11世纪前半贾宪的《释锁算术》，并绘画了“古法七乘方图”。故此，杨辉三角又被称为“贾宪三角”。

元朝数学家朱世杰在《四元玉鉴》（1303年）扩充了“贾宪三角”成“古法七乘方图”。

意大利人称之为“塔塔利亚三角形”（Triangolo di Tartaglia）以纪念在16世纪发现一元三次方程解的塔塔利亚。

在欧洲直到1623年以后，法国数学家帕斯卡在13岁时发现了“帕斯卡三角”。

布莱士·帕斯卡的著作Traité du triangle arithmétique（1655年）介绍了这个三角形。帕斯卡搜集了几个关于它的结果，并以此解决一些概率论上的问题，影响面广泛，Pierre Raymond de Montmort（1708年）和亚伯拉罕·棣·美弗（1730年）都用帕斯卡来称呼这个三角形。

近年来国外也逐渐承认这项成果属于中国，所以有些书上称这是“中国三角形”（Chinese triangle）

历史上曾经独立绘制过这种图表的数学家

·贾宪 中国北宋 11世纪 《释锁算术》

·杨辉 中国南宋1261《详解九章算法》记载之功

·朱世杰中国元代 1299《四元玉鉴》级数求和公式

·阿尔·卡西 阿拉伯 1427《算术的钥匙》

·阿皮亚纳斯德国 1527

·米歇尔`斯蒂费尔德国 1544《综合算术》二项式展开式系数

·薛贝尔 法国 1545

·B·帕斯卡 法国 1654《论算术三角形》

其实，中国古代数学家在数学的许多重要领域中处于遥遥领先的地位。中国古代数学史曾经有自己光辉灿烂的篇章，而杨辉三角的发现就是十分精彩的一页。

应用

性质6和性质7是杨辉三角的基本性质，是研究杨辉三角其他规律的基础。

与杨辉三角联系最紧密的是二项式乘方展开式的系数规律，即二项式定理。

例如，在杨辉三角中，第3行的三个数恰好对应着两数和的平方的展开式的每一项的系数，

即(a+b)²;=a²+2ab+b²

第4行的四个数恰好依次对应两数和的立方的展开式的每一项的系数

即(a+b)³=a³+3a²b+3ab²+b³

以此类推。

又因为性质6：第n行的m个数可表示为C(n-1,m-1)，即为从n-1个不同元素中取m-1个元素的组合数。因此可得出二项式定理的公式为：(a+b)ⁿ=C(n,0)aⁿ×bº+C(n,1)a^(n-1)×b¹+...+C(n,r)a^(n-r)×b^r...+C(n,n)aº×bⁿ

因此，二项式定理与杨辉三角形是一对天然的数形趣遇，它把数形结合带进了计算数学。求二项式展开式系数的问题，实际上是一种组合数的计算问题。用系数通项公式来计算，称为“式算”；用杨辉三角形来计算，称作“图算”。

折叠数在杨辉三角中的出现次数

由1开始，正整数在杨辉三角形出现的次数为∞,1, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 2, 4, ... （OEIS:A003016）。最小而又大于1的数在贾宪三角形至少出现n次的数为2, 3, 6, 10, 120, 120, 3003, 3003, ... （OEIS:A062527）

除了1之外，所有正整数都出现有限次，只有2出现刚好一次，6,20,70等出现三次；出现两次和四次的数很多，还未能找到出现刚好五次的数。120,210,1540等出现刚好六次。（OEIS:A098565）

因为丢番图方程 

有无穷个解，所以出现至少六次的数有无穷个多。解为

，其中Fn表示第n个斐波那契数（F1=F2=1）。

3003是第一个出现八次的数。

历史沿革

北宋人贾宪约1050年首先使用“贾宪三角”进行高次开方运算。

杨辉，字谦光，南宋时期杭州人。在他1261年所著的《详解九章算法》一书中，辑录了如上所示的三角形数表，称之为“开方作法本源”图，并说明此表引自11世纪中叶（约公元1050年）贾宪的《释锁算术》，并绘画了“古法七乘方图”。故此，杨辉三角又被称为“贾宪三角”。

元朝数学家朱世杰在《四元玉鉴》（1303年）扩充了“贾宪三角”成“古法七乘方图”。

意大利人称之为“塔塔利亚三角形”（Triangolo di Tartaglia）以纪念在16世纪发现一元三次方程解的塔塔利亚。

在欧洲直到1623年以后，法国数学家帕斯卡在13岁时发现了“帕斯卡三角”。

布莱士·帕斯卡的著作Traité du triangle arithmétique（1655年）介绍了这个三角形。帕斯卡搜集了几个关于它的结果，并以此解决一些概率论上的问题，影响面广泛，Pierre Raymond de Montmort（1708年）和亚伯拉罕·棣·美弗（1730年）都用帕斯卡来称呼这个三角形。

21世纪以来国外也逐渐承认这项成果属于中国，所以有些书上称这是“中国三角形”（Chinese triangle）

历史上曾经独立绘制过这种图表的数学家有：

• 贾宪 中国北宋 11世纪 《释锁算术》
• 杨辉 中国南宋1261《详解九章算法》记载之功
• 朱世杰 中国元代 1299《四元玉鉴》级数求和公式
• 阿尔·卡西 阿拉伯 1427《算术的钥匙》
• 阿皮亚纳斯 德国 1527
• 米歇尔.斯蒂费尔 德国 1544《综合算术》二项式展开式系数
• 薛贝尔 法国 1545
• B·帕斯卡 法国 1654《论算术三角形》

其实，中国古代数学家在数学的许多重要领域中处于遥遥领先的地位。中国古代数学史曾经有自己光辉灿烂的篇章，而杨辉三角的发现就是十分精彩的一页。

在编程中实现

杨辉三角在编程实现中较为容易。最常见的算法便是用上一行递推计算；也有运用和组合的对应关系而使用阶乘计算的，然而后者速度较慢且阶乘容易溢出。编程的输出大多相类，此处并不过多添加截图。

C、C++、C#、Java 语言之间的语法也大多相类，因此这里也不会将每一种算法都在这些语言中各实现一遍。要在这些语言的版本间修改，实际上只需注意一些简单的语法和函数名称的改变，如 C 的 int yh[M][M] 应改写为 Java 的 int[][] yh = new int[M][M]、C# 的 int[,] yh=new int[M,M]；C printf 应使用 Java 的 System.out.print、C# 的 Console.Write 、C++ 中更智能的 cout 来替换。

 

——————————————————————————————

杨辉三角，是二项式系数在三角形中的一种几何排列。在欧洲，这个表叫做帕斯卡三角形。帕斯卡（1623----1662）是在1654年发现这一规律的，比杨辉要迟393年，比贾宪迟600年。杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。
杨辉三角的特点：
 （与上图中的n不同，这里第一行定义为n=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个数等于第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个斐波那契数。
……
第一种实现形式：
【二维数组实现杨辉三角 输出10行】

//缺了一个部分自己想

#include <iostream>
#include <iomanip>
using namespace std;

/*杨辉三角最终显示效果是一个等腰三角形，两个最外边都是1
  杨辉三角的根本在于，每个数等于它上方两数之和
*/
int main(){
  const int n=11;//变量n在此处起到了限制输出行数的作用，可优化成用户输入
  //使第一列和对角线元素的值为1
  for (i=1;i<n;i++){            //前两行全为1，拿出来单独处理
     a[i][i]=1;//使最右侧边全为1
     a[i][1]=1;//使最左侧边全为1
  }

  //从第三行开始处理
  for (i=3;i<n;i++)                //三行开始出现变化
    for (j=2;j<=i-1;j++) //j始终慢i一步
       a[i][j]=a[i-1][j-1]+a[i-1][j];//每个数等于它上方两数之和，如a32=a21+a22

  //输出数组各元素的值
  for (i=1;i<n;i++){            //从第一行开始
     for (j=1;j<=i;j++)            //利用j将每一行的数据全部输出
       cout<<setw(5)<<a[i][j]<<" ";    //在C++中，setw(int n)用来控制输出间隔，这里是指前元素末尾与后元素末尾之间有个5空格位
  }
  cout<<endl;
  return 0;
}

效果展示图

PS1：setw()函数的使用：
 C++函数std::setw的行为与在流上调用n作为参数的成员宽度一样，它作为操纵器插入/提取（在输入流或输出流上插入/提取）。
 它用于设置要在输出操作上使用的字段宽度。

特点：

setw（）是C ++中的库函数。
setw（）在#include <iomanip.>中声明
setw（）将设置字段宽度。
setw（）设置要用作 下一个插入操作的字段宽度的字符数 。

参考资料：
 【C4learn.com】C ++ setw（）：设置字段宽度
PS2：std是什么意思？
 在C++中，std其实就是standard标准的意思，std是一个类（输入输出标准），它包括了cin成员和cout成员，using name space std ;以后才能使用它的成员。
 例如std::cin就是标准输入，std::cout就是标准输出的意思。
 #include <iostream.>,它包含了一个类，在类的使用之前要预处理一下，using namespace std;就是这个功能，然后你就可以使用cin,cout这两个成员函数了，假设你不使用预处理（using namespace std;),就需要加上加上std::cin或者std::cout再去使用它的成员函数。

第二种实现形式：
【指针动态开辟空间，一维数组实现杨辉三角 输出任意行】
 该方法使用灵活，但是理解略显困难。
//缺了一个部分自己想

#include <iostream>
#include <iomanip>
using namespace std;

int* YangHuiData(int n); //n是杨辉三角形的行数 
void YangHuiShow(int *pData, int n);//在屏幕上打印杨辉三角形 
int main() {
    int n;
    cout << "请输入杨辉三角形的行数";
    cin >> n;
    //计算杨辉三角并保存到二维数组
    int *pData = YangHuiData(n);
    //在屏幕上打印等腰三角形的杨辉三角 
    //n是杨辉三角形的行数 
}
 
int* YangHuiData(int n) {
    int *a = new int[n*n]; ////用指针a指向new动态分配的长度为(n*n)*sizeof(int)的内存空间 

    //完成杨辉三角形的计算，没有显示的位置填0 
    int i, j;
    for (i = 0; i<n*n; i++) {
        a[i] = 0;            //填0操作        
    }
 
    a[0] = 1;
    a[n] = 1;
    a[n + 1] = 1;
 
    for (i = 2; i<n; i++) {
        a[i*n] = 1;
        a[i*n + i] = 1;
        for (j = 1; j<i; j++) {
            a[i*n + j] = a[(i - 1)*n + j - 1] + a[(i - 1)*n + j]; //通过a[i*n+j]来访问第(i*n+j)个数据,根据杨辉三角的特性求值
        }
    }
 
    return a;
}
void YangHuiShow(int *a, int n) {
    //根据数据a指向的二维数组在屏幕上打印 
    //杨辉三角形，每行前面填充合适的空格 
    //以显示成等腰三角形，左右对称 
    int i, j;
    for (i = 0; i<n; i++)
    {
        for (j = 0; j<n - i - 1; j++)
            cout << setw(3) << " ";//前导空格，为单个数据的一半宽度  
        for (j = 0; j <= i; j++)
            cout << setw(6) << a[i*n + j];
        cout << endl;
    }
}

——————————

代码有缺的部分自己想，运行的是正确代码！