Java编程用栈来求解汉诺塔问题的代码实例(非递归)
【题目】
汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间。求当塔有N层的时候,打印最优移动过程和最优移动总步数。
【解答】
上一篇用的是递归的方法解决这个问题,这里我们用栈来模拟汉诺塔的三个塔,也就是不用递归的方法
原理是这样的:修改后的汉诺塔问题不能让任何塔从左直接移动到右,也不能从右直接移动到左,而是要经过中间,也就是说,实际上能做的动作,只有四个:左->中,中->左,中->右,右->中
用栈来模拟汉诺塔的移动,其实就是某一个栈弹出栈顶元素,压入到另一个栈中,作为另一个栈的栈顶,理解了这个就好说了,对于这个问题,有两个原则:
一:小压大原则,也就是,要压入的元素值不能大于要压入的栈的栈顶的元素值,这也是汉诺塔的基本规则
二:相邻不可逆原则,也就是,我上一步的操作如果是左->中,那么下一步的操作一定不是中->左,否则就相当于是移过去又移回来
有了这两个原则,就可以推导出两个非常有用的结论:
1、游戏的第一个动作一定是L->M
2、在走出最小步数过程中的任何时刻,四个动作中只有一个动作不违反小压大和相邻不可逆原则,另外三个动作一定都会违反
【代码实现】
importjava.util.Stack; classDemo{ publicenumAction{ No,LToM,MToL,MToR,RToM } //num是盘子的数量,left,mid,right分别代表左中右三个柱子 publicstaticinthanoi(intnum,Stringleft,Stringmid,Stringright){ //lS,mS,rS代表左中右三个栈(模拟柱子) StacklS=newStack (); Stack mS=newStack (); Stack rS=newStack (); lS.push(Integer.MAX_VALUE); mS.push(Integer.MAX_VALUE); rS.push(Integer.MAX_VALUE); for(inti=num;i>0;i--){ lS.push(i); } Action[]record={Action.No}; intstep=0; while(rS.size()!=num+1){ step+=fStackToStack(record,Action.MToL,Action.LToM,lS,mS,left,mid); step+=fStackToStack(record,Action.LToM,Action.MToL,mS,lS,mid,left); step+=fStackToStack(record,Action.MToR,Action.RToM,rS,mS,right,mid); step+=fStackToStack(record,Action.RToM,Action.MToR,mS,rS,mid,right); } returnstep; } //preNoAct是与现在所要进行的动作相反的动作,nowAct是现在所要进行的动作 publicstaticintfStackToStack(Action[]record,ActionpreNoAct,ActionnowAct,Stack fStack,Stack tStack,Stringfrom,Stringto){ if(record[0]!=preNoAct&&fStack.peek() "+to); record[0]=nowAct; return1; } return0; } publicstaticvoidmain(String[]args){ inti=hanoi(3,"left","mid","right"); System.out.println("一共走了"+i+"步"); } }
总结
以上就是本文关于Java编程用栈来求解汉诺塔问题的代码实例(非递归)的全部内容,希望对大家有所帮助。感兴趣的朋友可以参阅:Java蒙特卡洛算法求圆周率近似值实例详解、Java遗传算法之冲出迷宫、Java实现四则混合运算代码示例等,有什么问题可以随时留言,欢迎大家交流讨论。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。