一、問題描述及算法步驟

漢諾塔問題的大意是有三根柱子a, b, c，現(xiàn)在a柱有N個盤子從下往上尺寸遞減排列，要求：
1. 將a上的盤子移動到c柱上;
2. 每次移動一個盤子;
3. 柱子上的盤子始終必須是大的在下面

image.png

漢諾塔問題的經(jīng)典實現(xiàn)算法步驟如下：
1.把 前N-1個盤子移動到過渡柱b
2.把最低下的盤子從起始柱a移到終點柱c
3.然后把b柱的N-1個盤子也移到終點柱c
實現(xiàn)過程是一個遞歸的過程，遞歸公式為下：
g(n) = 2g(n-1) + 1
g(1) = 1

（實際上可以通過解該遞歸方程得出 g(n) = 2^n - 1）

二、編程實現(xiàn)

python語言實現(xiàn)代碼：

def Hanoi(num, a, b, c):
    global count
    if num == 1:
        count += 1
        print "第%d步：盤%d 從%s柱-->柱%s" % (count, num, a, c)
    else:
        Hanoi(num - 1, a, c, b)  # 以c作為過渡柱，將前N-1個盤子從a移到b
        # Hanoi(1,a,b,c)
        count += 1
        print "第%d步：盤%d 從%s柱-->柱%s" % (count, num, a, c)  # 將最后一個盤子從a柱移到c柱
        Hanoi(num - 1, b, a, c)  # 將b柱上的N-1個盤子移到c柱


if __name__ == '__main__':
    count = 0
    n = input("請輸入盤子的數(shù)目\n")
    Hanoi(n, 'A', 'B', 'C')
    print "總步數(shù)為%d" % count

注：另外，漢諾塔問題也可以使用堆棧進行非遞歸實現(xiàn)。