Java SE求解汉诺塔问题的示例代码
作者:K媾? 发布时间:2022-05-10 23:44:30
标签:Java,汉诺塔
1.问题描述
汉诺塔问题是一个经典的问题。汉诺塔(Hanoi Tower),又称河内塔,源于印度一个古老传说。
大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移动一个圆盘。 问应该如何操作?
2.画图分析
一个圆盘的情况:移动前
移动后
1个盘子:A直接移动到C
二个圆盘的情况:移动前
移动后
2个圆盘:A->B A->C B->C
三个圆盘的情况:移动前
移动后
三个圆盘:A->C A->B C->B A->C B->A B->C A-C
3.问题讲解
当有3个盘子的时候,你就会发现一个问题,你肯定是要先将上面的两个盘子移动到B柱,再把最底下的一个盘子移动到C柱,最后再把B柱的盘子移动到C柱。4个盘子的话也是一样,要先将上面的3个盘子移动到B柱,在把最底下的一个盘子移动到C柱,最后再把B柱的盘子移动到C柱。这样我们就有了一个思路,不管多少个盘子,都要先将n - 1个盘子移动到B柱,最底下的一个盘子移动到C柱,最后再把B柱的盘子移动到C柱。
我们先来看一下规律:
1个盘子:A->C 1次
2个盘子:A->B A->C B->C 3次
3个盘子:A->C A->B C->B A->C B->A B->C A-C 7次
这样你就能看出移动的次数其实就是2^n - 1(n是盘子的数量)
4.代码实现
ublic class TestDemo {
//首先要写个模拟鼠标移动过程的函数,我们要打印出移动的全部过程
//这个move函数做到的就是从1位置移动到2位置,有可能是A->B,A->C,C-B......等各种可能
public static void move(char pos1,char pos2){//所以说这里只需要传对应的位置就可以了
System.out.print(pos1+"->"+pos2+" ");//pos1移动到pos2
}
/**
*
* @param n n代表你盘子的个数
* @param pos1 盘子所在的位置
* @param pos2 盘子的中转位置
* @param pos3 盘子的结束位置
*/
public static void hanio(int n,char pos1,char pos2,char pos3){
if(n == 1){
move(pos1,pos3);//如果只有一个盘子那就从A柱挪到C柱上
}else{
hanio(n-1,pos1,pos3,pos2);//这里是把n-1个盘子从A柱借助C柱移动到B柱
move(pos1,pos3);//底下剩下的最后一个盘子从A柱移动到C柱
hanio(n-1,pos2,pos1,pos3);//这里是把n-1个盘子从B柱借助A柱移动到C柱
}
}
public static void main(String[] args) {
hanio(1,'A','B','C');//一开始我们的汉诺塔要规定一下,我们第一次给它传过去的位置
System.out.println();
hanio(2,'A','B','C');
System.out.println();
hanio(3,'A','B','C');
System.out.println();
}
}
打印结果:
来源:https://blog.csdn.net/m0_64397675/article/details/123205881
0
投稿
猜你喜欢
- Result也是Struts2比较重要的一部分,在Result的配置中常用的有四种类型:dispatcher、redirect、chain和
- 一、百度百科Sentinel 是面向分布式服务架构的高可用流量防护组件,主要以流量为切入点,从限流、流量整形、熔断降级、系统负载保护、热点防
- 英文设置加粗可以在xml里面设置: <SPAN style="FONT-SIZE: 18px">androi
- 上一次接触到编码的知识,还是上大学的时候,那时候学的是通信工程专业,有关编码的内容,不记得是在通信原理还是信息论与编码里面学到的了。却依然记
- 本项目主要实现对汽车维修厂的信息化管理功能,主要包含三个角色:管理员,维修师傅,客户。实现的主要功能包含用户管理、配置管理、汽车管理、故障管
- 当我们使用swagger,进行接口测试,怕接口不安全,担心暴露。可采用两种方式1.环境权限配置对swagger文档配置只在测试环境可访问,生
- 0x00:前言参考之前的《MyBatis 中 SqlMapConfig 配置文件详解》记了一下 MyBatis 中的核心配置文件各个标签的作
- IDEA快速搭建spring boot项目1.创建项目老规矩,点击Create New Project2.编写控制器在com.demo.sp
- 目录1.搭建环境2.项目搭建3.配置maven4.项目结构5.配置 MapperScan 注解6.创建实体7.创建接口8.测试8.1 upd
- 废话开篇:iOS与android在实现列表界面的时候是有重用机制的,目的就是减少内存开销,用时间换空间。个人感觉flutter并没有特别强调
- 引言设计: 嗯? 这个图片点击跳转进详情再返回图片怎么变白闪一下呢?产品: 是啊是啊! 一定是个bug开发: 囧囧囧在开发过程中, 也许你也
- 由Lombok的@AllArgsConstructor注解引发的错误需求:在Service实现中写了一个方法调用第三方接口同步数据。 功能代
- 本文主要介绍了Maven实战之搭建Maven * 和镜像的方法(图文),分享给大家,具体如下:准备工作安装3.6.*的Nexus理论Nexus
- 这篇文章主要介绍了Spring boot整合log4j2过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值
- 前言Kotlin一个强大之处就在于它的扩展函数,巧妙的运用这些扩展函数可以让你写出的代码更加优雅,阅读起来更加流畅,下面总结了在开发中经常用
- 一、泛型的概念1.1 基础案例泛型在Java中的应用非常广泛,最常见则是在集合容器中,先看下基础用法:public class Generi
- 先看代码public class TestDemo1 { public static void main(String[] ar
- PullToRefresh是一套实现非常好的下拉刷新库,它支持:1.ListView2.ExpandableListView3.GridVi
- 背景后台系统需要接入 企业微信登入,满足企业员工快速登入系统流程图简单代码说明自定义一套 springsecurity 认证逻辑主要就是 根
- Google 发布的Material Design支持库,对我们的APP设计有很大的影响,如果重新设计APP,支持库应该直接用V4提升到V7