22 - 杨辉三角形

鱼C-小师妹

上一讲最后给大家总结了一个“递归三定律”，本讲我们继续加深对递归的理解～

在线讲解：



杨辉三角形，又称帕斯卡三角形、贾宪三角形、海亚姆三角形、巴斯卡三角形，是二项式系数的一种写法，形似三角形。

在中国首现于南宋杨辉的《详解九章算法》得名，书中杨辉说明是引自贾宪的《释锁算书》，故又名贾宪三角形。



该图有很强的实用性，可以帮助古人将（a+b）的 n 次方快而准确地展开成多项式。

比如说，（a+b）的1 次方它等于a+b，展开还是两项，系数都是 1，相当于杨辉三角的第二行数字1、1。

（a+b）的 2 次方等于 a²+2ab+b²，展开变成三项，系数分别是 1、2、1，而杨辉三角第三行数字也是 1、2、1 。

（a+b）的 3 次方等于a³+3a²b+3b²a+b³，展开变成四项，系数分别是 1、3、3、1，是杨辉三角第四行数字

以此类推，（a+b）的 6 次方展开是多少？

我们查杨辉三角，看第七行数字：1、6、15、20、15、6、1。总共七个数字，说明展开后的多项式共有七项。

系数分别是 1、6、15、20、15、6、1，写出来是：

a⁶+6a⁵b+15a⁴b²+20a³b³+15a²b⁴+6ab⁵+b⁶

前 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 位时，在整数右侧补空格：



好啦，这就舒服很多了对吧～

源码： P22.py.zip (825 Bytes, 下载次数: 9, 售价: 7 鱼币)

2022-2-8 21:11 上传

点击文件名下载附件

其实到目前这种输出格式还是有不足，如果数位太长还是会乱！

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()

本节课就到这里，自己快去动手打印一下吧，下课！

超过光速c

围观学习！！

罗巴乔

学习学习

hornwong