递归实现 汉诺谈
汉诺塔问题
http://www.nowcoder.com/questionTerminal/7d6cab7d435048c4b05251bf44e9f185
把汉诺塔 问题是将 问题细分为 小问题。
要把所有 左边的盘子 移动到 最右边
首先 需要把 非底盘的盘子 移动到 中间柱子
然后 把地盘的盘子 放到 右边的柱子
最后再把 中间柱子 非底盘的盘子 移动到 右边的柱子
class Solution:
def getSolution(self , n ):
# 返回 结果
self.ans = []
# 开始 汉诺塔
self.hanoi(n, 'left', 'mid', 'right')
return self.ans
def hanoi(self, n, left, mid, right):
if n == 1:
# 只剩 一个 盘子， 需要 从 左边 移动到 右边 即可
self.move(left, right)
else:
# 把 左边的 移动 到 中间
self.hanoi(n - 1, left, right, mid)
# 左边的 移动到 右边
self.move(left, right)
# 中间的 移动到 右边
self.hanoi(n - 1, mid, left, right)
def move(self, left, right):
# 打印 移动操作
self.ans.append('move from ' + left + ' to ' + right)
