265 杨辉三角

杨辉三角

1. 杨辉三角的介绍
2. 杨辉三角的递归算法分析
3. 杨辉三角的代码实现

杨辉三角的介绍

杨辉三角，是二项式系数在三角形中的一种几何排列。杨辉三角是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。

杨辉三角的算法分析

上图标示了杨辉三角的前7行，如何求解杨辉三角的第n行数字是那些呢? 对于找规律的数学问题，如果能够找出递归的表达式是十分容易求解的。

定义函数:令f(n,m)来表示第n行的第m个数字，通过观察可以很容易得到f(n,m)=f(n-1,m-1)+f(n-1,m),即第n行的第m个数字应该为上一行的第m-1个数字和第m个数字之和。

边界分析:每行的左右两端则为边界条件,即f(n,1)=1,f(n,n)=1 (第n行的左右两端都是1)。

杨辉三角的代码实现

n=int(input()) #n>=1
def f(n,m):
	if n==m or m==1:#边界条件
		return 1
	else:#递归问题的拆解
		return f(n-1,m-1)+f(n-1,m)
for i in range(1,n+1):#打印第n行
	print(f(n,i),end=' ')

小结

• 根据杨辉三角的递归算法，理解递归算法的三要素
• 掌握杨辉三角的递归算法

习题

1. 画出上述问题中函数f(7,4)的递归执行图
2. 在不使用递归的情况下，请对第n行的杨辉三角进行求解，对比递归了说一说递归的优点