Python学习笔记（二）—第四天，递归函数（阶乘和汉诺塔游戏）

今天主要学习了递归函数，已经尝试了一些小例子，这里拿阶乘和汉诺塔来记录下。

1、阶乘函数

阶乘很简单，即n! = 1x2x3x...xn。

先用了常用的迭代函数来写阶乘，代码如下，很简单的函数

def factorial(x):
    for x in range(1,x+1):
        if x == 1:
            y = 1
        else:
            y = y * x
    return y

temp = int(input ('Please enter a number :'))
print(temp)
if temp == 0:
    print ('0没有阶乘哦！')
else:
    temp1 = factorial(temp)
    print( "%d 的阶乘为 %d" %(temp,temp1))

逻辑很简单，不断地给变量y进行迭代。因为是在学习递归，所以又用递归的方法，重新来写一下。

原理就是，n! = n x (n-1)!

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)      #即n! = n * (n-1)!
        
number = int(input ('请输入一个正整数'))
print (number)
result = factorial(number)
print("%d 的阶乘是：%d" % (number,result))

用递归来写的话，就感觉这个函数清晰明了多了。

2、汉诺塔游戏

背景：法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

简单说，就是有三根柱子（a,b,c）,a柱子上有n个盘子，从上到下的盘子是从小到大，要求，把这n个盘子从a移动到c上，切移动的中间不允许大的盘子放在小的盘子上面。如图：

思考这个问题的时候，我将其想成了三步走：把a轴上的n个盘子看做两部分来理解，最下面最大的1个盘子，以及其他的（n-1）个盘子.

1、如果将其当做两部分，那么第一步要做的，就是讲上面的（n-1）个盘子，移动到b轴上；

2、第二步，然后将a轴上剩下的另外一部分即最后那1个盘子，从a轴移动到c轴；

3、第三步，再将b上的那一部分（n-1）个盘子，从b移动到c。

 

那么，依据上面的三步走的考虑，写出的代码如下：

def hanoi(n,a,b,c):    
    if n == 1:                    # 如果只有一个盘，那么就是把这一个盘，从a轴（起始轴）移动到c轴（目标轴）。
        print (a ,'-->', c)
        
    else:                        #如果有n个盘子    
        hanoi((n-1),a,c,b)        #那么第一步，就是先把（n-1）个盘子从a轴移动到b轴，以c轴为缓冲。此时，a轴为起始轴，b轴为目标轴，c轴为缓冲轴。
        hanoi(1,a,b,c)            #第二步，移动了（n-1）个盘子后，a轴还剩下1个，那么就是把最后这个从a轴移动到c轴。即hanoi(1,a,b,c)，a -->c。
        hanoi((n-1),b,a,c)        #第三步，将b轴上的（n-1）个盘子，从b轴移动到c轴，此时b为起始轴，a为缓冲轴，c为目标轴，即hanoi((n-1),b,a,c)
        
n = int(input('请输入汉诺塔层数'))
hanoi(n,'A','B','C')

如此，当用户输入数字后，就可以得到想要的汉诺塔移动。

编译一下试试

请输入汉诺塔层数3
A --> C
A --> B
C --> B
A --> C
B --> A
B --> C
A --> C

得到这个结果，正确。