据结构（三）-- 用栈实现汉诺塔(python)

《数据结构C语言版》P55

算法思想：

  为了把n块盘从X塔座移到Z塔座借助Y塔座，就必须把n-1块盘从X塔座移到Y塔座借助Z塔座，再将X塔座上剩余的第n块盘移到Z塔座上，最后将Y塔座上的n-1块盘移到Z塔座上借助X塔座，结束程序。
  而在实现将n-1块盘从X塔座移到Y塔座借助Z塔座时，又必须先实现将n-2块盘从X塔座上移到Y塔座上，借助Z塔座，再将第n-2块盘从X塔座上移到Z塔座上，最后将Y塔座上的n-2块盘移到Z塔座上借助X塔座。
  从而形成递归。

python3

class Solution:
    def hanoi(self, n, x, y, z):  # 将n块盘从x盘移到z盘借助y盘
        if n == 1:
            self.move(x, 1, z)
        else:
            self.hanoi(n-1, x, z, y)  # 将n-1块盘从x盘移到y盘借助z盘
            self.move(x, n, z)  # 将第n块盘从z移到z
            self.hanoi(n-1, y, x, z)  # 将n-1块盘从y盘移到z盘借助x盘

    def move(self, a, n, b):  # 将第n号盘从a移到b
        a.pop()
        b.append(n)
        print('将第' + str(n) + "块圆盘从" + a[0] + '移到' + b[0])

if __name__ == '__main__':
    x = ['a']
    r = [i for i in range(1, 4)]
    x.extend(r)
    y = ['b']
    z = ['c']
    t = Solution()
    t.hanoi(3, x, y, z)