汉诺塔问题

汉诺塔问题_牛客题霸_牛客网

问题简述

请实现一个函数打印汉诺塔问题的最优移动轨迹。
输入：
    2
返回值：
    ["move from left to mid","move from left to right","move from mid to right"]

思路

• 定义 move(i, left, right, mid) 表示把 i 个圆盘从 left 移动到 right，通过 mid；

• 移动过程：

  • move(i - 1, left, mid, right)：先把上面 i-1 个圆盘从 left 移动到 mid，通过 right；

  • f'move from {left} to {right}'：把最底下的圆盘从 left 移动到 right

  • move(i - 1, mid, right, left)：再把这 i-1 个圆盘从 mid 移动到 right，通过 left

Python

class Solution:
    def getSolution(self, n: int) -> List[str]:
        ret = []

        def move(i, left, right, mid):
            """把 i 个圆盘从 left 移动到 right，通过 mid"""
            if i == 0: return

            move(i - 1, left, mid, right)  # 先把上面 i-1 个圆盘从 left 移动到 mid，通过 right
            ret.append(f'move from {left} to {right}')  # 把最底下的圆盘从 left 移动到 right
            move(i - 1, mid, right, left)  # 再把这 i-1 个圆盘从 mid 移动到 right，通过 left

        move(n, 'left', 'right', 'mid')
        return ret