首页 > 试题广场 >

汉诺塔问题

[编程题]汉诺塔问题
  • 热度指数：12475 时间限制：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

输入

2

输出

["move from left to mid","move from left to right","move from mid to right"]
算法知识视频讲解
添加回答
啥头像 啥
发表于 2015-08-13 11:37:10 回复(0)
Java
JustYoung头像 JustYoung 
import java.util.*;

public class Solution {
    
    public void move(int n, ArrayList<String> list, String a, String b, String c) {
        if (n == 1) {
            list.add(String.format("move from %s to %s", a, b));
        } else {
            move(n - 1, list, a, c, b);
            move(1, list, a, b, c);
            move(n - 1, list, c, b, a);
        }
    }
    
    public ArrayList<String> getSolution(int n) {
        // write code here
        ArrayList<String> list = new ArrayList<>();
        move(n, list, "left", "right", "mid");
        return list;
    }
}

发表于 2016-09-06 13:53:27 回复(1)
程序猿灰灰头像 程序猿灰灰
import java.util.*;

public class Solution{
public static void main(String []args){
ArrayList<String> list=getSolution(3);
for(String s:list){
System.out.println(s);
}
}
    public static ArrayList<String> getSolution(int n) {
        // write code here
        ArrayList<String> list=new ArrayList<String>();
        Stack stack=new Stack();
        Disk disk=new Disk(n,"left","middle","right");
       
        stack.push(disk);
        Disk popDisk=null;
        while((popDisk=stack.pop())!=null){

            if(popDisk.status==1)
            {
            list.add("move from "+popDisk.left+" to "+popDisk.right);
           
            }
            else
            {
           stack.push(new Disk(popDisk.status-1,popDisk.middle,popDisk.left,popDisk.right));
           stack.push(new Disk(1,popDisk.left,popDisk.middle,popDisk.right));
           stack.push(new Disk(popDisk.status-1,popDisk.left,popDisk.right,popDisk.middle));
            }
        }
        return list;
    }
}

class Disk{
    String left;
    String middle;
    String right;
    int    status;

public Disk(int status,String left,String middle,String right){
        this.status=status;
        this.left=left;
        this.middle=middle;
        this.right=right;
    }
}

class Stack{
    Disk disks[]=new Disk[1000];
    int  top=-1;  
    
    public void push(Disk d)
    {
    top++;
        disks[top]=d;
    }
    public Disk pop()
    { 
   
        if(isEmpty()==true)
            return null;
       
        Disk disk= disks[top];
        top--;
        return disk;
            
    }
    
    public boolean isEmpty()
    {
     return top==-1;
            
    }
    
    
}
发表于 2015-07-23 14:12:30 回复(0)
JacobGo！头像 JacobGo！
递归求解
假设有from柱子，mid柱子和to柱子，都在from的圆盘上完全移动到to，最优过程为：
1.1~i-1的圆盘从from移动到mid；
2.单独的圆盘从from移动到to；
3.把圆盘1~i-1从mid移动到to。如果圆盘只有一个，直接把这个圆盘从from移动到to即可。 


import java.util.*;

public class Solution {
    ArrayList<String> res=null;
    public ArrayList<String> getSolution(int n) {
        if(n<=0)
            return null;
        res=new ArrayList<String>();
        func(n,"left","mid","right");
        
        return res;
    }
    /*
     * 把n个盘子从from移动到to
     */
    private void func(int n, String from, String mid, String to) {
        if(n==1)
            res.add("move from "+from+" to "+to);
        else{
            func(n-1,from,to,mid);
            func(1,from,mid,to);
            func(n-1,mid,from,to);
        }
            
        
    }
}

编辑于 2017-12-16 10:33:25 回复(1)
Java
不知Andy头像 不知Andy 
import java.util.*;

public class Solution {
    private String[] pos = {"left", "mid", "right"};
    public ArrayList<String> getSolution(int n) {      
        return getSolution(n, 0, 2);
    }
    public ArrayList<String> getSolution(int n, int from, int to) {       
        if(n==0) return new ArrayList<String>();
        ArrayList<String> list = getSolution(n-1, from, 3-from-to);
        list.add("move from "+pos[from]+" to "+pos[to]);
        list.addAll(getSolution(n-1, 3-from-to, to));
        return list;
    }
}
先把三个柱子编码0，1，2。
假设我们从柱子x向柱子y移动n个盘，由于大的不能放小的上面，所以移动最下面一个的时候前面n-1个一定按顺序排在第三个柱子（编码为3-x-y）上，将最后一个从x移到y，再把3-x-y上的全移动到y。递归得到答案。

发表于 2016-09-06 14:01:37 回复(3)
C/C++
nbgao头像 nbgao 
class Solution {
public:
    vector<string> result;
    void Move(int n, string a, string b, string c)
    {
        if(n==1)
        {
            string s = "move from " + a + " to " + b;             result.push_back(s);             }else{
            Move(n-1, a, c, b);
            Move(1, a, b, c);
            Move(n-1, c, b, a);         }     }
    vector<string> getSolution(int n) {
        Move(n, "left", "right", "mid");
        return result;
    }
};

发表于 2017-10-28 00:33:08 回复(0)
super1Angle头像 super1Angle 





import java.util.ArrayList;

public class Test {
	public static ArrayList<String> getSolution(int n) {
		ArrayList<String> list = new ArrayList<String>();
		list = recurse(n, 0, 2);
		return list;
	}
	public static ArrayList<String> recurse(int n, int from, int to) {
		ArrayList<String> list = new ArrayList<String>();
		//如果只有一个圆盘
		if(n == 1) {
			if(from == 0 && to == 1) {
				list.add("move left to mid");
			} else if(from == 0 && to == 2) {
				list.add("move left to right");
			} else if(from == 1 && to == 0) {
				list.add("move mid to left");
			} else if(from == 1 && to == 2) {
				list.add("move mid to right");
			} else if(from == 2 && to == 0) {
				list.add("move right to left");
			} else if(from == 2 && to == 1) {
				list.add("move right to mid");
			}
		} else {
			if(from == 0 && to == 1) {
				//先将n-1个圆盘从左边搬到右边
				list.addAll(recurse(n - 1, 0, 2));
				//再将最底层的圆盘从左边搬到中间
				list.add("move left to mid");
				//最后将n-1个圆盘从右边搬到中间
				list.addAll(recurse(n - 1, 2, 1));
			} else if(from == 0 && to == 2) {
				//先将n-1个圆盘从左边搬到中间
				list.addAll(recurse(n - 1, 0, 1));
				//再将最底层的圆盘从左边搬到右边
				list.add("move left to right");
				//最后将n-1个圆盘从中间搬到右边
				list.addAll(recurse(n - 1, 1, 2));
			} else if(from == 1 && to == 0) {
				//先将n-1个圆盘从中间搬到右边
				list.addAll(recurse(n - 1, 1, 2));
				//再将最底层的圆盘从中间搬到左边
				list.add("move mid to left");
				//最后将n-1个圆盘从右边搬到左边
				list.addAll(recurse(n - 1, 2, 0));
			} else if(from == 1 && to == 2) {
				//先将n-1个圆盘从中间搬到左边
				list.addAll(recurse(n - 1, 1, 0));
				//再将最底层的圆盘从中间搬到右边
				list.add("move mid to right");
				//最后将n-1个圆盘从左边搬到右边
				list.addAll(recurse(n - 1, 0, 2));
			} else if(from == 2 && to == 0) {
				//先将n-1个圆盘从右边搬到中间
				list.addAll(recurse(n - 1, 2, 1));
				//再将最底层的圆盘从右边搬到左边
				list.add("move right to left");
				//最后将n-1个圆盘从中间搬到左边
				list.addAll(recurse(n - 1, 1, 0));
			} else if(from == 2 && to == 1) {
				//先将n-1个圆盘从右边搬到左边
				list.addAll(recurse(n - 1, 2, 0));
				//再将最底层的圆盘从右边搬到中间
				list.add("move right to mid");
				//最后将n-1个圆盘从左边搬到中间
				list.addAll(recurse(n - 1, 0, 1));
			}
		}
		return list;
	}
	public static void main(String[] args) {
		ArrayList<String> list = getSolution(2);
		System.out.println(list);
	}
}


编辑于 2015-08-04 17:59:21 回复(1)
Python3
九天揽月a头像 九天揽月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)
Java
TernaryUp头像 TernaryUp 
import java.util.*;


public class Solution {
    static ArrayList<String> res = new ArrayList<>();

    public ArrayList<String> getSolution (int n) {
        hanluo(n, "left", "mid", "right");
        return res;
    }

    public void hanluo(int n, String left, String mid, String right) {
        if (n == 1) {
            res.add(String.format("move from %s to %s", left, right));
            return;
        }
        hanluo(n - 1, left, right, mid);
        hanluo(1, left, mid, right);
        hanluo(n - 1, mid, left, right);
    }
}

发表于 2024-06-01 13:07:42 回复(0)
唐氏综合征头像 唐氏综合征
1. 如果想要将第n个移动到最右边，就需要考虑先将 n-1个移动到 中间，然后将中间的先移动到右边，才能将第n个移动到右边，以此类推，因此 第n个盘子可以拆解为三步，每个过程都需要其他的一个盘子作为辅助,这是一个伪动态规划问题，它没有重复计算，每一步都是必要的. 

 public static ArrayList<String> getSolution(int n) {
        ArrayList<String> res = new ArrayList<>();
        move(n, "left", "mid", "right", res);
        return res;
    }

    // 递归函数，实现移动逻辑
    private static void move(int n, String from, String aux, String to,
                             ArrayList<String> res) {
        if (n == 1) {  // 基本情况：只有一个盘子，直接移动
            res.add("move from " + from + " to " + to);
        } else {
            move(n - 1, from, to, aux,
                 res);  // 将前 n-1 个盘子从 from 移动到 aux，to 作为辅助
            res.add("move from " + from + " to " +
                    to);  // 移动第 n 个盘子到目标柱子
            move(n - 1, aux, from, to,
                 res);  // 将 n-1 个盘子从 aux 移动到 to，from 作为辅助
        }
    }


发表于 2024-05-14 18:20:23 回复(0)
keepgoing20190801113019头像 keepgoing20190801113019 
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> getSolution(int n) {
        process(n);
        return res;
    }
    vector<string> res;
    string tab[4]={"","left","mid","right"};
    void process(int n, int left=1,int mid=2,int right=3) {
        if (n==1) {
            string tmp="move from " + tab[left] + " to " + tab[right];
            res.push_back(tmp);
        }
        else {
            process(n-1, left,right,mid);
            string tmp="move from " + tab[left] + " to " + tab[right];
            res.push_back(tmp);
            process(n-1, mid, left, right);
        }
    }
};

编辑于 2024-01-18 18:28:29 回复(0)
C++
牛客的琦琦同学头像 牛客的琦琦同学 
class Solution {
  public:
    void GetRet(vector<string>& ret, string src, string des) {
        string s1 = "move from ";
        string s2 = " to ";
        s1 += src;
        s2 += des;
        s1 += s2;
        ret.push_back(s1);
    }
    void Hanoi(vector<string>& ret, int n, string left, string mid, string right) {
        if (n == 1) {
            //将left直接移动到right
            GetRet(ret, left, right);
        } else {

            Hanoi(ret, n - 1, left, right,mid);   //将left上的n-1个盘子借助right移动到mid上
                
            GetRet(ret, left, right);//将left上第n个盘子直接移动到right上
          
            Hanoi(ret, n - 1, mid, left, right);  //将mid上的n-1个盘子借助left移动到right上
        }
    }
    vector<string> getSolution(int n) {
        // write code here
        vector<string> ret;
        //ret是要记录结果的容器
        //left mid right 是三个柱子的位置
        //我们约定 这三个位置有特定含义
        // left代表要移动盘子的起始位置 mid 代表辅助的柱子  right代表重点
        Hanoi(ret, n, "left", "mid", "right");
        return ret;
    }
};
// int main() {
//     Solution s1;
//     s1.getSolution(2);

//     return 0;
// }

发表于 2023-03-08 13:08:22 回复(0)
C++
Hのは嫌いです头像 Hのは嫌いです
一样的代码为啥我内存用了11MB…… 
class Solution
{
  public:
    std::vector<std::string> ops;
    void GetOps(int n, const std::string& left, const std::string& mid, const std::string& right)
    {
        if (n == 0) return;
        GetOps(n - 1, left, right, mid);
        ops.emplace_back("move from " + left + " to " + right);
        GetOps(n - 1, mid, left, right);
    }
    std::vector<std::string> getSolution(int n)
    {
        GetOps(n, "left", "mid", "right");
        return ops;
    }
};
发表于 2023-01-05 18:11:49 回复(0)
Java
一颗宏心头像 一颗宏心 
import java.util.*;

public class Solution {
    public ArrayList<String> getSolution(int n) {
        ArrayList<String> list = new ArrayList<String>();
        move(n,list,"left","mid","right");
        return list;
    }

    public static void move(int n, ArrayList<String> list,String a,String b,String c){
        if(n==1){
            list.add("move from "+a+" to "+c);
        }else{
            move(n-1,list,a,c,b);
            list.add("move from "+a+" to "+c);
            move(n-1,list,b,a,c);
        }
    }
}

发表于 2022-12-03 10:30:05 回复(0)
Python3
求offer牛头像 求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)
C++
人间不可理喻头像 人间不可理喻
class Solution {
public:
    vector<string> getSolution(int n) {
        // write code here
        vector<string> result;
        getStepresult(result, n, "left", "rignt", "mid");
        return result;
    }

    void getStepresult(vector<string> &s, int n, string start, string end, string mid){
        string temp;
        if(n == 1){
            temp = "move from " + start + " to " + end;
            s.push_back(temp);
        }else{
            getStepresult(s, n-1, start, mid, end);
            temp = "move from " + start + " to " + end;
            s.push_back(temp);
            getStepresult(s, n-1, mid, end, start);
        }
    }
};
发表于 2022-11-22 09:30:46 回复(0)
ACM真难打头像 ACM真难打 
class Solution {
public:
    vector< string >ans;
    void Hanoi(int n, string left, string mid, string right) {
        if(n == 1) {
            string s = "move from " + left + " to " + right;
            ans.push_back(s);
        } else {
            Hanoi(n - 1, left, right, mid);
            string s = "move from " + left + " to " + right;
            ans.push_back(s);
            Hanoi(n - 1, mid, left, right);
        }
    }
    vector<string> getSolution(int n) {
        Hanoi(n, "left", "mid", "right");
        return ans;
    }
};

发表于 2022-11-01 20:07:51 回复(0)
大卷菜头像 大卷菜 
import java.util.*;

// 主要 考虑的 是 每步  n - 1 怎么走 ? 
//  1 层 怎么走 ? 

public class Solution {
    private static ArrayList<String> list = new ArrayList<>();
    public ArrayList<String> getSolution(int n) {
        // write code here
        // 逐步分解子问题 知道 一个该咋走吧 作为 递归终结者。
        //整体从左到右 就写从左到右
        leftToRight(n);
        return list;
    }
    private void leftToRight(int n) {
        if (n == 1) {
            list.add("move from left to right");
            return;
        }
        // 剩下 n - 1 个 小的压大的 给 n == 1 让路  
        // 怎么 走 ？ 走法 一样 先让最后一个走 剩下的让路
        leftTomid (n - 1);
        // 走到中间了 送走底层去他相应的位置  好 怎么去下一个位置 mid to right 让 n - 1 去下一个位置
        list.add("move from left to right");
        midToRight(n - 1);
    }

    private void leftTomid(int n) {
        if (n == 1) {
            list.add("move from left to mid");
            return;
        }
        // 也是 让路 原则  n - 1 去哪 ？ 去右边 刚开始 是 n 每个柱子上都没有 盘子
        leftToRight( n - 1);
        list.add("move from left to mid");
        rightTomid(n - 1);
    }

    private void rightToLeft(int n) {
        if (n == 1) {
            list.add("move from right to left");
            return;
        }
        rightTomid(n - 1);
        list.add("move from right to left");
        midToleft(n - 1);
    }

    private void  rightTomid(int n) {
        if ( n == 1) {
            list.add("move from right to mid");
            return;
        }
        // 怎么去 让路
        rightToLeft(n-1);
        // 再来
        list.add("move from right to mid");
        leftTomid(n-1);
    }

    private void midToRight( int n ) {
        if (n == 1) {
            list.add("move from mid to right");
            return;
        }
        // 和上面 一样 剩余的让路
        midToleft( n - 1);
        list.add("move from mid to right");
        leftToRight( n - 1);
    }

    private void midToleft(int n) {
        if ( n == 1) {
            list.add("move from mid to left");
            return;
        }
        // 怎么去 让路 
        midToRight( n - 1);
        list.add("move from mid to left");
        rightToLeft(n - 1);
    }
}

发表于 2022-10-30 20:36:36 回复(0)
Java
肥咩咪头像 肥咩咪
分而治之思想 
import java.util.*;

public class Solution {
    public ArrayList<String> getSolution(int n) {
        ArrayList<String> list=new ArrayList<>();
        tower(list,n,"left","mid","right");
        return list;
    }

    public void tower(ArrayList<String> list,int n,String l,String m,String r){
        if(n==1){
            list.add("move from "+l+" to "+r);
        }else{
            tower(list,n-1,l,r,m);//注意递归时的传值，不是直接写"left"、"right"、"mid"
            list.add("move from "+l+" to "+r);
            tower(list,n-1,m,l,r);
        }
    }
}


发表于 2022-10-29 22:48:59 回复(0)
Java
屏己头像 屏己 
import java.util.*;

public class Solution {
    private ArrayList<String> ans = new ArrayList<>();
    public ArrayList<String> getSolution(int n) {
        // write code here
        dfs(n, 1, 3);
        return ans;
    }
    
    public String getType(int x) {
        switch(x) {
            case 1:
                return "left";
            case 2:
                return "mid";            
            case 3:
                return "right";
            default:
                return "left";
        }
    }
    public void dfs (int n, int begin, int end) {
        if (n == 0) {
            return;
        }
        
        int tmp = 2;
        if ((begin == 2 && end == 1 )|| (begin == 1 && end == 2)) {
            tmp = 3;
        } else if ((begin == 2 && end == 3 ) || (begin == 3 && end == 2)) {
            tmp = 1;
        }
        dfs(n-1, begin, tmp);
        
        String beginStr = getType(begin);
        String endStr = getType(end);
        ans.add("move from " + beginStr + " to " + endStr);
        
        dfs(n-1, tmp, end);
    }
}

发表于 2022-09-13 17:16:26 回复(0)
提交观点

问题信息

动态规划 递归
来自：面试常考算法题(七)-...
难度：
63条回答 18810浏览

热门推荐

通过挑战的用户

查看代码

相关试题

汉诺塔问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号