Java SE求解汉诺塔问题的示例代码
作者:K媾? 时间:2022-05-10 23:44:30
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
标签:Java,汉诺塔
0
投稿
猜你喜欢
ObjectMapper 如何忽略字段大小写
2023-07-31 07:07:18
python只需30行代码就能记录键盘的一举一动
2023-06-27 18:22:12
Java基础之堆内存溢出的解决
2023-11-10 20:06:30
浅谈JVM内存溢出原因和解决思路
2023-11-23 12:24:15
基于JAVA文件中获取路径及WEB应用程序获取路径的方法
2022-08-21 01:26:57
Java新手环境搭建 JDK8安装配置教程
2023-11-25 17:23:10
Java为实体类动态添加属性的方法详解
2023-09-01 05:31:43
Java线程池ThreadPoolExecutor源码深入分析
2023-11-09 19:49:36
Idea中SpringBoot多模块项目的建立实现
2023-11-08 07:52:34
Java中ArrayList集合的常用方法大全
2023-09-01 15:23:30
springcloud配置ssh的问题及解决方法
2023-11-03 15:48:11
IO中flush()函数的使用代码示例
2023-11-27 03:49:00
详解Spring-boot中读取config配置文件的两种方式
2021-07-04 15:52:55
使用开源项目JAVAE2 进行视频格式转换
2023-11-08 07:18:24
C++高并发内存池的整体设计和实现思路
2023-07-03 16:29:31
Spring boot2X负载均衡和反向代理实现过程解析
2023-02-06 04:18:53
基于SpringMVC的全局异常处理器介绍
2023-11-23 20:55:58
带你重新认识MyBatis的foreach
2023-11-21 08:44:54
SpringBoot文件分片上传的示例代码
2023-06-18 11:30:15
Spring MVC 使用支付宝接口完成在线支付的示例代码
2023-11-29 04:07:55