杨辉三角 http://baike.baidu.com/view/7804.htm 定义如下:
- 1
- / \
- 1 1
- / \ / \
- 1 2 1
- / \ / \ / \
- 1 3 3 1
- / \ / \ / \ / \
- 1 4 6 4 1
- / \ / \ / \ / \ / \
- 1 5 10 10 5 1
把每一行看做一个 list, 试写一个 generator, 不断输出下一行的 list.
该题目考查生成器的应用. 一般的思路是, 首先在每一行输出一个 1, 随后通过循环, 位置 i(从 2 开始)的数是上一行 i 与 i-1 位置的数之和, 当 i 与上一行数字个数相同时, 循环终止, 最后再添加进一个 1, 形成新的一行.
基于这个基本思路, 将 python 的生成器运用到里面, 有两种常见的写法:
一种写法如下:
- def triangles():# 杨辉三角的一种生成方法
- l = [1]
- while True :
- yield l
- for i in range ( 1,len (l) ) :
- l [i] = h [i] + h [i-1]
- l.append (1)
- h = l[:]
另外一种写法如下, 运用了 list 的生成式:
- def triangles():
- l = [1]
- while True :
- yield l
- l = [1] + [ l[i] + l[i+1] for i in range ( len (l) - 1)] + [1]
可以看到, 以上两种写法都是相当简洁的. 一开始这两个代码看不太懂, 比如说为啥第一种写法里一开始 h 里面没有数, 却也能够正常执行? 主要是对于生成器的 yield 机制不明白, 以及对于 range 的用法不是特别清楚. 以下就这两点分别解释.
首先, 当函数中出现了 yield 之后, 该函数就不再被视为函数, 而视为一个生成器. 此时, 整个函数被使用的语句流程会发生改变, 一般的函数都是调用的时候从函数入口进, 发现 return 或函数执行完毕后返回, 而生成器函数则是每次调用函数执行, 执行到 yield 返回, 下次再调用函数的时候从上次 yield 返回处继续执行.
其次, range 的用法中是, 如果是 [range(x,x) 其中 x 是常量] 的形式, range 依然返回空. 故在上述代码的 for 循环中, 由于在第一次试图循环的时候, 后面的 range 要么是 range(1,1) 要么是 range(0), 故都会成功避开 i 或者 h 没有实际值的循环, 执行接下来的部分. 当第二次试图循环开始时, i 和 h 内的内容都已经满足条件了, 所以就能正常运行了.
还有一种我看到的最简单的写法:
- def triangles():
- L = [1]
- while True:
- yield L
- L= [(L + [0])[i] + ([0] + L)[i] for i in range(len(L)+1)]
这一种写法直接去掉了第二种写法里每次 L 两边额外插入的[1], 使其变为了一个完整的一个 list 生成式, 可以说是相当精妙.
那么, 这种写法为什么也可以呢? 我们再来分析一下杨辉三角的性质, 这样, 为了直观理解, 我们先利用上面的代码, 举一个运行中的过程例子.
比如, L 此时为[1,1](杨辉三角第二行), 现在需要求第三行. 根据第五行的生成式, 将按照以下步骤进行计算:
1.L 尾部加 0, 得到[1,1,0], 我们称之为 tempL1
2.L 首部加 0, 得到[0,1,1], 我们称之为 tempL2
3. 现在, 根据之后的 for 循环, L 最终要被赋值成由 tempL1 与 tempL2 对应相同位置数字之和的列表替代, 经过计算, 这个新的 L 应该为[1,2,1]. 居然确实是杨辉三角的第三行!
相信聪明的观众已经明白了, 这个最简单的写法是利用了杨辉三角本身的对称性质, 让同一行错开一位竖式相加, 得到的就是下一行的结果. 同时, 利用 python 里面本身就极为方便的列表扩展写法和列表生成式, 才有了第三种如此简洁的写法~
来源: https://www.cnblogs.com/sbhyc/p/9230794.html