首页 > 试题广场 >

汉诺塔问题

[编程题]汉诺塔问题

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

算法知识视频讲解

啥

发表于 2015-08-13 11:37:10 回复(0)

Java

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！

递归求解

假设有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

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

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





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)

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のは嫌いです

一样的代码为啥我内存用了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牛

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真难打

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)

C++

huitudou

class Solution {
private:
    vector<string> result;
    void move(string A, string B, string C, int n) {
        if (n==1) {
            result.push_back("move from "+A+" to "+C);
            return;
        }
        move(A, C, B, n-1); // A的n-1层移到B
        move(A, B, C, 1); // A的最后一层移到C
        move(B, A, C, n-1); // B的n-1层移到C
    }
public:
    vector<string> getSolution(int n) {
        move("left", "mid", "right", n);
        return result;
    }
};

发表于 2022-08-18 22:45:30 回复(0)

Java

痞子水鬼

import java.util.*;

public class Solution {
public ArrayList<String> getSolution(int n) {
String dp = dp(n, "L->R");
System.out.println(dp);
ArrayList<String> res = new ArrayList<String>();
String[] resultStr = dp.split("1");
for (int i = 0; i < resultStr.length; i++) {
if (resultStr[i].equals("L->R")) {
res.add("move from left to right");
} else if (resultStr[i].equals("L->M")) {
res.add("move from left to mid");
} else if (resultStr[i].equals("M->R")) {
res.add("move from mid to right");
} else if (resultStr[i].equals("R->M")) {
res.add("move from right to mid");
} else if (resultStr[i].equals("M->L")) {
res.add("move from mid to left");
} else if (resultStr[i].equals("R->L")) {
res.add("move from right to left");
}
}
System.out.println(res.toString());

return res;
}

/**
* @param n 移动的圆盘数
* @param dir 起始柱子和结束柱子移动方向 0：L->R 1:L->M 2：M->R 3:R->M 4:M->L 5:R->L
* @return
*/
private static String dp(int n, String dir) {
if (n == 1) {
if (dir.equals("L->R")) {
return "L->R";
} else if (dir.equals("L->M")) {
return "L->M";
} else if (dir.equals("M->R")) {
return "M->R";
} else if (dir.equals("R->M")) {
return "R->M";
} else if (dir.equals("M->L")) {
return "M->L";
} else if (dir.equals("R->L")) {
return "R->L";
}
} else {
if (dir.equals("L->R")) {
return dp(n - 1, "L->M") + "1" + "L->R" + "1" + dp(n - 1, "M->R");
} else if (dir.equals("L->M")) {
return dp(n - 1, "L->R") + "1" + "L->M" + "1" + dp(n - 1, "R->M");
} else if (dir.equals("M->R")) {
return dp(n - 1, "M->L") + "1" + "M->R" + "1" + dp(n - 1, "L->R");
} else if (dir.equals("R->M")) {
return dp(n - 1, "R->L") + "1" + "R->M" + "1" + dp(n - 1, "L->M");
} else if (dir.equals("M->L")) {
return dp(n - 1, "M->R") + "1" + "M->L" + "1" + dp(n - 1, "R->L");
} else if (dir.equals("R->L")) {
return dp(n - 1, "R->M") + "1" + "R->L" + "1" + dp(n - 1, "M->L");
} else {
return null;
}

}
return null;
}
}

发表于 2022-08-06 21:07:17 回复(0)

布加迪.威龙

class Solution {
public:
    
    vector<string> getSolution(int n) {
        // write code here
        helper(n, "left", "mid", "right");
        return ans;
    }
    int helper(int n,string left, string mid, string right){
        if(n==0)
            return 0;
        if(n==1){
            ans.push_back("move from "+left+" to "+right);
            return 0;
        }
        helper(n-1, left, right, mid);
        ans.push_back("move from "+left+" to "+right);
        helper(n-1, mid, left, right);
            
        return 0;
            
    }
private:
    vector<string> ans;
};

发表于 2022-07-18 11:21:43 回复(0)