python汉诺塔递归算法

‘壹’ 【python】汉诺塔递归

系统自带的演示代码，可以研究一下

#!/usr/bin/envpython3
"""turtle-example-suite:
tdemo_minimal_hanoi.py
Aminimal'TowersofHanoi'animation:

lefttotherightpeg.
Animhoquiteelegantandconcise
,which
isderivedfromthebuilt-intypelist.
Discsareturtleswithshape"square",but
()
---------------------------------------
ToexitpressSTOPbutton
---------------------------------------
"""
fromturtleimport*
classDisc(Turtle):
def__init__(self,n):
Turtle.__init__(self,shape="square",visible=False)
self.pu()
self.shapesize(1.5,n*1.5,2)#square-->rectangle
self.fillcolor(n/6.,0,1-n/6.)
self.st()
classTower(list):
"Hanoitower,asubclassofbuilt-intypelist"
def__init__(self,x):
"createanemptytower.xisx-positionofpeg"
self.x=x
defpush(self,d):
d.setx(self.x)
d.sety(-150+34*len(self))
self.append(d)
defpop(self):
d=list.pop(self)
d.sety(150)
returnd
defhanoi(n,from_,with_,to_):
ifn>0:
hanoi(n-1,from_,to_,with_)
to_.push(from_.pop())
hanoi(n-1,with_,from_,to_)
defplay():
onkey(None,"space")
clear()
try:
hanoi(6,t1,t2,t3)
write("pressSTOPbuttontoexit",
align="center",font=("Courier",16,"bold"))
exceptTerminator:
pass#turtledemouserpressedSTOP
defmain():
globalt1,t2,t3
ht();penup();goto(0,-225)#writerturtle
t1=Tower(-250)
t2=Tower(0)
t3=Tower(250)
#maketowerof6discs
foriinrange(6,0,-1):
t1.push(Disc(i))
#preparespartanicuserinterface;-)
write("pressspacebartostartgame",
align="center",font=("Courier",16,"bold"))
onkey(play,"space")
listen()
return"EVENTLOOP"
if__name__=="__main__":
msg=main()
print(msg)
mainloop()

‘贰’ 汉诺塔递归算法是什么

汉诺塔是经典递归问题：

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘。

游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

如果A只有一个（A->C）。

如果A有两个（A->B）,(A->C),(B->C)。

如果A有三个（A->C）,(A->B),(C->B),(A->C),(B->A),(B->C),(A->C)。

如果更多，那么将会爆炸式增长。

递归：就是函数自己调用自己。 子问题须与原始问题为同样的事，或者更为简单；递归通常可以简单的处理子问题，但是不一定是最好的。

其实递归在某些场景的效率是很低下的。尤其是斐波那契.从图你就可以发现一个简单的操作有多次重复。因为它的递归调用俩个自己。那么它的递归的膨胀率是指数级别的，重复了大量相同计算。

起源：

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

‘叁’ python解决汉诺塔问题

解汉诺塔最简单的做法就是递归:

类似如何将大象装进冰箱：1）将冰箱门打开；2）把大大象放进去；3）把冰箱门关上……

我们将所有的盘都在同一个杆上从大到小排列视为【完美状态】，那么，目标就是将最大盘片为n的完美状态从a杆移到b杆，套用装大象的思路，这个问题同样是三步：

1）把n-1的完美状态移到另一个杆上；

2）把n移到目标杆上；

3）把n-1的完美状态移到目标杆上。

如下：

‘肆’ 汉诺塔递归算法是什么

如下：

1、汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

2、抽象为数学问题：从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数。

算法分析（递归算法）：

实现这个算法可以简单分为三个步骤：把n-1个盘子由A 移到 B；把第n个盘子由 A移到 C；把n-1个盘子由B 移到 C。从这里入手，在加上上面数学问题解法的分析，我们不难发现，移到的步数必定为奇数步。

1、中间的一步是把最大的一个盘子由A移到C上去。

2、中间一步之上可以看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上。

3、中间一步之下可以看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上。

‘伍’ 关于python递归函数实现汉诺塔

仔细看一下 5-7行调用 move 时候的参数顺序， 不是你说的那样没有变：

#5 的含义是将 A 上的前 n-1 个移动到 B
#6 : 将 A 最后一个移动到 C
#7: 将 B 上的 n-1 (即#5 从 A 移动过来的 n-1) 个移动到 C

‘陆’ 汉诺塔的算法

算法介绍：当盘子的个数为n时，移动的次数应等于2^n–1。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放A、B、C；

若n为奇数，按顺时针方向依次摆放A、C、B。

所以结果非常简单，就是按照移动规则向一个方向移动金片：如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C

汉诺塔问题也是程序设计中的经典递归问题。

(6)python汉诺塔递归算法扩展阅读

由来：

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。

不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，

假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下：18446744073709551615秒。

这表明移完这些金片需要5845.54亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。

‘柒’ python请用递归算法编程解决汉诺塔问题 在线等

这是Python3系统自带的一个例子，估计就是这个意思，本来他是6个盘子，按照你要求改成4个了。递归算法没问题，描述也非常详细 ；）

#!/usr/bin/envpython3
fromturtleimport*
classDisc(Turtle):
def__init__(self,n):
Turtle.__init__(self,shape="square",visible=False)
self.pu()
self.shapesize(1.5,n*1.5,2)#square-->rectangle
self.fillcolor(n/6.,0,1-n/6.)
self.st()
classTower(list):
"Hanoitower,asubclassofbuilt-intypelist"
def__init__(self,x):
"createanemptytower.xisx-positionofpeg"
self.x=x
defpush(self,d):
d.setx(self.x)
d.sety(-150+34*len(self))
self.append(d)
defpop(self):
d=list.pop(self)
d.sety(150)
returnd
defhanoi(n,from_,with_,to_):
ifn>0:
hanoi(n-1,from_,to_,with_)
to_.push(from_.pop())
hanoi(n-1,with_,from_,to_)
defplay():
onkey(None,"space")
clear()
try:
hanoi(6,t1,t2,t3)
write("pressSTOPbuttontoexit",
align="center",font=("Courier",16,"bold"))
exceptTerminator:
pass#turtledemouserpressedSTOP
defmain():
globalt1,t2,t3
ht();penup();goto(0,-225)#writerturtle
t1=Tower(-250)
t2=Tower(0)
t3=Tower(250)
#maketowerof6discs
foriinrange(4,0,-1):
t1.push(Disc(i))
#preparespartanicuserinterface;-)
write("pressspacebartostartgame",
align="center",font=("Courier",16,"bold"))
onkey(play,"space")
listen()
return"EVENTLOOP"
if__name__=="__main__":
msg=main()
print(msg)
mainloop()

‘捌’ python利用递归解决汉诺塔问题，求大神解释一下代码

这是一个典型的递归程序
当只有一层的时候，直接把x放到z上结束
当大于1层的时候，先把x和z放到y上，然后继续递归
把y放到x上，然后放到z上，结束处理

‘玖’ 哪位大佬有python汉诺塔的教程

学到递归的时候有个汉诺塔的练习，汉诺塔应该是学习计算机递归算法的经典入门案例了，所以本人觉得可以写篇博客来表达一下自己的见解。这markdown编辑器还不怎么会用，可能写的有点格式有点丑啦，各位看官多多见谅.
网上找了一张汉诺塔的图片，汉诺塔就是利用用中间的柱子把最左边的柱子上的圆盘依次从大到小叠上去，说白了就是c要跟原来的a一样

童鞋们理解了汉诺塔的递归算法原理后，可以写个程序来试试，这里只是学到Python的递归所以用了Python，童鞋们可以用其他语言实现，汉诺塔确实能帮助理解递归原理，递归在程序设计中的重要性不言而喻啦！