【题目】
汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间。求当塔有N层的时候,打印最优移动过程和最优移动总步数。
【解答】
上一篇用的是递归的方法解决这个问题,这里我们用栈来模拟汉诺塔的三个塔,也就是不用递归的方法
原理是这样的:修改后的汉诺塔问题不能让任何塔从左直接移动到右,也不能从右直接移动到左,而是要经过中间,也就是说,实际上能做的动作,只有四个:左→中→中,左,中,右,右→中
用栈来模拟汉诺塔的移动,其实就是某一个栈弹出栈顶元素,压入到另一个栈中,作为另一个栈的栈顶,理解了这个就好说了,对于这个问题,有两个原则:
一:小压大原则,也就是,要压入的元素值不能大于要压入的栈的栈顶的元素值,这也是汉诺塔的基本规则
二:相邻不可逆原则,也就是,我上一步的操作如果是左→中,那么下一步的操作一定不是中→左,否则就相当于是移过去又移回来
有了这两个原则,就可以推导出两个非常有用的结论:
1,游戏的第一个动作一定是L, M
2,在走出最小步数过程中的任何时刻,四个动作中只有一个动作不违反小压大和相邻不可逆原则,另外三个动作一定都会违反
【代码实现】
进口java.util.Stack;
课堂演示{
公共enum行动{
不,LToM MToL、MToR RToM
}//num是盘子的数量,左,中,对分别代表左中右三个柱子
公共静态int河内(int num,字符串,字符串中,字符串){//lS,女士,rS代表左中右三个栈(模拟柱子)
StacklS=new Stack ();
Stack女士=new Stack ();
StackrS=new Stack ();
lS.push (Integer.MAX_VALUE);
mS.push (Integer.MAX_VALUE);
rS.push (Integer.MAX_VALUE);
(int i=num; i> 0;我——){
lS.push(我);
}
行动[]={行动记录。没有};
int一步=0;
而(rS.size () !=num + 1) {
+=fStackToStack步(记录、Action.MToL Action.LToM lS, mS,左,中期);
+=fStackToStack步(记录、Action.LToM Action.MToL女士,lS,中期,左);
+=fStackToStack步(rS,记录、Action.MToR Action.RToM女士,是的,中期);
+=fStackToStack步(记录、Action.RToM Action.MToR女士,rS,中期,右);
}
返回步骤;
}//preNoAct是与现在所要进行的动作相反的动作,nowAct是现在所要进行的动作
公共静态int fStackToStack (preNoAct行动[]记录,行动,行动nowAct StackfStack StacktStack,字符串,字符串){
如果(记录[0]!=preNoAct,,fStack.peek () & lt;tStack.peek ()) {
tStack.push (fStack.pop ());
system . out。println(“移动”+ tStack.peek () +”、“+ +”→“+);
记录[0]=nowAct;
返回1;
}
返回0;
}
公共静态void main (String [] args) {
int i=河内(3、“左”、“中”、“右”);
system . out。println(“一共走了”+我+“步”);
}
}
以上就是本文关于Java编程用栈来求解汉诺塔问题的代码实例(非递归)的全部内容,希望对大家有所帮助。感兴趣的朋友可以参阅:Java蒙特卡洛算法求圆周率近似值实例详解,Java遗传算法之冲出迷宫,Java实现四则混合运算代码示例等,有什么问题可以随时留的言,欢迎大家交流讨论。
