题解 | #汉诺塔问题#

思路： 从题中给出的有效信息：

• 汉诺塔，不需要记录次数，但是需要移动的塔的名字
• 对于汉诺塔，无论在哪座塔上，小盘必须要在大盘上面，因此可以逆向思维从结果考虑，left塔最下面的大盘，必定是left塔仅剩它，而right塔上面又什么东西都没有时才可以移动，则其余n-1个盘都在mid塔上，且顺序为从小到大依次往下，则mid就是一个n-1的汉诺塔。由此可见，这是一个需要用递归的问题，怎么用递归？我们可以看下方图解：

当n=1时，可以直接移动： 当n=2时，需要借助mid才能移动： 当n=3时，借助righ移动了3-1=2到mid上，再将mid到right看成新的2个盘的汉诺塔，借助left即可： 由此可见，仅需要将其当作n-1再利用旁边另一个塔即可实现递归。 方法一：递归

class Solution {
public:
    //标记移动字符串的函数
    void move(string m, string n, vector<string>& s)
    {
        string temp = "move from "+ m + " to " + n;
        s.push_back(temp);
    }
    //实现汉诺塔递归的函数
    void hanoi(int n, string left, string mid, string right, vector<string>& s)
    {
        if(n == 1)//圆盘只有一个时，只需将其从left移到right
            move(left, right, s);//信息添加进string数组
        else
        {
            hanoi(n - 1, left, right, mid, s);//递归，把left上编号1~n-1的圆盘移到mid上，以right为辅助塔
            move(left, right, s);//把left塔上的圆盘移到right上
            hanoi(n - 1, mid, left, right, s);//递归，把mid塔上编号1~n-1的圆盘移到righ上，以left为辅助塔
        }
    }
    vector<string> getSolution(int n) {
        string left = "left";
        string mid = "mid";
        string right = "right";
        vector<string> res;
        hanoi(n, left, mid, right, res);
        return res;
    }
};

复杂度分析：

• 时间复杂度：O(2^n)，因为一个规模为n的递归里面包含了两个n-1，即T(n)=1+T(1)+2T(n-1)
• 空间复杂度：O(n)，递归栈的最大深度

方法二：非递归

递归的核心思想是栈，能够用递归的问题，用栈就能够解决。 不过需要注意，参数不会再随着函数传递，所以需要设置一个结构来存参数，再以这个参数结构来构建栈。

class Solution {
public:
    struct param {
        int n;
        string from;   //源自
        string pass;   //经过
        string to;     //去向
    };//设置参数集合
    //标记移动字符串的函数
    void move(string m, string n, vector<string>& s)
    {
        string temp = "move from "+ m + " to " + n;
        s.push_back(temp);
    }
    //实现汉诺塔非递归的函数
    void hanoi(int n, string left, string mid, string right, vector<string>& s)
    {
        if(n == 1)//圆盘只有一个时，只需将其从left移到right
            move(left, right, s);//信息添加进string数组
        else
        {
            stack<param> temp;   //用栈来模拟递归
            param p1;
            p1.n = n, p1.from = left, p1.pass = mid, p1.to = right; //初始化
            while(!(p1.n == 0 && temp.empty())){
                param p2 = p1;
                while (p2.n > 0) {
                        temp.push(p2);  //进栈直到最后一个，相当于递归子问题
                        p2.n --;
                        swap(p2.pass, p2.to);
                }
                p1 = temp.top();  //出栈，相当于递归回来
                temp.pop();
                move(p1.from, p1.to, s);
                p1.n --;
                swap(p1.from, p1.pass);
            }
        }
    }
    vector<string> getSolution(int n) {
        string left = "left";
        string mid = "mid";
        string right = "right";
        vector<string> res;
        hanoi(n, left, mid, right, res);
        return res;
    }
};

复杂度分析：

• 时间复杂度：O(2^n)，相当于一个递归
• 空间复杂度：O(n)， 栈空间，也即方法一中递归栈最大深度