漢諾塔：漢諾塔（又稱河內(nèi)塔）問(wèn)題是源于印度一個(gè)古老傳說(shuō)的益智玩具巍膘。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤狐史。大梵天命令婆羅門把圓盤從下面開(kāi)始按大小順序重新擺放在另一根柱子上痒给。并且規(guī)定，在小圓盤上不能放大圓盤骏全，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤
目標(biāo)：將A上的圓盤移動(dòng)到C
- 思路
從圓盤較少然后依次增加找規(guī)律：數(shù)字代表圓盤大小和位置
<1> 當(dāng)A只有一個(gè)圓盤時(shí)(1)苍柏，不用想直接A -> C
<2> 當(dāng)A只有兩個(gè)圓盤時(shí)(1/2)，要借助B完成姜贡。先 A -> B,然后就可以把最大一個(gè)從A -> C
先不著急B -> C. 分析一下此時(shí)C有最大的圓盤试吁，那么任何圓盤都可以直接放到C上，此時(shí)C可以認(rèn)為是空的鲁豪。B上有一個(gè)圓盤潘悼，如果把B看做A，A看做B爬橡，就回到了<1>那種情況
<3> 當(dāng)A只有三個(gè)圓盤時(shí)(1/2/3)治唤，先不要著急移動(dòng)。想要把A上的圓盤全部移動(dòng)到C上糙申，必定需要把A最底部的最大的圓盤移動(dòng)到C.將1/2兩個(gè)圓盤看做一個(gè)整體宾添，則可以直接按照<2>操作了，超級(jí)偽代碼如下：
A(1/2) -> B
A(3) -> C
B(1/2) -> C
執(zhí)行<2>的步驟
- 代碼實(shí)現(xiàn)
# n代表圓盤的數(shù)量柜裸，a,b,c代表柱子
def move(n, a, b, c):
if n == 1:
print("從 %s 移動(dòng)一個(gè)圓盤到 %s" % (a, c))
else:
# 將圓盤數(shù)-1(除去最大的圓盤)借助c移動(dòng)到b
move(n-1, a, c, b)
# 將a上最大圓盤一定到c
print("從 %s 移動(dòng)一個(gè)圓盤到 %s" % (a, c))
# 將a看做b缕陕，b看做a，重復(fù)執(zhí)行
move(n-1, b, a, c)
move(3, "A", "B", "c")
