【牛客题霸题解】汉诺塔问题

把n个盘子从Left 借助 Mid，移动到Right柱子上
可以分为以下三步：

1. 把n-1个盘子从Left 借助 Right，移动到Mid柱子上
2. 把剩下最大的那一个盘子从Left移动到 Right柱子上
3. 把n-1个盘子从Mid 借助 Left，移动到,Right柱子上

我们定义函数

void Hanoi(int n,string Left,string Mid,string Right)

来完成把n个盘子从Left 借助 Mid，移动到Right柱子上
然后进行递归就可以了
c++

class Solution{
public:
    vector<string> ans;
    //把n个盘子从Left 借助 Mid，移动到Right柱子上
    void Hanoi(int n,string Left,string Mid,string Right)
    {
        if(n==0){return;}
        //把n-1个盘子从Left 借助 Right，移动到Mid柱子上
        Hanoi(n-1,Left,Right,Mid);
        //把剩下最大的那一个盘子从Left移动到 Right柱子上
        string t = "move from " + Left + " to " + Right;
        ans.push_back(t);
        //把n-1个盘子从Mid 借助 Left，移动到,Right柱子上
        Hanoi(n-1,Mid,Left,Right);
    }
    vector<string> getSolution(int n) {
        Hanoi(n,"left","mid","right");
        return ans;
    }
};

java

import java.util.*;
public class Solution{
    ArrayList<String> ans = new ArrayList<>();
    //把n个盘子从Left 借助 Mid，移动到Right柱子上
    public void Hanoi(int n, String Left, String Mid, String Right)
    {
        if(n==0){return;}
        //把n-1个盘子从Left 借助 Right，移动到Mid柱子上
        Hanoi(n-1,Left,Right,Mid);
        //把剩下最大的那一个盘子从Left移动到 Right柱子上
        String t = "move from "+Left+" to "+Right;
        ans.add(t);
        //把n-1个盘子从Mid 借助 Left，移动到,Right柱子上
        Hanoi(n-1,Mid,Left,Right);
    }
    public ArrayList<String> getSolution(int n) {
        Hanoi(n,"left","mid","right");
        return ans;
    }
}

python

class Solution:
    #把n个盘子从Left 借助 Mid，移动到Right柱子上
    def Hanoi(self,n,Left,Mid,Right):
        if n==0:
            return
        #把n-1个盘子从Left 借助 Right，移动到Mid柱子上
        self.Hanoi(n-1,Left,Right,Mid)
        #把剩下最大的那一个盘子从Left移动到 Right柱子上
        t = "move from "+Left+" to "+Right
        self.ans.append(t)
        #把n-1个盘子从Mid 借助 Left，移动到,Right柱子上
        self.Hanoi(n-1,Mid,Left,Right)
    def getSolution(self , n ):
        self.ans = []
        self.Hanoi(n,"left","mid","right")
        return self.ans