当前位置：首页 > news >正文

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

news 2025/1/1 10:20:23

🔥博客主页🔥：【坊钰_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();}}