马鞍山网站建设公中淼建设工程有限公司网站
🔥博客主页🔥：【 坊钰_CSDN博客 】
欢迎各位点赞👍评论✍收藏⭐
目录
1. 题目
2. 分析
2.1 图解
2.2 代码解析
3. 完整代码
3.1 运行截图
4. 小结
1. 题目
汉诺塔问题是一个经典的递归问题，源自一个古老的印度传说。在这个问题中，我们有三根柱子和一系列不同大小的圆盘，这些圆盘最初按大小顺序堆叠在一根柱子上。目标是将所有圆盘移动到另一根柱子上，遵循两个规则：一次只能移动一个圆盘，且在移动过程中较大的圆盘不能放在较小的圆盘上面。
2. 分析
2.1 图解
首先我们不能一口吃下去，我们要一步一步来看
- 如果只有一个盘子 （n == 1）
那么直接 A --> C 就行了
- 如果只有两个盘子 （n == 2）
A --> B A --> C B --> C
这是基本步骤，显然发现不了什么规律
- 如果只有三个盘子 （n == 3）
都存在特殊情况:（n - 1）个盘子在 B 柱子上，最大的盘子在 C 柱子上，把（n - 1）个盘子看作整体（借助 A 柱子）放到 C 柱子上
- 如果只有四个盘子 （n == 4）
不管怎么移动， 都存在特殊情况:（n - 1）个盘子在 B 柱子上，最大的盘子在 C 柱子上，把（n - 1）个盘子看作整体（借助 A 柱子）放到 C 柱子上
那这时候，递归规律就出来了
一句话：先把 A 柱子上（n - 1）个盘子放在 B 柱子上，在将 A柱子上第 n 个盘子放在 C 柱子上，然后将 B 柱子上（n - 2）个盘子放在 A 柱子上，在讲 B 柱子上第 （n - 1）个盘子放在 C 柱子上.....依次递归下去
2.2 代码解析
先定义一个方法用来打印运动过程
public static void move(char p1, char p2) {System.out.print(p1 + " -> " + p2 + " ");}在定义方法进行递归
public static void Htower(int n, char pos1, char pos2, char pos3) {if(n == 1) {move(pos1, pos3);return ;}Htower(n - 1, pos1, pos3, pos2);move(pos1, pos3);Htower(n - 1, pos2, pos1,pos3);}这里进行代码解释
- pos 1 ，pos 2 ，pos 3 分别代表 A B C （柱子）
- if() 语句表示有一个盘子的话，只需盘子运动一次即可
- pos 1 ：盘子的起始柱子
- pos 2 ：盘子的借助的柱子（中转位置）
- pos 3 ：盘子的终点位置（最终位置）
- 第六行代码意思是-> 先将 A 柱子的（n - 1）个盘子借助 C 柱子移到 B 柱子上
- 第七行代码意思是-> 在将 A 柱子剩的一个最大的盘子移到 C 柱子上
- 第八行代码意思是->将 B 柱子的（n - 1）个盘子借助 A 柱子移到 C 柱子上
3. 完整代码
public class Test {public static void move(char p1, char p2) {System.out.print(p1 + " -> " + p2 + " ");}/** pos1:起始位置* pos2:中转位置* pos3:终点位置* */public static void Htower(int n, char pos1, char pos2, char pos3) {if(n == 1) {move(pos1, pos3);return ;}Htower(n - 1, pos1, pos3, pos2);move(pos1, pos3);Htower(n - 1, pos2, pos1,pos3);}public static void main(String[] args) {// 用多组数据检测Htower(1,'A', 'B', 'C');System.out.println();Htower(2,'A', 'B', 'C');System.out.println();Htower(3,'A', 'B', 'C');System.out.println();Htower(4,'A', 'B', 'C');System.out.println();Htower(5,'A', 'B', 'C');System.out.println();}}3.1 运行截图
4. 小结
以上就是对该题的了解，具体还需宝子们去实践，如果觉得该博客对你有用的话，希望一键三连，点个关注不迷路，谢谢支持！