Java编程用栈来求解汉诺塔问题的代码实例(非递归)
作者:凌风暨 时间:2023-01-13 21:41:25
【题目】
汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间。求当塔有N层的时候,打印最优移动过程和最优移动总步数。
【解答】
上一篇用的是递归的方法解决这个问题,这里我们用栈来模拟汉诺塔的三个塔,也就是不用递归的方法
原理是这样的:修改后的汉诺塔问题不能让任何塔从左直接移动到右,也不能从右直接移动到左,而是要经过中间,也就是说,实际上能做的动作,只有四个:左->中,中->左,中->右,右->中
用栈来模拟汉诺塔的移动,其实就是某一个栈弹出栈顶元素,压入到另一个栈中,作为另一个栈的栈顶,理解了这个就好说了,对于这个问题,有两个原则:
一:小压大原则,也就是,要压入的元素值不能大于要压入的栈的栈顶的元素值,这也是汉诺塔的基本规则
二:相邻不可逆原则,也就是,我上一步的操作如果是左->中,那么下一步的操作一定不是中->左,否则就相当于是移过去又移回来
有了这两个原则,就可以推导出两个非常有用的结论:
1、游戏的第一个动作一定是L->M
2、在走出最小步数过程中的任何时刻,四个动作中只有一个动作不违反小压大和相邻不可逆原则,另外三个动作一定都会违反
【代码实现】
import java.util.Stack;
class Demo{
public enum Action{
No,LToM,MToL,MToR,RToM
}
//num是盘子的数量,left,mid,right分别代表左中右三个柱子
public static int hanoi(int num,String left,String mid,String right){
//lS,mS,rS代表左中右三个栈(模拟柱子)
Stack<Integer> lS = new Stack<Integer>();
Stack<Integer> mS = new Stack<Integer>();
Stack<Integer> rS = new Stack<Integer>();
lS.push(Integer.MAX_VALUE);
mS.push(Integer.MAX_VALUE);
rS.push(Integer.MAX_VALUE);
for(int i=num;i>0;i--){
lS.push(i);
}
Action[] record = { Action.No };
int step = 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);
}
return step;
}
//preNoAct是与现在所要进行的动作相反的动作,nowAct是现在所要进行的动作
public static int fStackToStack(Action[] record,Action preNoAct,Action nowAct,Stack<Integer> fStack,Stack<Integer> tStack,String from,String to){
if(record[0] != preNoAct && fStack.peek() < tStack.peek()){
tStack.push(fStack.pop());
System.out.println("Move " + tStack.peek() + " " + from + "->" + to);
record[0] = nowAct;
return 1;
}
return 0;
}
public static void main(String[] args){
int i = hanoi(3,"left","mid","right");
System.out.println("一共走了" + i + "步");
}
}
来源:http://blog.csdn.net/qq_39776901/article/details/77865185#comments
标签:java,栈
0
投稿
猜你喜欢
Java实现学生选课管理系统
2023-04-12 20:00:16
springboot如何引入外部yml配置文件
2023-11-07 07:35:38
C#中的虚方法和抽象方法的运用
2023-06-02 15:49:40
jvm垃圾回收之GC调优工具分析详解
2023-08-17 12:40:20
c#实现汉诺塔问题示例
2023-08-09 13:20:02
C#实现启用与禁用本地网络的方式小结【3种方式】
2022-04-21 18:45:14
腾讯开源消息中间件TubeMQ总体介绍分析
2022-06-21 05:10:03
java实现二叉树的创建及5种遍历方法(总结)
2022-03-14 09:00:28
java9开始——接口中可以定义private私有方法
2023-03-27 06:53:15
Unity 从Resources中动态加载Sprite图片的操作
2023-08-26 11:37:18
Android开发使用Databinding实现关注功能mvvp
2023-07-23 19:27:32
spring boot配置多个请求服务代理的完整步骤
2023-03-30 10:30:49
Android Studio配置国内镜像源(利用hosts)
2023-05-29 18:47:54
SpringBoot Actuator埋点和监控及简单使用
2023-11-20 20:09:39
java 动态 代理的方法总结
2023-08-25 04:00:33
android实现密码框右侧显示小眼睛
2023-01-26 19:54:59
Maven 生成打包可执行jar包的方法步骤
2023-01-02 14:53:15
Android递归方式删除某文件夹下的所有文件(.mp3文件等等)
2022-06-05 06:43:46
浅谈C#中的值类型和引用类型
2023-10-30 21:41:41
关于dubbo的RPC和RESTful性能及对比
2023-05-23 02:55:14