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