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