问题描述:
有三个立柱A、B、C。A柱上穿有大小不等的圆盘N个,较大的圆盘在下,较小的圆盘在上。要求把A柱上的圆盘全部移到C柱(终点)上,保持大盘在下、小盘在上的规律(可借助B柱)。每次移动只能把一个柱子最上面的圆盘移到另一个柱子的最上面。请输出移动过程。
解答
这是动态规划问题中的一种,用递归来实现较为简单方便。
所以说一共就三步
把 前n-1 号盘子从A柱经过C柱移动到B柱
把n号盘子从A柱移动到C柱
然后把n-1个盘子从B柱经过A柱移动到C柱
代码:
1 def hanoi(n, a, b, c): 2 if n == 1: 3 print(print("moving from %s to %s" % (a, c))) 4 else: 5 hanoi(n - 1, a, c, b) 6 hanoi(1, a, b, c) 7 hanoi(n - 1, b, a, c) 8 9 10 hanoi(3, ‘A‘, ‘B‘, ‘C‘)