汉诺塔问题

问题描述:

有三个立柱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)

 

汉诺塔问题

上一篇:机械臂学习(十三)


下一篇:1140 Look-and-say Sequence (20 分)