#0723周一#迭代、生成器、高阶函数

一、递归函数与汉诺塔问题

问题：有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，如何移动？

命名规则：从下往上进行编号，如A柱从下往上第5个盘子——A5th；A柱从下往上第5个盘子到最顶端盘子——A5

1. 最简版：n = 2
分为三步：

初始	移动	目标
A2th	→	B
A1th	→	C
B1th	→	C

2. 升级版：n = 3
分为“3”步：

初始	移动	目标
A2	→	B
A1th	→	C
B2	→	C

在这种情况下，将A2th、A3th视为一个整体，A柱上的盘子由两部分组成，A1th和（A2th+A3th），就变成了最简版的情况。
当然，这里说是三步是错误的，因为第一步中，将（A2th+A3th）搬到B是不允许的，但是，这一步也是最简版的情况，只是初始棒与目标棒发生了变化。

也就是说，不管初始状态A柱上有多少个盘子，都可以分为两个整体，A1th和A2，只需要三大步，至于第一步和第三步中A2是怎么移动的，不需要管。
好，现在再来看第一大步，A2是如何移动到B上去的，就可以把A2这个整体再分为1+（剩下的），执行三步操作。
这就是递归的过程。

以上三步分别对应代码中的

move(n-1, a, c ,b)
move(1, a, b, c)
move(n-1, b, a, c)

完整代码

def move(n, a, b, c):
    if n == 1:
        print('move', a, '-->', c)
    else:
        move(n-1, a, c ,b)
        move(1, a, b, c)
        move(n-1, b, a, c)

move(5, 'A', 'B', 'C')

参考资料：

1. python中的汉诺塔递归算法的具体运算过程是怎样的？ - 孙饭的回答 - 知乎
   https://www.zhihu.com/question/37152936/answer/509161984
2. 如何理解汉诺塔的递归？ - 酱紫君的回答 - 知乎
   https://www.zhihu.com/question/24385418/answer/282940567

二、生成器（Generator）与杨辉三角

1. 为什么要使用生成器？

假设有列表L = [1, 2, 3, 4,..., 1000000000]，而在实际使用时只需要里面的几个元素，比如第10个、第30000个、第5000000个，但是在使用之前L必须全部生成，造成了很大的内存浪费。
生成器就是用来解决这个问题，生成器的原理是用哪个临时计算哪个，不产生额外的内存消耗，当然计算需要时间，这是一种用时间换空间的方式，但是是值得的，因为运算时间可以忽略不计。

2. 如何创建生成器？

对比列表的创建与生成器的创建：

L = [x * x for x in range(10)]
G = (x * x for x in range(10))

可见，区别一个是[]，一个是()。但是两者在使用时不同，L可以直接使用下标进行调用，而生成器创建的G则不可以，如：

>>> l = [x * x for x in range(10)]
>>> print(l[2])
4
>>> g = (x * x for x in range(10))
>>> print(g[2])
Traceback (most recent call last):
  File "<input>", line 1, in <module>
TypeError: 'generator' object is not subscriptable

生成器的元素通常用for循环取出，如：

g = (x * x for x in range(10))
for n in g:
    print(n)

如何取出特定位置元素？→ 使用next()循环计算下一个值

def gen(n):
    n = n + 1
    g = (x * x for x in range(n))
    while n > 0:
        value = next(g)
        n = n - 1
    return value

k = gen(3)
print(k)

--> 9

3. 杨辉三角

好难，看懂再说吧。。。

三、高阶函数

1. map()

map()函数接收两个参数，一个是函数，一个是Iterable，map将传入的函数依次作用到序列的每个元素，并把结果作为新的Iterator返回。
因此函数是对单个元素进行处理的。下面这个例子中不要在def里写for循环了

例：利用map()函数，把用户输入的不规范的英文名字，变为首字母大写，其他小写的规范名字。输入：['adam', 'LISA', 'barT']，输出：['Adam', 'Lisa', 'Bart']

def normalize(name):
    return name[0:1].upper() + name[1:].lower()

L2 = list(map(normalize, L1))

最后由于map()返回的是Iterator，因此要利用list将其转换为列表。

2. reduce()

reduce把一个函数作用在一个序列[x1, x2, x3, ...]上，这个函数必须接收两个参数，reduce把结果继续和序列的下一个元素做累积计算。
同样是函数对序列的元素施加运算，同时操作两个元素。
这里再说一下，执行完map(func, <序列>)后，返回的是Iterator（可迭代对象），这是一种序列，而非单个的元素。
因此，这样的形式是可以理解的：reduce(fn, map(char2num, s))

例:利用map和reduce编写一个str2float函数，把字符串'123.456'转换成浮点数123.456：

from functools import reduce

def str2float(s):
    left, right = s.split(".")

    def fn1(left):
        return reduce(lambda x, y: x * 10 + y, map(int, left))

    def fn2(right):
        def sub_fn2(x, y):
            return x * 0.1 + y
        return 0.1 * reduce(sub_fn2, map(int, right[::-1]))

    return fn1(left) + fn2(right)

print('str2float(\'123.456\') =', str2float('123.456'))
if abs(str2float('123.456') - 123.456) < 0.00001:
    print('测试成功!')
else:
    print('测试失败!')

注意:

1. lambda函数：fn1和fn2的功能是一致的，采用lambda函数可以使代码清晰简洁。
2. 整数部分与小数部分的处理方式具有明显的不同，因此必然需要采用不同的函数，编程时不要纠结。
3. right[::-1]，举例说明：

>>> a=[1, 2, 3, 4, 5]
>>> print(a[2::-1]) # 取从下标为2的元素翻转读取
[ 3 2 1 ]
>>> print(a[::-1]) # 从最后一个元素翻转读取
[5, 4, 3, 2, 1]