【经典算法题目】汉诺塔问题

汉诺塔问题

有A、B、C三个木桩，在木桩A上从下往上按大小顺序摞着n片圆盘。要求把圆盘从下往上按大小顺序重新摆放在木桩C上。并且规定，在小圆盘上不能放大圆盘，在三个木桩之间一次只能移动一个圆盘。

递归算法求解

def hanoi(n, p1, p2, p3):
    if n<1:
        print("Error")
    elif n==1:
        print("{}->{}".format(p1, p3))
    else:
        hanoi(n-1, p1, p3, p2) # 将 n-1 个圆盘从木桩p1移到木桩p2
        print("{}->{}".format(p1, p3)) # 将第 n 个圆盘从木桩p1移到木桩p3
        hanoi(n-1, p2, p1, p3) # 将 n-1 个圆盘从木桩p2移到木桩p3
if __name__=="__main__":
    hanoi(5, 'A', 'B', 'C')

移动次数递推公式:

C(1) = 1
C(n) = 2 * C(n-1) + 1 = 2^n - 1

所以该算法的时间复杂度为O(2^n).

汉诺塔问题变种

变种1

有A、B、C、D四个木桩，在木桩A上从下往上按大小顺序摞着n片圆盘。要求把圆盘从下往上按大小顺序重新摆放在木桩D上。并且规定，在小圆盘上不能放大圆盘，在四个木桩之间一次只能移动一个圆盘。

变种2

有A、B、C三个木桩，在木桩A上从下往上按大小顺序摞着n片圆盘，在木桩B上从下往上按大小顺序摞着m片圆盘,所有圆盘大小都不相同。要求把圆盘从下往上按大小顺序重新摆放在木桩C上。并且规定，在小圆盘上不能放大圆盘，在三个木桩之间一次只能移动一个圆盘。

变种3

有A、B、C三个木桩，在木桩A上从下往上按大小顺序摞着n片圆盘，在木桩B上从下往上按大小顺序摞着m片圆盘，在木桩C上从下往上按大小顺序摞着l片圆盘，所有圆盘大小都不相同。要求把圆盘从下往上按大小顺序重新摆放在木桩C上。并且规定，在小圆盘上不能放大圆盘，在三个木桩之间一次只能移动一个圆盘。