汉诺塔解体思路

前言

前几天在廖雪峰老师的博客上学习Python时，在递归函数中廖老师出了这么一个问题：

汉诺塔的移动可以用递归函数非常简单地实现。

请编写move(n, a, b, c)函数，它接收参数n，表示3个柱子A、B、C中第1个柱子A的盘子数量，然后打印出把所有盘子从A借助B移动到C的方法，例如：def move(n, a, b, c):

move(3, 'A', 'B', 'C')

期待输出:

• A --> C

• A --> B

• C --> B

• A --> C

• B --> A

• B --> C

• A --> C

本文不讨论这个问题的移动次数，只讨论这个函数的写法，以及思考过程。

汉诺塔：

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

这里感谢评论区的网友给了我解题思路

• 假设：A柱子只有两个盘，上面为n-1个小盘，下面为1个大盘；B：0盘；C：0盘

• 移动步骤①：A柱的n-1个盘，借助C柱的缓冲，移动到B柱，move(n-1,a,c,b)

• 移动步骤②：A柱的1个盘，借助B柱的缓冲，移动到C柱，move(1,a,b,c)

• 移动步骤③：B柱的n-1个盘，借助A柱的缓冲，移动到C柱，move(n-1,b,a,c)”

      if n == 1:
        print(a, '-->', c)
      else:
        move(n-1,a,c,b)
        move(1,a,b,c)
        move(n-1,b,a,c)