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，童鞋們可以用其他語言實現，漢諾塔確實能幫助理解遞歸原理，遞歸在程序設計中的重要性不言而喻啦！