一次只能搬1个盘子
2.大盘子不能叠在小盘子上
神的旨意说一旦这些盘子完成迁移，寺庙将会坍塌，世界将会毁灭！
若要搬完这64个盘子：需要移动的次数为 2^{64} - 1 = 18446744073709551615次
如果每秒钟搬一次盘子，需要584942417355年（即五千亿年！）
分析：
根据递归三定律： 最小问题规模（基本结束条件）、如何减小规模、调用自身。
假设有三个柱子，x，y，z ；有5个盘子，穿在 x 柱子上，需要挪到 z 柱子：
若能把上面的四个盘子挪到 y 柱子上，问题就简单了。
把最下面的最大号盘子直接从 x 柱子挪到 z柱子即可
再用同样的办法把 y柱子上的四个盘子，挪到 z 柱子，就完成了。
即 把 n-1 个盘子从x经过z挪到 y ， 把 n 盘子从 x 到 z ，剩下的 n-1 从 y 经过x到 z 。
直到剩下1个盘子，直接挪到 z 。
def moveTower(height, fromPole, withPole, toPole):
if height >= 1:
当盘子数量大于1时
# 将 n-1 个盘子从 x（fromPOle） 移动到 y(withPole), 经过 z(toPole)
moveTower(height - 1, fromPole, toPole, withPole)
# 打印盘子移动过程
moveDisk(height, fromPole, toPole)
# 将 n - 1 个盘子从 y（withPole）移动到 z（toPole） ，经过 x（fromPole）
moveTower(height - 1, withPole, fromPole, toPole)
def moveDisk(disk, fromPole, toPole):
print(f'移动{disk}号盘子，从{fromPole}到{toPole}。')
moveTower(3, 'x', 'y', 'z')
移动1号盘子，从x到z。
# 移动2号盘子，从x到y。
# 移动1号盘子，从z到y。
# 移动3号盘子，从x到z。
# 移动1号盘子，从y到x。
# 移动2号盘子，从y到z。
# 移动1号盘子，从x到z。
"""Leetcode:汉诺塔问题，用栈将所有盘子从第一根柱子移动到最后一根。"""
class Solution:
def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
n = len(A)
self.move(n, A, B, C)
def move(self, n, A, B, C):
if n == 1:
C.append(A.pop())
else:
self.move(n - 1, A, C, B)
C.append(A.pop())
self.move(n - 1, B, A, C)
发表于 2022-5-25 19:40
|
发表于 2022-5-25 19:41
