首页 > 试题广场 >

汉诺塔问题

[编程题]汉诺塔问题

热度指数：12031 时间限制：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"]

算法知识视频讲解

牛客313925129号

发表于 2021-07-16 11:26:31

精华题解方法一递归汉诺塔问题的解决方案可以分为3步：1、把n-1个盘子从left 借助 right，搬到mid柱子上；2、把剩下最大的那一个盘子从left搬到right柱子上；3、把n-1个盘子从mid 借助 left，搬到right柱子上。示意图如下：至于如何把n-1个盘子搬到另一个柱子上，同样参照上面展开全文

王清楚

发表于 2021-04-10 18:20:02

把n个盘子从Left 借助 Mid，移动到Right柱子上可以分为以下三步：把n-1个盘子从Left 借助 Right，移动到Mid柱子上把剩下最大的那一个盘子从Left移动到 Right柱子上把n-1个盘子从Mid 借助 Left，移动到,Right柱子上我们定义函数 void Han 展开全文

牛客169612650号

发表于 2022-04-11 13:02:19

把n个盘子从left借助mid，转移到right分为三步：将前n-1个盘子从left借助right,转移到mid 将第n个盘子从legft直接移到right 将前n个盘子从mid借助left移到right class Solution: def getSolution(self , 展开全文

landf31

发表于 2022-04-10 14:33:48

import java.util.*; public class Solution { static ArrayList<String> list=new ArrayList<String>();//存放结果 public ArrayList<Stri 展开全文

牛客338107602号

发表于 2022-07-05 12:47:34

总结：1.汉诺塔问题是经典的递归问题，移动n个盘从left借助mid移动到right,可以分解为先将n-1个盘从left借助right移动到mid,再把第n个盘从left直接移动到right，之后再将mid处的n-1个盘从mid借助left移动到right.其中移动n-1个盘的过程又可以划分为类似的展开全文

贪睡的乌龟在攒经验

发表于 2022-09-07 15:46:48

//递归的方法 class Solution { public: void hanno(int n,vector<string> &ans,string from,string to,string other ){ 展开全文

AimerAimer

发表于 2021-10-10 15:41:43

题意：有一个由底至上为从大到小放置的 n 个圆盘，和三个柱子（分别为左/中/右即left/mid/right），开始时所有圆盘都放在左边的柱子上，展开全文

OfferCall！

发表于 2021-03-18 09:13:44

汉诺塔问题汉诺（Hanoi）塔问题：古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用展开全文

摸鱼学大师

发表于 2021-07-13 20:26:17

思路：从题中给出的有效信息：汉诺塔，不需要记录次数，但是需要移动的塔的名字对于汉诺塔，无论在哪座塔上，小盘必须要在大盘上面，因此可以逆向思维从结果考虑，left塔最下面的大盘，必定是left塔仅剩它，而right塔上面又什么东西都没有时才可以移动，则其余n-1个盘都在mid塔上，且顺序为从小展开全文