本篇文章为大家展示了Python中怎么利用递归算法实现汉诺塔,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。
1. 找出Fibonacci数列中,下标为 n 的数(下标从0计数)
Fibonacci数列的形式是这样的:0,1,1,2,3,5,8,13……
① 使用while循环,python2代码如下:
def fib(n): a,b=0,1 count=0 while count<n: a,b=b,a+b count=count+1 print a
运行结果如下:
>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
② 使用递归(递归必须要有边界条件),python2代码如下:
def fib(n): if n==0 or n==1:#递归的边界条件 return n else: return fib(n-1)+fib(n-2)
运行结果如下:
>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
递归是最能表现计算思维的算法之一,我们以f(4)为例,看一下递归的执行过程:
同一程序,使用递归虽然程序简洁,但递归的执行效率要比循环低,系统的资源消耗比循环大。因为递归是一层一层地往里面调用,结束后又一层一层地返回,所以递归的执行效率并不高。那为什么还要使用递归呢?因为有一些问题,我们找不到非常明显的循环方案,但容易找到明显的递归方案。比如说著名的汉诺塔问题。
2. 汉诺塔
下图是一个简化版的汉诺塔游戏,只有4个盘子:
汉诺塔游戏规则如下:
python2代码如下:
def hanoi(a,b,c,n): if n==1:#递归结束条件 print a,'->',c else: hanoi(a,c,b,n-1) print a,'->',c hanoi(b,a,c,n-1)
运行结果:
>>> hanoi('A','B','C',1)
A -> C
>>> hanoi('A','B','C',2)
A -> B
A -> C
B -> C
>>> hanoi('A','B','C',3)
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
上述内容就是Python中怎么利用递归算法实现汉诺塔,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。