首页 > 试题广场 >

汉诺塔问题

[编程题]汉诺塔问题

热度指数：13014 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

我们有由底至上为从大到小放置的 n 个圆盘，和三个柱子（分别为左/中/右即left/mid/right），开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，要求一次只能移动一个圆盘，而且大的圆盘不可以放到小的上面。

请实现一个函数打印最优移动轨迹。

给定一个 `int n` ，表示有 n 个圆盘。请返回一个 `string` 数组，其中的元素依次为每次移动的描述。描述格式为： `move from [left/mid/right] to [left/mid/right]`。

数据范围： $1\le n \le 16$

要求：时间复杂度 $O(3^n)$ ，空间复杂度 $O(3^n)$

示例1

输入

输出

["move from left to mid","move from left to right","move from mid to right"]

算法知识视频讲解

Python3

九天揽月a

# 简简单单十几行
class Solution:
    def getSolution(self , n: int) -> List[str]:
        # write code here
        def hannuota(n, start: str, end: str):
            solution = []
            all = ['left', 'mid', 'right']
            all.remove(start)
            all.remove(end)
            midd = all[0]
            if n == 1:
                solution.append(f"move from {start} to {end}")
                return solution
            else:
                solution.extend(hannuota(n-1, start, midd))
                solution.append(f"move from {start} to {end}")
                solution.extend(hannuota(n-1, midd, end))
                return solution

        return hannuota(n, 'left', 'right')

发表于 2024-08-22 11:37:38 回复(0)

Python3

求offer牛

class Solution:
    def getSolution(self , n: int) -> List[str]:
        # write code here
        
        def move(n,left,mid,right,res):
            if n==0:
                return 
            move(n-1,left,right,mid,res)
            res.append('move from '+left+' to '+right)
            move(n-1,mid,left,right,res)
            return res
        
        res = []
        return move(n,'left','mid','right',res)

发表于 2022-11-29 14:52:13 回复(0)