首页 > 试题广场 >

汉诺塔问题

[编程题]汉诺塔问题

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

算法知识视频讲解

Java

One_Heart

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)

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)

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)

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)

Java

阿尼亚瓦库瓦库

import java.util.*;

public class Solution {
    
    ArrayList<String> result = new ArrayList<>();
    
    public ArrayList<String> getSolution(int n) {
        // write code here
        hanoi(n, "left", "mid", "right");
        return result;
    }
    
    private void hanoi(int n, String from, String by, String to) {
        
        if (n == 0) {
            return;
        }
        
        if (n == 1) {
            result.add("move from " + from + " to " + to); // 一个的时候直接转移
        } else {
            hanoi(n - 1, from, to, by); // 先借助第三根柱子转移到第二根柱子
            result.add("move from " + from + " to " + to);
            hanoi(n - 1, by, from, to); // 再从第二根柱子借助地一根柱子转移到第三根柱子
        }
    }
}

经典分治问题。再简化一些：

import java.util.*;

public class Solution {
    
    ArrayList<String> result = new ArrayList<>();
    
    public ArrayList<String> getSolution(int n) {
        // write code here
        hanoi(n, "left", "mid", "right");
        return result;
    }
    
    private void hanoi(int n, String from, String by, String to) {
        
        if (n == 0) {
            return;
        }
        
        hanoi(n - 1, from, to, by); // 先借助第三根柱子转移到第二根柱子
        result.add("move from " + from + " to " + to);
        hanoi(n - 1, by, from, to); // 再从第二根柱子借助地一根柱子转移到第三根柱子
    }
}

编辑于 2021-05-26 14:14:47 回复(0)

Java

学习算法脑壳疼

import java.util.*;

public class Solution {
    ArrayList<String> str=new ArrayList<>();
    public ArrayList<String> getSolution(int n) {
        // write code here
        HanNuo(n,"left","mid","right");
        return str;
    }
    public void HanNuo(int n,String left,String mid,String right){
        if(n==1){
            str.add("move from "+left+" to "+right);
        }
        else{
            HanNuo(n-1,left,right,mid);
            str.add("move from "+left+" to "+right);
            HanNuo(n-1,mid,left,right);
        }
    }
}

发表于 2021-05-04 19:04:32 回复(0)

Java

安徒生的谎言

import java.util.*;

public class Solution {
    public static ArrayList<String> getSolution(int n) {
        // write code here
        ArrayList<String> result=new ArrayList<>();
        if(n==0) {}
        else {
            Solution(result,n, "left", "right", "mid");
        }
        return result;
    }
    public static void Solution(ArrayList<String> array, int n, String x,String y,String z) {
        if(n==0) {}
        else {
            Solution(array,n-1, x, z, y);
            array.add("move from "+x+" to " +y);
            Solution(array,n-1, z, y, x);
        }
    }
}

发表于 2018-01-28 11:21:07 回复(0)

Java

Holiday_12138

import java.util.*;
public class Solution {
    public void solution(int n,String begin,String end,String tmp,ArrayList<String> res){
        if(n<=0)
            return ;
        if(n==1)
            res.add(new String("move from "+begin+" to "+end));
        else{
            solution(n-1,begin,tmp,end,res);
            solution(1,begin,end,tmp,res);
            solution(n-1,tmp,end,begin,res);
        }
    }
    public ArrayList<String> getSolution(int n) {
        ArrayList<String> res=new ArrayList<String>();
        solution(n,"left","right","mid",res);
        return res;
    }
}

发表于 2017-03-06 15:49:39 回复(0)

Java

詆調壹點

import java.util.*;
public class Solution {
  public ArrayList<String> getSolution(int n) {
		ArrayList<String> list = new ArrayList<>();
		hanoi(list, n, "left", "mid", "right");
		return list;
	}
	public static void hanoi(ArrayList<String> list, int n, String from, String denpend, String to) {
		if(n == 1) {
			list.add("move from " + from + " to " + to);
		} else {
			hanoi(list, n - 1, from, to, denpend);
			hanoi(list, 1, from, denpend, to);
			hanoi(list, n - 1, denpend, from, to);
		}
	}
}

发表于 2016-09-21 21:32:45 回复(0)

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)

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)