练习3：汉诺塔问题

题目要求

分析

1. f(n)要实现：
   把全部n块从L移至R
   步骤：
   （1）把前n-1块从L移至M
   （2）把第n块从L移至R
   （3）把前n-1块从M移至R
2. 递归的来源：实现f(n)中的步骤（2）和（3）与f(n-1)密切相关
3. 把f(n)的实现过程用递归形式写出：
   （1）g(f(n-1))
   （2）把第n块从L移至R
   （3）h(f(n-1))
   问题的关键在于g与h如何实现

代码1——官方的

def f(n, start, end, by):
    if n == 1:
        print("Move from " + start + " to " + end)
    else:
        f(n-1, start, by, end)
        f(1, start, end, by)
        f(n-1, by, end, start)


f(3, "L", "R", "M")

Move from L to R
Move from L to M
Move from R to M
Move from L to R
Move from M to L
Move from M to R
Move from L to R

代码2——我的

def f(n):
    options = []
    if n == 1:
        options.append(["L", "R"])
        return options
    else:

        #把前n-1块从L移至M

        options.append(["L", "R"])

        #把前n-1块从M移至R

        return options

代码3——对官方的改写1

def f(n, start="L", end="R", by="M"):
    options = []
    if n == 1:
        options.append([start, end])
        return options
    else:

        for _ in f(n-1, start, by, end):
            options.append(_)

        options.append([start, end])

        for _ in f(n-1, by, end, start):
            options.append(_)

        return options


for _ in f(3):
    print(_)

['L', 'R']
['L', 'M']
['R', 'M']
['L', 'R']
['M', 'L']
['M', 'R']
['L', 'R']

代码4——对官方的改写2

def f(n, start="L", end="R", by="M"):
    options = []
    if n == 1:
        options.append([start, end])
        return options
    else:
        options.extend(f(n-1, start, by, end))
        options.append([start, end])
        options.extend(f(n-1, by, end, start))

        return options


for i, _ in enumerate(f(5), 1):
    print(i, _)

思考

1. f(n-1)、g(f(n-1))、h(f(n-1))这三者的关系可以通过对f的功能做扩展来更好的体现，对f(n)添加更多参数，使它们三者在更广义的层面上有更清晰的联系

Tips

1. 用for in解压，用append添加
2. 解压过程中可以使用enumerate函数来输出序号，并且可以指定起始序号
3. append() 追加单个元素到List的尾部，只接受一个参数，参数可以是任何数据类型，被追加的元素在List中保持着原结构类型。此元素如果是一个list，那么这个list将作为一个整体进行追加
4. extend() 将一个列表中每个元素分别添加到另一个列表中，只接受一个参数。实际上不仅可以接受list，它接受的参数是一个可迭代对象即可，将该可迭代对象解压后分别添加至原list中。