Python学习笔记(二)—第四天,递归函数(阶乘和汉诺塔游戏)

时间:2022-05-18 02:59:58

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

1、阶乘函数

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

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

 1 def factorial(x):
 2     for x in range(1,x+1):
 3         if x == 1:
 4             y = 1
 5         else:
 6             y = y * x
 7     return y
 8 
 9 temp = int(input ('Please enter a number :'))
10 print(temp)
11 if temp == 0:
12     print ('0没有阶乘哦!')
13 else:
14     temp1 = factorial(temp)
15     print( "%d 的阶乘为 %d" %(temp,temp1))

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

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

 1 def factorial(n):
 2     if n == 1:
 3         return 1
 4     else:
 5         return n * factorial(n-1)      #即n! = n * (n-1)!
 6         
 7 number = int(input ('请输入一个正整数'))
 8 print (number)
 9 result = factorial(number)
10 print("%d 的阶乘是:%d" % (number,result))

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

2、汉诺塔游戏

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

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

Python学习笔记(二)—第四天,递归函数(阶乘和汉诺塔游戏)

思考这个问题的时候,我将其想成了三步走:把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

得到这个结果,正确。