【Java SE 题库】递归的魅力之--＞ 汉诺塔问题

 🔥博客主页🔥：【 坊钰_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. 小结

以上就是对该题的了解，具体还需宝子们去实践，如果觉得该博客对你有用的话，希望一键三连，点个关注不迷路，谢谢支持！