杨辉三角的快速求法

杨辉三角的快速求法

引用

CSDN

1.

https://blog.csdn.net/hz_zhangrl/article/details/139815474

一、杨辉三角形

杨辉三角形，又称贾宪三角形，帕斯卡三角形，是二项式系数在三角形中的一种几何排列，古称“开方作法本源图”。

杨辉三角的历史

北宋人贾宪约1050年首先使用“贾宪三角”进行高次开方运算。最早出现在《宋史·艺文志》中贾宪所著的《黄帝九章算法细草》九卷，书已无存，但其许多内容为100多年后的南宋数学家杨辉1261年撰写的《详解九章算法》之中，故又称为杨辉三角形。

图1 杨辉简介

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

在欧洲，帕斯卡在1654年发现这一规律，所以这个表又叫做帕斯卡三角形，但是帕斯卡的发现比杨辉要迟393年，比贾宪晚500年。

二、快速求解方法

如图2所示，如果序列(或数组)的第一个和最后一个元素为0，下一行的所有元素都查以用上一行对应的元素和上一行前一个元素和。先输出，再添0为求下一行作准备。

对Python列表a，a[-1]=a[n-1]，所以只需给列表尾部添加0元素即可。

图2 杨辉三角快速求解原理图

三、Python代码

这也许是最短的求杨辉三角的Python代码。

n = 15							                    # 生成杨辉三角的行数
Δ = [1]							                    # 初始化杨辉三角
for i in range(n):					                # 外循环
    print(' '.join(str(j) for j in Δ).center(60))	# 格式化输出，内循环
    Δ.append(0)				                        # 添加个0(Δ[-1]=0)，用于计算下一行
    Δ = [Δ[j]+Δ[j-1] for j in range(len(Δ))]		# 计算下一行，内循环  

四、执行结果