最近在“廖雪峰的官方網(wǎng)站”學(xué)習(xí)Python，遇到漢諾塔遞歸問題百思不得其解，先是百度了漢諾塔原理，然后查看了別人的寫的文章，通過整理匯總，希望能夠幫助其他人理解。

漢諾塔原理：（來源于百度百科）

漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。

邏輯推理

圖片:

推理邏輯：

首先有3個(gè)柱子(A B C) ,A柱子有N個(gè)圓盤，假如我們圓盤按照L1-Ln表示，要將A中圓盤移動(dòng)到其他柱子中去，假如為C，需要幾步。規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。

假如n=1

則圓盤為L(zhǎng)1 ,只需將圓盤從A→C,共一步

假如n=2

則圓盤為L(zhǎng)1,L2 ,則需要將先將L1從A→C,然后將L2從A→B,最后將L1從C→B,共3步。

假如n=3

則圓盤為L(zhǎng)1,L2 ,L3, 先將L1從A→C,然后將L2從A→B,L1從C→B,然后將L3從A→C,然后將L1從B→A,將L2從B→C,再將A→C。

...

簡(jiǎn)單思考：

上面只是一個(gè)移動(dòng)過程，如果沒有圖片很難理解 ，我們可以簡(jiǎn)單思考下，將所有盤片看成L1-L(n-1)和Ln兩個(gè)部分。如果有n個(gè)盤片需要移動(dòng)，則：

# 子目標(biāo)1：將前n-1個(gè)盤子從a移動(dòng)到b上

# 子目標(biāo)2：將最底下的最后一個(gè)盤子從a移動(dòng)到c上

# 子目標(biāo)3：將b上的n-1個(gè)盤子移動(dòng)到c上

實(shí)際上n-1個(gè)圓盤本身又是一個(gè)遞歸，一直可以分解成n=1為止。

下面貼上代碼

# 漢諾塔思想筆記

# 認(rèn)識(shí)漢諾塔的目標(biāo)：把A柱子上的N個(gè)盤子移動(dòng)到C柱子

# 遞歸的思想就是把這個(gè)目標(biāo)分解成三個(gè)子目標(biāo)

# 子目標(biāo)1：將前n-1個(gè)盤子從a移動(dòng)到b上

# 子目標(biāo)2：將最底下的最后一個(gè)盤子從a移動(dòng)到c上

# 子目標(biāo)3：將b上的n-1個(gè)盤子移動(dòng)到c上

# 然后每個(gè)子目標(biāo)又是一次獨(dú)立的漢諾塔游戲，也就可以繼續(xù)分解目標(biāo)直到N為1

def move(n, a, b, c):

if n == 1:

print(a, '-->', c)

else:

move(n-1, a, c, b)# 子目標(biāo)1

move(1, a, b, c)# 子目標(biāo)2

move(n-1, b, a, c)# 子目標(biāo)3

n = input('enter the number:')

move(int(n), 'A', 'B', 'C')

? 代碼解釋如下“

/**

我把3個(gè)盤子的漢諾塔全部通過代碼演示，按縮進(jìn)原則，每一個(gè)縮進(jìn)即進(jìn)一個(gè)遞歸函數(shù)，每打印一次即中止當(dāng)前遞歸,也就是每個(gè)print

說明:

1.n = 3, n = 2, n = 1是每次執(zhí)行if(n == 1)的結(jié)果，這里就不寫判斷了，相信童鞋們也能看懂，也就是n不等與1時(shí)就減1進(jìn)入遞歸

2.請(qǐng)注意a,b,c柱每次進(jìn)入函數(shù)的順序，不要被形參帶錯(cuò)路了，看準(zhǔn)每次函數(shù)參數(shù)的實(shí)參

**/

move(3, "a", "b", "c")

n=3:

//開始從a上移動(dòng)n-1即2個(gè)盤子通過c移動(dòng)到b,以騰出c供a最后一個(gè)盤子移動(dòng)

move(2, "a","c","b")

n=2:

//開始進(jìn)行n=2的一個(gè)遞歸，把當(dāng)前a('a')柱上的n-1個(gè)盤子通過c('b'）移動(dòng)到b('c')

move(1, "a", "b", "c")

n=1:

//n=2的第一個(gè)遞歸完成,打印結(jié)果，執(zhí)行當(dāng)前子函數(shù)剩余代碼

print("a", "->", "c")

move(1, "a", "c", "b")

n=1:

print("a", "->", "b")

move(1, "c", "a", "b")

n=1:

print("c", "->", "b")

//到這里完成了a柱上面的n-1即是2個(gè)盤子的移動(dòng)

//開始把a(bǔ)柱上最后一個(gè)盤子移動(dòng)到c柱上

move(1, "a", "b", "c")

n=1:

print("a", "->", "c")

//到這里完成移動(dòng)a柱上的最后一個(gè)盤子到c柱上

move(2, "b", "a", "c")

n=2:

//開始進(jìn)行n=2的第二個(gè)遞歸,即把當(dāng)前b('b')的盤子(n-1個(gè))通過a('a')移動(dòng)到c('c')上

move(1, "b", "c", "a")

n=1:

//n=2 的第二個(gè)遞歸完成，打印結(jié)果并執(zhí)行當(dāng)前子函數(shù)的剩余代碼

print("b", "->", "a")

move(1, "b", "a", "c")

n=1:

print("b", "->", "c")

move(1, "a", "b", "c")

n=1:

print("a", "->", "c")

//到這里把b上的盤子通過a移動(dòng)到c,

//整個(gè)代碼執(zhí)行完畢,漢諾塔移動(dòng)完成

好吧，我承認(rèn)我不會(huì)用這個(gè)博客，好多格式都沒有表現(xiàn)出來。

? ?你們可以參考以下幾個(gè)地方：

? ?百度百科-漢諾塔原理：https://baike.baidu.com/item/%E6%B1%89%E8%AF%BA%E5%A1%94/3468295?fr=aladdin

? ?廖雪峰的官方網(wǎng)站-Python：https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/001431756044276a15558a759ec43de8e30eb0ed169fb11000

? Python技術(shù)交流：http://bbs.fishc.com/thread-61965-1-1.html?

? ?遞歸經(jīng)典案例分析：http://blog.csdn.net/hikobe8/article/details/50479669

總結(jié)

以上是生活随笔為你收集整理的汉诺塔python代码解释_Python-汉诺塔原理分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。