用python实现汉诺塔、斐波拉契数列以及杨辉三角

第一部分：汉诺塔

首先介绍一下汉诺塔，历史故事就由读者通过链接去了解。汉诺塔就是指有ABC三个柱子，A柱子上有若干个大小不一的盘子，盘子从下到上依次减小，现在要将A柱子上的盘子通过B柱子（过渡柱子）转移到C柱子上，要求大盘子不能放在小盘子之上。

汉诺塔的移动可以用递归函数非常简单地实现。

利用整体法解题思路：

首先不管A柱子中有几个盘子，要将A柱子中的所有盘子都放到C柱子上，可以先将A柱子最上面的（n-1）个盘子整体放在B柱子上，再将A柱子的最下面的一个盘子放在C柱子上，再将之前B柱子上的（n-1）个盘子整体放在C柱子上，这样就ok了！

def Hanoi(n,a,b,c):
    if n == 1:
    #当n等于1时单独处理
        print(a,'--->',c)
    else:
        Hanoi(n-1,a,c,b)
        #将A柱子上的除了最下面的盘子，其余盘子均放到B柱子上
        Hanoi(1,a,b,c)
        #将A柱子上留的最大的盘子转移到C柱子上
        Hanoi(n-1,b,a,c)
        #再将之前B柱子上的n-1个盘子移动到C柱子上
Hanoi(4,'A','B','C')
#调用函数

输出结果为:

A ---> B
A ---> C
B ---> C
A ---> B
C ---> A
C ---> B
A ---> B
A ---> C
B ---> C
B ---> A
C ---> A
B ---> C
A ---> B
A ---> C
B ---> C

这个一定要注意整体法思想

第二部分：斐波拉契数列

同样的，先介绍一下斐波拉契数列，简而言之就，就是除第一个和第二个数外，任意一个数都可由前两个数相加得到，即：1, 1, 2, 3, 5, 8, 13, 21, 34, ...

我在这里说两种实现方法，其实实质是十分相似，一种是用函数实现，另一种是用生成器实现，（后面介绍生成器与函数的区别）。

1.函数进行实现，代码如下：

def Fibonacci(max):
    n = 0
    a = 0
    b = 1
    while n < max:
        print(b)
        a, b = b, a + b
        #这一步肯定是对有些人来说是难以理解的
        #实质上 a,b = b, a + b 就相当于:
        #t = (b, a + b)   t是一个tuple
        #a = t[0]
        #b = t[1]
        n += 1
    return

Fibonacci(20)

输出结果为:

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765

2.用生成器来实现，代码如下：

def Fibonacci(max):
    n = 0
    a = 0
    b = 1
    while n < max:
        yield b
        a, b = b, a + b
        n += 1
    return

for n in Fibonacci(20):
    print(n)

输出结果依旧如上。

之前用函数实现的斐波拉契数列实质上是定义了斐波拉契数列的推算规则，可以从第一个元素开始，推算出后续的任意元素，这种逻辑非常类似于生成器（generator），只需将函数的print（b）改为yield b，后面再用循环进行输出就成了generator。如果一个函数定义中包含yield关键字，那么这个函数就不再是一个普通函数，而是一个generator。

也许有人会问，既然可以用函数实现，为什么还要大费周章的使用生成器呢？

这是因为通过列表生成式，我们可以直接创建一个列表。但是，受到内存限制，列表容量肯定是有限的。而且，如果创建一个包含100万个元素的列表，不仅占用很大的存储空间，而且如果我们仅仅需要访问前面几个元素，那后面绝大多数元素占用的空间都白白浪费了。所以，如果将列表元素可以按照某种算法推算出来，那我们就可以在循环的过程中不断推算出后续的元素，这样就不必创建完整的list，从而节省大量的空间。因此在Python中就产生了这种一边循环一边计算的机制，称为生成器generator。

函数与生成器的最主要的区别是执行流程不同，函数是顺序执行，遇到return语句或者最后一条语句就返回，而变成generator后，每次调用next（）的时候执行，遇到yield语句返回，再次执行时从上次返回的yield语句出继续执行。

generator保存的是算法，每次调用next(g)，就计算出g的下一个元素的值，直到计算到最后一个元素，没有更多的元素时，抛出StopIteration的错误。当然，上面这种不断调用next(g)实在是太变态了，我们最常使用的方法是使用for循环，因为generator也是可迭代对象

 第三部分：杨辉三角

一样，也先介绍一下杨辉三角，每一行第一个数和最后一个数都是1，每一行的中间的数字等于上一行距离最近数字之和。把每一行看做一个list，试写一个generator，不断输出下一行的list。

由于输出格式的问题，最后本人的输出结果呈直角三角形，并非像上图中的等腰三角形。

代码如下：

def Trianngle(n):
    #打印第一行和第二行
    print([1])
    #单独处理第一行
    list1 = [1,1]
    #定义一个列表来存储第二行的值
    print(list1)
    #打印第三行及以后
    for i in range(2,n):
    #打印第三行，但是第三行的数字是通过第二行数字相加得到的，因此范围是从第二行到第n行，
    #不需要取到第n行，只需要取到(n-1)行就好了，因为第n行的值是通过第(n-1)行计算出来的。
        list2 = []
        #定义一个空列表来存储数字
        for i in range(0,len(list1)-1):
        #每一行的两边的数字都是由上面一行的数字相加得到的，因此只需要取第0个到第len(list1)-1的数
        #为什么这块取到的最大值是len(list1)-1,如果是len(list1),到下一行list1[i+1]时会下标越界
            list2.append(list1[i] + list1[i+1])
            #将每一行的上一行的下标为i的数字和下标为(i+1)的数字相加并加入到列表list2中
        list1 = [1] + list2 + [1]
        #因为每一行的第一个和最后一个数字都是1，因此将list2中的数字和两个1拼接起来
        yield (list1)
#遍历输出
for x in Trianngle(10):
    print(x)

输出结果如下：

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]