Java编程用栈来求解汉诺塔问题的代码实例(非递归)
作者:凌风暨 发布时间:2023-01-13 21:41:25
标签:java,栈
【题目】
汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间。求当塔有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
0
投稿
猜你喜欢
- <%@ page language="java" contentType="text/html; cha
- poi解析Excel文件版本问题解决办法poi解析Excel文件时有两种格式: HSSFWorkbook格式用来解析Excel2003(xl
- 前言Java8 由Oracle在2014年发布,是继Java5之后最具革命性的版本。Java8吸收其他语言的精髓带来了函数式编程,lambd
- 简介AccessibilityService的设计初衷是为了辅助有身体缺陷的群体使用Android应用,它的设计贯穿着Android的控件树
- struts2可以非常简单地使用FreeMarker模板作为视图技术,对于传统的jsp页面而言,FreeMarker是一个绝佳的替代方案。除
- List 是在开发中比较常用的集合,今天总结一下 Java 中初始化 List 的几种方式。1、常规方式List<String>
- 定义MD全称Message-Digest,即信息摘要,所以MD家族的算法也叫信息摘要算法MD家族有MD2、MD3、MD4、MD5,一代比一代
- ELK环境安装ELK是指Elasticsearch、Kibana、Logstash这三种服务搭建的日志收集系统,具体搭建方式可以参考《Spr
- 配置详情pom.xmldependency> <groupId>com.baomidou<
- 一、算法描述波雷费密码是一种对称式密码,是首种双字母取代的加密法。下面描述算法步骤:1、从1号二维码M05,提取明文信息和密文,M05格式:
- 1、取得控制台应用程序的根目录方法方法1、Environment.CurrentDirectory 取得或设置当前工作目录的完整限定路径方法
- 我们深知在操作Java流对象后要将流关闭,但往往事情不尽人意,大致有以下几种不能一定将流关闭的写法:1.在try中关流,而没在finally
- 1. 前言老板说,明天甲方要来看产品,你得造点数据,而且数据必须是“真”的,演示效果要好看一些,这样他才会买我们的产品,我好明年给你换个嫂子
- The java.io.Writer.flush() method flushes the stream. If the stream ha
- 前文本章是关于Java流程控制语句的最全汇总,本篇为汇总上篇。流程是人们生活中不可或缺的一部分,它表示人们每天都在按照一定的流程做事。比如出
- 前言最近在改进项目的并发功能,但开发起来磕磕碰碰的。看了好多资料,总算加深了认识。于是打算配合查看源代码,总结并发编程的原理。准备从用得最多
- 1、properties文件显示乱码问题原因是因为properties默认使用ASCII码,就算在文件中填写了中文,再打开后依然会转换成AS
- 1.新建springBoot项目在前面有两种方式2.加入thymeleaf模板引擎SpringBoot推荐使用thymeleaf模板引擎语法
- 概念优先级队列是一种先进先出(FIFO)的数据结构,与队列不同的是,操作的数据带有优先级,通俗的讲就是可以比较大小,在出队列的时候往往需要优
- 近日,开发者头条上分享了一篇“小米java第二轮面经”,有很多的java程序员表示非常有兴趣。下面就和各位分享小米java第二轮面经:0、谈