Python算法 汉诺塔

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/84997039

算法描述：

汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着N片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

算法分析：

将 N 个圆盘从左边柱子移动到右边柱子：

• [递归的]将 N-1 个圆盘从左边柱子移动到中间柱子。
• 将最大的圆盘从左边柱子移动到右边柱子。
• [递归的]将 N-1 个圆盘从中间柱子移动到右边柱子

算法实现：

def hanoit(height, left='left', middle='middle', right='right'):
    if height:
        hanoit(height - 1, left, middle, right)
        print(left, '-->', right)
        hanoit(height - 1, middle, right, left)