文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Java用递归方法解决汉诺塔问题详解

2024-04-02 19:55

关注

前言

博主之前有写过关于递归问题的思维模式:

递归的思路

下面将用这种思维模式来求解经典汉诺塔问题。

一、问题描述

汉诺塔(又称河内塔)问题是源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。

大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。

并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

问应该如何操作?

玩法如下:

1.有三根杆子A,B,C。A杆上有若干碟子

2.每次移动一块碟子,小的只能叠在大的上面

3.把所有碟子从A杆全部移到C杆上

在这里插入图片描述

在这里插入图片描述

二、问题分析

(两步直接解决问题)

1.第一步(先思考终止条件)

考虑n=1的情况:

在这里插入图片描述

只需要把这个块从A移到C即可。

在这里插入图片描述

2.第二步(宏观看待整个问题)

当n>=2时,把如图蓝色框框想象成上面的n-1个块(我把它称为一堆块),红色框框表示的是最下面的一块(命名为底块),这样问题可以简化为如图所示的三步。

在这里插入图片描述

第一步:先把上面的一堆块 从A(起始柱子)移动到B(目标柱子)上,在这个过程中,C(辅助柱子)起到中转的作用(因为题目要求移动的过程中,小盘子要保证在大盘子上面)

第二步:把最下面的红色大块直接从A(起始柱子)移动到C(目标柱子)。这里注意,这一步的目标柱子和第一步的不一样。

第三步:把上面的一堆块从B(起始柱子)移动到C(目标柱子)上,A(辅助柱子)起到中转的作用。

三、解决方案

那么问题就很简单了,递归的代码就分为两部分:终止条件和递归逻辑。

上一篇博客讲到,我们思考递归问题的时候,可以直接把这个大问题拆解成很多个子问题,想象这个功能别人已经写好了(就是这个递归函数),我们做不到的功能直接调用这个递归函数就可以(注意逻辑)。

public class Recursion {
    public static void main(String[] args) {
        int n = 3;
        hanoiTower(n,'A','B','C');
    }

    
    public static void hanoiTower(int nDisks,char A,char B,char C) {
        // 边界
        if (nDisks == 1) {
            // 直接一步到位,用不到B,A上的这一个盘子从A -> C
            move(nDisks,A,C);
            return;
        }
        // n >= 2,核心步骤1,先把顶上的 n -1个小盘子从A -> B,C作为辅助
        hanoiTower(nDisks - 1,A,C,B);
        // 核心步骤2.此时A上就剩下第n个盘子,一步到位将最大的这个盘子一次移动到C
        move(nDisks,A,C);
        // 核心步骤3.此时再把B上的这n-1个盘子从B -> C,A作为辅助
        hanoiTower(nDisks - 1,B,A,C);
    }

    
    public static void move(int nDisks, char sourceTower, char destTower) {
        System.out.println("编号为"+nDisks+"的盘子正在从"+sourceTower+"->"+destTower);
    }

四、示例

n=3的时候

在这里插入图片描述

在这里插入图片描述

以上就是用宏观思维去进行递归求解汉诺塔的方法,希望大家多多支持哟(●ˇ∀ˇ●)

到此这篇关于Java用递归方法解决汉诺塔问题详解的文章就介绍到这了,更多相关Java 汉诺塔内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯