汉诺塔问题

描述
我们有由底至上为从大到小放置的 n 个圆盘，和三个柱子（分别为左/中/右即left/mid/right），开始时所有圆盘都放在左边的柱子上，按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上，要求一次只能移动一个圆盘，而且大的圆盘不可以放到小的上面。
请实现一个函数打印最优移动轨迹。给定一个 `int n` ，表示有 n 个圆盘。请返回一个 `string` 数组，其中的元素依次为每次移动的描述。描述格式为： `move from [left/mid/right] to [left/mid/right]`。


方法一

思路分析

本题是典型的递归问题，可以使用自顶向下的方法实现，所谓自顶向下的方法，就是说从最大的问题出发，逐渐减小问题规模。对于汉诺塔问题，可以这样考虑：总共需要移动n个盘子（设置左侧柱子为A，中间的柱子为B，右侧的柱子为C）递归实现的思想为：
  • 将A柱上的n-1个盘子借助C柱移向B柱
  • 将A柱上仅剩的最后一个盘子移向C柱
  • 将B柱上的n-1个盘子借助A柱移向C柱
设置函数Hanoi(n, A, B, C)表示将n个盘子从上A柱子上移动到C柱子，那么递归的规程如下：
  • Hanoi(n-1, A, C, B)将A柱上的n-1个盘子借助C柱移向B柱
  • Hanoi(1, A, B, C）将A柱上仅剩的最后一个盘子移向C柱，在此时将本题要求的移动轨迹表示为“move from A to C”，这也是递归结束的条件
  • Hanoi(n-1, B, A, C）将B柱上的n-1个盘子借助A柱移向C柱

图解


核心代码 

class Solution {
public:
    vector<string>temp;
    vector<string> getSolution(int n) {
        // write code here
        Hanoi(n,"left","mid","right");
        return temp;
        
    }
    void Hanoi(int num,string A,string B,string C)
    {
        if(num==1)
            temp.push_back("move from "+A+" to "+C) ;//只有一个盘子从left to right
        else{
            Hanoi(num-1,A,C,B);//将left柱子上面的n-1个盘子放到min柱子
            Hanoi(1,A,B,C);//将left柱子上最后一个盘子直接放到right柱子
            Hanoi(num-1,B,A,C);//将mid柱子上的n-1盘子放到right柱子
        }
        
    }
};
复杂度分析
  • 时间复杂度：当规模为1时，只需要移动一步即可，耗时为O(1),当规模大于1时，先将n-1个圆盘移动到b，耗时T(n-1),b的n-1个圆盘移动到目标柱子,耗时T(n-1)，时间复杂度可表示为，总的时间复杂度为$O(2^n)$
  • 空间复杂度：递归深度为n，空间复杂度为$O(n)$

方法二

思路分析

也可以使用非递归的思想对方法一进行改变，利用迭代的思想得到如下的算法步骤：
  • 左侧柱子中将最小的盘子移到下一个柱子上，中间柱子中将最小的盘子移到下一个柱子上
  • 对上述步骤中的剩余两个柱子上的最顶端的盘子判断，将小一点的盘子移动到大一点的盘子的柱子上，如果一个柱子是空的，那么直接将盘子放到空柱子上
  • 一直重复执行上述步骤
需要注意的是如果n为奇数，那么需要将mid与right对换。

图解



核心代码 

class Solution {
public:
    string name[3] = { "left","mid","right" };
    stack<int> s[3];
    vector<string> temp;
    void move(int a, int b)
    {
	if (s[a].empty() && !s[b].empty() || (!s[a].empty() && !s[b].empty() && s[a].top() > s[b].top()))//a为空，或者b不为空；或者a柱子顶端盘子较大，移动b柱子顶端盘子
	{
		s[a].push(s[b].top());//移动b柱子顶端盘子
		s[b].pop();//左侧柱子上的盘子移走
        temp.push_back("move from "+name[b]+" to "+name[a]);
		return;
	}
	else if (!s[a].empty() && s[b].empty() || (!s[a].empty() && !s[b].empty() && s[a].top() < s[b].top()))//a不为空，b为空；或者b柱子顶端盘子较大，移动a柱子顶端盘子
	{
		s[b].push(s[a].top());//移动a柱子顶端盘子到b
		s[a].pop();//左侧柱子a上的盘子移走
        temp.push_back("move from "+name[a]+" to "+name[b]);
		return;
	}
    }
    vector<string> getSolution(int n) {
        // write code here
        for (int i = n; i > 0; i--)
		      s[0].push(i);
        int a1, a2, a3;
        a2 = 0;
        a3 = 1;
        if (n % 2 != 0)
        {
            name[1] = "right";
            name[2] = "mid";
        }
        while (1)
        {
            move(a2, a3);//左侧柱子上的盘子移动到下一个柱子
            if (s[a3].size() == n)//如果右侧柱子盘子数量为n,那么移动结束
                break;
            a1 = a2;//将中间柱子作为左侧柱子
            a2 = a3;//右侧柱子作为中间柱子
            a3 = (a2 + 1) % 3;
            move(a1, a3); //左侧柱子上的盘子移动到下一个柱子 
                }
        return temp;
    }
    
};
复杂度分析
  • 时间复杂度：使用迭代的办法时间复杂度为$O(2^n)$
  • 空间复杂度：使用了与递归算法相同复杂度的栈空间，为$O(n)$，以及正常的存储输出数组，因此空间复杂度为$O(n)$