《数据结构C语言版》P55
算法思想:
为了把n块盘从X塔座移到Z塔座借助Y塔座,就必须把n-1块盘从X塔座移到Y塔座借助Z塔座,再将X塔座上剩余的第n块盘移到Z塔座上,最后将Y塔座上的n-1块盘移到Z塔座上借助X塔座,结束程序。
而在实现将n-1块盘从X塔座移到Y塔座借助Z塔座时,又必须先实现将n-2块盘从X塔座上移到Y塔座上,借助Z塔座,再将第n-2块盘从X塔座上移到Z塔座上,最后将Y塔座上的n-2块盘移到Z塔座上借助X塔座。
从而形成递归。
python3
class Solution:
def hanoi(self, n, x, y, z): # 将n块盘从x盘移到z盘借助y盘
if n == 1:
self.move(x, 1, z)
else:
self.hanoi(n-1, x, z, y) # 将n-1块盘从x盘移到y盘借助z盘
self.move(x, n, z) # 将第n块盘从z移到z
self.hanoi(n-1, y, x, z) # 将n-1块盘从y盘移到z盘借助x盘
def move(self, a, n, b): # 将第n号盘从a移到b
a.pop()
b.append(n)
print('将第' + str(n) + "块圆盘从" + a[0] + '移到' + b[0])
if __name__ == '__main__':
x = ['a']
r = [i for i in range(1, 4)]
x.extend(r)
y = ['b']
z = ['c']
t = Solution()
t.hanoi(3, x, y, z)