玩命的流沙问题是一个非常经典的算法，我们首先来研究一下修改的玩命的流沙（简化步骤），在后面我们将来讲述经典的玩命的流沙问题。
题目：
修改后的玩命的流沙的规则：现在限制不能从最左侧的塔直接移动到最右侧，必需要经过中间；同时从最右侧移动到最左测试，同样必需经过中间；要求移动N层塔时，打印最优移动
1、用递归函数实现（从最左移动到最右）
分析：
- 当只有一层塔时，我们先需要将其从左移到中间，再从中间移动到右边，共分为两步；如果它就在中间，那么我们只需要将它移动到左或则右，一步就行；
- 当我们有N 层塔时，我们需要先将1~N-1层塔移动到右边，然后移动第N层塔到中间，再将1~N-1层塔移动到最左边，将N层塔由中间移动右边；这样，第N层塔就移好了
- 接下来重复上述步骤，将1~N-2层塔移到最右边，将第N-1层塔移到最中间……（利用递归函数实现）
代码实现：
void _HanoiProblem1(int num,string from,string to,int& count)//num代表塔的层数，from代表开始移动的位置(left，mid，right)，to 代表要移动到的位置{ if(num == 1)//我们只有一层塔 { if(from.compare("mid")==0 || to.compare("mid")==0)//此时只需直接移动 { count++; cout<<"move "<<num<<" from "<<from.c_str()<<" to "<<to.c_str()<<endl; } else { cout<<"move "<<num<<" from "<<from.c_str()<<" to "<<"mid"<<endl; count++; cout<<"move "<<num<<" from "<<"mid"<<" to "<<to.c_str()<<endl; count++; } } else//我们有多层塔 { if(from.compare("mid")==0 || to.compare("mid")==0) { string another; if(from.compare("left")==0) another = "right"; else another = "left"; _HanoiProblem1(num-1,from,another,count);//例如从左移到中间，先将1~N-1层塔移动到右边， cout<<"move "<<num<<" from "<<from.c_str()<<" to "<<to.c_str()<<endl;//再将第N层塔移到中间 count++; _HanoiProblem1(num-1,another,to,count);//再将1~N-1层塔移到中间 } else//从左移到右或从右移到左 { _HanoiProblem1(num-1,from,to,count);//例如从左移到右，先将1~N-1层塔从左移动到右边， cout<<"move "<<num<<" from "<<from.c_str()<<" to "<<"mid"<<endl;//再将第N层塔移到中间 count++; _HanoiProblem1(num-1,to,from,count);//再将1~N-1层塔从右移动到左边 cout<<"move "<<num<<" from "<<"mid"<<" to "<<to.c_str()<<endl;//再将第N层塔从中间移到右边 count++; _HanoiProblem1(num-1,from,to,count);//再将1~N-1层塔从左移动到右边 } }}void HanoiProblem1(int num,string from,string to){ int count = 0; _HanoiProblem1(num,from,to,count); cout<<"count is: "<<count<<endl;}测试代码：
void funtest(){ HanoiProblem1(2,"left","right");}int main(){ funtest(); getchar(); return 0;}结果图
2.用栈模拟实现
分析：
我们上面用递归实现，我们已经知道了基本的走法，接下来我们用栈来模拟玩命的流沙问题，将塔的移动转换为入栈和出栈的操作，但是，由题我们知道了参数入栈和出栈的两个基本规则
满足了以上两条规则，我们现在看移动的过程，一个塔a,只有四中可能的动作，从左到中，从中到右，从右到中，从中到左，但是要满足以上两种规则我们发现它只有一种动作可以走；例如：a在最左边，第一次，它只能从左到中间，第二次，由规则知，从左到中间不行，从中间到左没有意义，那么只剩下从中间到右和从右到中间，我们只需判断就能得到结果。
代码实现：
enum action{ No, LToM, MToL, RToM, MToR,};int fStackToStack(action& record,action preAction,action nowAction,stack<int>& fstack,stack<int>& tstack,string from,string to){ if(record != preAction && fstack.top() < tstack.top())//满足两条准则，动作不可逆和小压大原则 { int data = fstack.top(); fstack.pop(); tstack.push(data); cout<<"move "<<data<<" from "<<from.c_str()<<" to "<<to.c_str()<<endl; record = nowAction; return 1; } return 0;}int HanoiProblem2(int num,string left,string mid,string right){ stack<int> ls; stack<int> ms; stack<int> rs; ls.push(INT_MAX); ms.push(INT_MAX); rs.push(INT_MAX); for(int idx=num; idx>0; --idx) ls.push(idx); action record = No;//记录上一步的动作 int count = 0; while(rs.size() != num+1) { count += fStackToStack(record,MToL,LToM,ls,ms,left,mid); count += fStackToStack(record,LToM,MToL,ms,ls,mid,left); count += fStackToStack(record,MToR,RToM,rs,ms,right,mid); count += fStackToStack(record,RToM,MToR,ms,rs,mid,right); } return count;}测试代码：
void funtest(){ int ret = HanoiProblem2(2,"left","mid","right"); cout<<ret<<endl;}int main(){ funtest(); getchar(); return 0;}结果图：