Java使用递归法解决汉诺塔问题的代码示例
作者:goldensun 发布时间:2023-09-05 20:31:28
标签:Java,递归
汉诺(Hanoi)塔问题:古代有一个梵塔,塔内有三个座A、B、C,A座上有n个盘子,盘子大小不等,大的在下,小的在上(如图)。
有一个和尚想把这n个盘子从A座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。在移动过程中可以利用B座,要求打印移动的步骤。如果只有一个盘子,则不需要利用B座,直接将盘子从A移动到C。
如果有2个盘子,可以先将盘子1上的盘子2移动到B;将盘子1移动到c;将盘子2移动到c。这说明了:可以借助B将2个盘子从A移动到C,当然,也可以借助C将2个盘子从A移动到B。
如果有3个盘子,那么根据2个盘子的结论,可以借助c将盘子1上的两个盘子从A移动到B;将盘子1从A移动到C,A变成空座;借助A座,将B上的两个盘子移动到C。这说明:可以借助一个空座,将3个盘子从一个座移动到另一个。
如果有4个盘子,那么首先借助空座C,将盘子1上的三个盘子从A移动到B;将盘子1移动到C,A变成空座;借助空座A,将B座上的三个盘子移动到C。
Java代码如下:
public class Hanoi {
public static void main(String[] args) {
int disk = 3; //盘子
move(disk, 'A', 'B', 'C');
}
/*
* 根据题意,从上向下编号 => 1 ~ n
*/
/**
*
* @param topN 源塔顶的盘子编号
* @param from 从哪个塔移动
* @param inter 中介,过渡的塔
* @param to 目的塔
*/
private static void move(int topN, char from, char inter, char to) {
if (topN == 1) {
System.out.println("Disk 1 from " + from + " to " + to);
} else {
move(topN - 1, from, to, inter);
System.out.println("Disk " + topN + " from " + from + " to " + to);
move(topN - 1, inter, from, to);
}
}
}
out
Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C
0
投稿
猜你喜欢
- 定义:动态给一个对象添加一些额外的职责,就象在墙上刷油漆.使用Decorator模式相比用生成子类方式达到功能的扩充显得更为灵活。设计初衷:
- 打包与运行在项目开发完成之后,可以直接用IDEA将其打包成JAR包运行,也可以打包成WAR包运行以便在多服务器、多配置环境下运行。双击cle
- 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方
- 前言作为一个写java的使用最多的轻量级框架莫过于spring,不管是老项目用到的springmvc,还是现在流行的springboot,都
- /** * 三角数字: * 比达哥斯拉领导下的古希腊数学家发现了一个有趣的数字序列1, 3, 6, 10, 15, 21,... *
- 一.解析概念StringUtils概念StringUtils 方法的操作对象是 Java.lang.String 类型的对象,是 JDK 提
- 作为开发人员,掌握开发环境下的调试技巧十分有必要。我们在编写java程序的过程中,经常会遇到各种莫名其妙的问题,为了检测程序是哪里出现问题,
- 最近修改线上bug的时候排查了一个十分隐藏的bug,直接上代码:Integer a = null;boolean flag = true;I
- 前言AndroidStudio升级到3.0之后,gradle版本也随之升级到了3.0.0版本。当gradle插件升级到3.0.0及以上后,我
- using System; using System.Collections.Generic; using System.Text; usi
- 在谈 JVM 内存区域划分之前,我们先来看一下 Java 程序的具体执行过程,我画了一幅图。Java 源代码文件经过编译器编译后生成字节码文
- 本文实例讲述了Hibernate实现批量添加数据的方法。分享给大家供大家参考,具体如下:1.Hibernate_016_Ba
- 前言Condition是在Spring4.0增加的条件判断功能,通过这个功能可以实现选择性的创建Bean对象。引入一个例子SpringBoo
- 工作笔记(在不知道json的key时如何获取当前json的keys)String json="{'name':
- 1.将本地jar包放入本地仓库。只需执行如下命令即可:mvn install:install-file -Dfile=D:/demo/fib
- Java IDE工具提供了多种用户独特需求和个人偏好来创建编程环境的方法。Java框架能够简化程序员的工作。这些框架被设计和开发用于在任何服
- 一直使用的是FastJson,感觉还不错,很方便。看了一段别人的分析,觉得很有道理。为什么要使用Fastjson,其实原因不需要太多,喜欢就
- JPA连接到数据库,调用存储过程,这样的需求很常见。本文就针对这一点,讲述如何使用spring Data JPA调用存储过程的方法。1、存储
- 1、实现原理不同过滤器和 * 底层实现方式大不相同,过滤器 是基于函数回调的, * 则是基于Java的反射机制( * )实现的。1、拦
- 本文实例为大家分享了java导出百万以上数据的excel文件,供大家参考,具体内容如下1.传统的导出方式会消耗大量的内存,2003每个she