【Java】汉诺塔
汉诺塔
汉诺塔(Tower of Hanoi)(河内塔):把圆盘从下面开始按大小顺序重新摆放到另一根柱子上,并且小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
汉诺塔规则
- disk表示圆盘数
- 一次只能移动一个圆盘
- 小圆盘只能在大圆盘的上方
- A 、B 、C分别表示圆柱
- A为起始圆柱、B为中转圆柱、C为终止圆柱
disk = 1 时:
移动次数为:2^1 - 1
只需要将绿色圆盘从 A->C 直接移过去;
A->C

disk = 2 时:
移动次数为:2^2 - 1,一次只能移动一个圆盘
- 黄色圆盘从 A->B
- 绿色圆盘从 A->C
- 黄色圆盘从 B->C
A->B A->C B->C

disk = 3 时:
移动次数为:2^3 - 1,一次只能移动一个圆盘
- 粉色圆盘从 A->C
- 黄色圆盘从 A->B
- 粉色圆盘从 C->B
- 绿色圆盘从 A->C
- 粉色圆盘从 B->A
- 黄色圆盘从 B->C
- 粉色圆盘从 A->C
A->C A->B C->B A->C B->A B->C A->C


递归分析
- 先看desk = 3 个圆盘时,我们是先将圆柱A上面的2个圆盘(3 - 1),借助圆柱C最终移动到圆柱B上;
- 此时圆柱A上就只剩1个圆盘,就可以直接将圆盘从圆柱A移动到圆柱C;
- desk = 2个圆盘,先将圆柱B上面的那1个圆盘(2 - 1),最终直接从圆柱B移动到圆柱A上;
- 此时圆柱B上就只剩1个圆盘,就可以直接从圆柱B移动到圆柱C上;
- 只剩最后1个圆盘了,则是直接从圆柱A上移动到圆柱C上;
disk = n 时:
移动次数为:2^n - 1,一次只能移动一个圆盘
错误递归分析
- 当desk = n个圆盘时,需要将圆柱A上面的n-1个圆盘,借助圆柱C最终移动到圆柱B上;
- 此时圆柱A上就只剩1个圆盘,则直接从圆柱A移动到圆柱C;
- desk = n 时,先将圆柱B上面的n-1个圆盘,借助圆柱C最终移到圆柱A上;
- 此时圆柱A上有n-1个圆盘,递归以上步骤;
- 当 desk = n-1时,需要将圆柱A上面的(n-1) - 1个圆盘,借助圆柱C移到圆柱B上(这里已经在开始和desk = n 的情况一样);
- 此时圆柱A上就只剩1个圆盘,则直接从圆柱A移动到圆柱C;
- desk = n-1时,先将圆柱B上面的(n-1) - 1个圆盘,借助圆柱C最终移到圆柱A上;
- 此时圆柱A上有(n-1) - 1个圆盘,递归以上步骤;
错误代码分析
public class TowerOfHanoi {public static void hanoi(int n, char posA, char posB, char posC) {// hanoi(圆盘个数,参数1,参数2,参数3)// 参数1表示起始位置、参数2表示中转位置、参数3表示终止位置if(n == 1) {move(posA, posC);return; // 递归一定要return}// 这一步就是将 圆柱A 上的 n-1个 圆盘// 借助圆柱C 移动到 圆柱B上hanoi(n-1, posA, posC, posB);// 将圆柱A上剩下的一个移到圆柱C上move(posA, posC);// 将 圆柱B 上的所有圆盘 借助圆柱C 移到圆柱A上hanoi(n-1, posB, posC, posA); // 这里是错的}public static void move(char pos1, char pos2) {System.out.println(pos1 + "->" + pos2);}public static void main(String[] args) {hanoi(3, 'A', 'B', 'C');}
}
正确递归分析
- 当desk = n个圆盘时,需要将圆柱A上面的n-1个圆盘,借助圆柱C最终移动到圆柱B上;
- 此时圆柱A上就只剩1个圆盘,则直接从圆柱A移动到圆柱C;
- 将圆柱B上的n-1个圆盘,借助圆柱A最终移动到圆柱C上;
- 此时圆柱B上就只剩一个圆盘,则直接从圆柱B移动到圆柱C;

正确代码分析
public class TowerOfHanoi {public static void hanoi(int n, char posA, char posB, char posC) {// hanoi(圆盘个数,参数1,参数2,参数3)// 参数1表示起始位置、参数2表示中转位置、参数3表示终止位置if(n == 1) {move(posA, posC);return; // 递归一定要return}// 这一步就是将 圆柱A 上的 n-1个 圆盘// 借助圆柱C 移动到 圆柱B上hanoi(n-1, posA, posC, posB);// 将圆柱A上剩下的一个移到圆柱C上move(posA, posC);hanoi(n-1, posB, posA, posC);}public static void move(char pos1, char pos2) {System.out.println(pos1 + "->" + pos2);}public static void main(String[] args) {hanoi(3, 'A', 'B', 'C');}
}相关文章:
【Java】汉诺塔
汉诺塔 汉诺塔(Tower of Hanoi)(河内塔):把圆盘从下面开始按大小顺序重新摆放到另一根柱子上,并且小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 汉诺塔规则 disk表示圆盘数一次只…...
Java实现对Html文本的处理
1.引入jsoup <dependency><groupId>org.jsoup</groupId><artifactId>jsoup</artifactId><version>1.8.3</version> </dependency> 2. html示例 示例代码: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1…...
Vue项目创建与启动(2023超详细的图文教程)
目录 一、下载node.js 二、下载vue-cli与webpack插件 三、项目初始化(项目配置详细信息) 四、项目启动 五、Vue项目工程结构(扩展知识) 一、下载node.js 1.检测是否已经安装过node.js 打开控制台,输入 npm -v如果有会显示对应版本 如果没有会显示…...
EtherCAT主站读取从站EEPROM抓包分析
0 工具准备 1.EtherCAT主站 2.EtherCAT从站(本文使用步进电机驱动器) 3.Wireshark1 抓包分析 1.1 报文总览 本文让主站去读取从站1字地址为0的EEPROM数据内容,主站读取从站EEPROM数据内容使用Wireshark抓包如下: 1.2 EEPROM读…...
Elasticsearch 8.X 如何生成 TB 级的测试数据 ?
1、实战问题 我只想插入大量的测试数据,不是想测试性能,有没有自动办法生成TB级别的测试数据?有工具?还是说有测试数据集之类的东西?——问题来源于 Elasticsearch 中文社区https://elasticsearch.cn/question/13129 2…...
汽车标定技术(四)--问题分析:多周期测量时上位机显示异常
目录 1.问题现象 2.数据流分析 3.代码分析 3.1 AllocDAQ 3.2 AllocOdt 3.3 AllocOdtEntry 4.根因分析及解决方法 4.1 根因分析 4.2 解决方案 1.问题现象 在手撸XCP代码时, DAQ的实现是一大头痛的事情。最初单周期实现还好一点,特别是…...
Flink SQL时间属性和窗口介绍
(1)概述 时间属性(time attributes),其实就是每个表模式结构(schema)的一部分。它可以在创建表的 DDL 里直接定义为一个字段,也可以在 DataStream 转换成表时定义。 一旦定义了时间…...
Tomcat免安装版修改标题名称和进程
tomcat免安装版启动后闪退问题 问题描述 在官网下载的tomcat免安装版的你安装完环境后发现启动闪退,tomcat启动依赖环境是JDK,所以需要tomcat对应版本的JDK支持。 tomcat8官网下载地址:https://tomcat.apache.org/ JDK环境官网下载地址&…...
vim搜索、替换tab
bibtex 中的缩进可能不一致,强迫症犯了想将: 缩进空格改 tab;行首的多个 tab 改为单个 参考 [1],空格换 tab 可以: :set noexpandtab :%retab!行首的多个 tab 换单个: :%s/^\t\/\t/gReferences Replac…...
一文读懂ARM安全性架构和可信系统构建要素
一文读懂ARM安全性架构和可信系统构建要素 所谓可信系统(trusted system),即能够用于保护密码和加密密钥等资产(assets)免受一系列的可信攻击,防止其被复制、损坏或不可用(unavailable…...
Voice vlan、ICMP、单臂路由、mux-vlan
目录 一,Voice VLAN Voice vlan配置命令 一,问:已知网络中一台服务器的IP地址,如何找到这太服务器在哪台交换机的哪个接口上编辑 思路: 二,ICMP协议 三,ICMP案例分析编辑 四…...
TCP IP 网络编程(七) 理解select和epoll的使用
文章目录 理解select函数select函数的功能和调用顺序设置文件描述符设置监视范围及超时select函数调用示例 优于select的epoll基于select的I/O复用速度慢实现epoll时必要的函数和结构体epoll_createepoll_ctlepoll_wait基于epoll的服务器端 边缘触发和水平触发 理解select函数 …...
Linux accept和FD_xxx的使用
Linux socket accept功能的作用是在服务器端等待并接受客户端的连接请求。当有客户端尝试连接服务器时,服务器调用accept函数来接受该连接请求,并创建一个新的socket来与该客户端进行通信。 具体来说,accept函数被动监听客户端的三次握手连接…...
树结构及其算法-二叉运算树
目录 树结构及其算法-二叉运算树 C代码 树结构及其算法-二叉运算树 二叉树的应用实际上相当广泛,例如表达式之间的转换。可以把中序表达式按运算符优先级的顺序建成一棵二叉运算树(Binary Expression Tree,或称为二叉表达式树)…...
vue的rules验证失效,部分可以部分又失效的原因
vue的rules验证失效,部分可以部分又失效的原因 很多百度都有,但是我这里遇到了一个特别的,那就是prop没有写全,导致验证某一个失效 例子: 正常写法 el-form-item....多个省略<el-form-item label"胶币" prop"cost"><el-input v-model"form.…...
c#字符串转整数类型
将字符串转换为整数类型。为了方便,C#提供了一个内置的方法TryParse来实现这个功能 字符串(String):表示一串字符的数据类型。整数(Integer):表示不带小数点的数字。解析(Parsing&a…...
【LeetCode】118. 杨辉三角
118. 杨辉三角 难度:简单 题目 给定一个非负整数 *numRows,*生成「杨辉三角」的前 numRows 行。 在「杨辉三角」中,每个数是它左上方和右上方的数的和。 示例 1: 输入: numRows 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]示例…...
【Vue.js】Vue3全局配置Axios并解决跨域请求问题
系列文章目录 文章目录 系列文章目录背景一、部署Axios1. npm 安装 axios2. 创建 request.js,创建axios实例3. 在main.js中全局注册axios4. 在页面中使用axios 二、后端解决跨域请求问题方法一 解决单Contoller跨域访问方法二 全局解决跨域问题 背景 对于前后端分离…...
【车载开发系列】CRC循环冗余校验码原理
【车载开发系列】CRC循环冗余校验码原理 CRC循环冗余校验码原理 【车载开发系列】CRC循环冗余校验码原理一. CRC算法原理二. 生成多项式三. 多项式与其对应代码四. CRC码校验原理1)发送端2)接收端 五. CRC码原理方法1)发送端生成CRC码方法2&a…...
数据库实验:SQL的数据更新
目录 实验目的实验内容实验要求实验步骤实验过程总结 再次书接上文,sql基础的增删改查 实验目的 (1) 掌握DBMS的数据查询功能 (2) 掌握SQL语言的数据更新功能 实验内容 (1) update 语句用于对表进行更新 (2) delete 语句用于对表进行删除 (3) insert 语句用于对表…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...






