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

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

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

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上，切移动的中间不允许大的盘子放在小的盘子上面。如图：

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

得到这个结果，正确。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

• LeetCode 1006：笨阶乘
• LeetCode每日一题: 阶乘后的零（No.172）
• LeetCode - 172 - 阶乘后的零（factorial-trailing-zeroes）
• Python 拓展之特殊函数（lambda 函数，map 函数，filter 函数，reduce 函数）
• Python 函数调用&定义函数&函数参数
• python基础教程：函数，函数，函数，重要的事说三遍

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。