22 - 杨辉三角形
本帖最后由 鱼C-小师妹 于 2022-2-21 18:31 编辑上一讲最后给大家总结了一个“递归三定律”，本讲我们继续加深对递归的理解～
在线讲解：
https://www.bilibili.com/video/BV1HT4y1K7DY?p=25
杨辉三角形，又称帕斯卡三角形、贾宪三角形、海亚姆三角形、巴斯卡三角形，是二项式系数的一种写法，形似三角形。
在中国首现于南宋杨辉的《详解九章算法》得名，书中杨辉说明是引自贾宪的《释锁算书》，故又名贾宪三角形。
该图有很强的实用性，可以帮助古人将（a+b）的 n 次方快而准确地展开成多项式。
比如说，（a+b）的1 次方它等于a+b，展开还是两项，系数都是 1，相当于杨辉三角的第二行数字1、1。
（a+b）的 2 次方等于 a2+2ab+b2，展开变成三项，系数分别是 1、2、1，而杨辉三角第三行数字也是 1、2、1 。
（a+b）的 3 次方等于a3+3a2b+3b2a+b3，展开变成四项，系数分别是 1、3、3、1，是杨辉三角第四行数字
以此类推，（a+b）的 6 次方展开是多少？
我们查杨辉三角，看第七行数字：1、6、15、20、15、6、1。总共七个数字，说明展开后的多项式共有七项。
系数分别是 1、6、15、20、15、6、1，写出来是：
a6+6a5b+15a4b2+20a3b3+15a2b4+6ab5+b6
前 9 行写出来如下：
１
１ １
１ ２ １
１ ３ ３ １
１ ４ ６ ４ １
１ ５ 10 10 ５ １
１ ６ 15 20 15 ６ １
１ ７ 21 35 35 21 ７ １
１ ８ 28 56 70 56 28 ８ １
通过上面的分析杨辉三角形中的数是 (x+y) 的 N 次方幂展开式各项的系数。
杨辉三角是程序设计中具有代表性的题目！
求解的方法很多，即然开头说到递归，那就先来用递归法打印出杨辉三角形。
开始前，一起再朗读下“递归三定律”：
[*]必须有一个结束条件
[*]必须能改变状态向结束条件推进
[*]必须调用自身
读的很好！
接下来从杨辉三角形的特点出发，可以总结出：
[*]第 x 行有 x 个值（设起始行为第1行）
[*]对于第 x 行的第 y（y＞＝3）个值，当 y=1 或 y=x 时，其值为1；当 y!=1 且 y!=x 时，其值为第 x-1 行的第 y-1 个值与第 x-1 行的第 y 个值之和
这两点就很符合，上节课总结的递归三定律：
结束条件就是 x 和 y 为 1，每一轮值的调用即是改变状态向结束条件推进，也是调用自身～
我们将这些特点提炼成数学公式，则位于杨辉三角第 x 行第 y 列的值为：
我们先把公示翻译成代码：
def c(x, y):
if y == 1 or y == x:
return 1
else:
z = c(x-1, y-1) + c(x-1, y)
return z
函数都写出来了，核心部分就搞定了。
接下来通过 input() 来获取用户输入的行数，然后一行一行遍历调用函数就可以了。
这里就遇到另外一个难点，三角的打印。
手写很容易，自己看距离就好，但是机器没办法吖，需要我们告诉它们哪里需要加空格～
来观察下上面三角的特点。
前面说过了，print() 默认会换行，我们通过设置 end=" " 来取消换行，并在末尾加空格。
将上面所说的过程写成代码：
for i in range(1, n+1):
for j in range(0, n-i+1):
print(" ", end=" ")
for j in range(1, i+1):
print(f"{c(i, j)}", end=" ")
print()
好了，运行看下结果：
这里格式还是有些诡异，我们可以用传统的 %d 格式化对象为十进制操作。
使用后，在需要输出的长字符串中占位置。输出字符串时，可以依据变量的值，自动更新字符串的内容。
修改最后一个 print：
print("%3d"%c(i, j), end=" ")
%3d意思是打印结果为 3 位整数，当整数的位数不够 3 位时，在整数右侧补空格：
好啦，这就舒服很多了对吧～
源码：
其实到目前这种输出格式还是有不足，如果数位太长还是会乱！
def c(x, y):
if y == 1 or y == x:
return 1
else:
z = c(x-1, y-1) + c(x-1, y)
return z
n = int(input("请输入需要打印的杨辉三角行数："))
for i in range(1, n+1):
for j in range((n-i)//2):
print("\t", end='')
for j in range(1,i+1):
# 要形成“隔行错开”的效果，所以我们在偶数行加4个空格
if i % 2 == 1:
print(" ", end='')
# 为何要使用TAB而非空格，大家可以将下面的end='\t'改成对应的空格数即可知晓
print(f"{c(i,j)}", end='\t')
print()
本节课就到这里，自己快去动手打印一下吧，下课！ 围观学习！！ 学习学习 {:5_95:}
页:
[1]