汉诺塔移动

简介: 汉诺塔

 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。[1]大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

image.gif编辑

游戏规则:

将A上的n个盘子移动到C上,在移动的过程中,大盘子不能盖在小盘子上面。

问题分析:

此游戏我们可以通过递归来完成,抓住递归的本身语义,我们知道递归最终结束步骤是将最后一个盘子从A移到C上, 子问题为将除过最下面的盘子移动到B上,将最下面的盘子一步移动到C上,再将剩下的n-1个盘子移动到C上。

image.gif编辑

代码实现:

public static void main(String[] args) {
        int n = 3;
        hanoiTower(n,'A','B','C');
    }
    // 此时需要将A上的n个盘子移动到C上,B作为辅助
    public static void hanoiTower(int n,char A,char B,char C) {
        // 1.base case。不借助任何其他的移动,一步就可到位的条件是啥?n取什么值时?
        // 当n == 1时,说明此时A上就一个盘子,一步到位,直接将A上的这一个盘子移动到C上即可
        if (n == 1) {
            move(1,A,C);
            return;
        }
        // 此时n >= 2
        // 先将A上的这n - 1个盘子移动到B上,C作为辅助
        hanoiTower(n - 1,A,C,B);
        // 此时A上就只剩下最大的那个n盘子,一步到位,将最大的盘子移动到C上即可
        move(n,A,C);
        // 将B上的这n - 1个盘子从B移动到C,A作为辅助
        hanoiTower(n - 1,B,A,C);
    }
    // 将编号为n的盘子从source-> dist塔上
    private static void move(int nDisks, char sourceTower, char distTower) {
        System.out.println("编号为" + nDisks + "的盘子从" + sourceTower + "->" + distTower);
    }

image.gif


目录
打赏
0
0
1
0
15
分享
相关文章
【数据结构】堆的创建
文章目录 一、基于大堆的上下调整 1.向上调整 (1)解决措施: (2)代码实现 (3)测试 2.向下调整 (1)解决措施: (2)代码实现
在Linux中,如何配置和使用fail2ban来防止暴力攻击?
在Linux中,如何配置和使用fail2ban来防止暴力攻击?
(“拨”取数字的典例:N位水仙花数判断及水仙花数变种)
这篇内容介绍了如何判断和生成水仙花数,水仙花数是一个n位数,其各位数字的n次方之和等于该数本身。文章首先回顾了"拨数"的概念,然后通过实例展示了如何判断三位水仙花数,并将其推广到任意位数的水仙花数。作者提供了详细的解题思路和代码示例,强调了解决这类问题时要慢下来,分步骤分析问题。最后,文章还探讨了一个水仙花数的变种问题,即数字拆分后乘积之和等于原数的情况。
1010 0
python基础篇:什么是装饰器?装饰器有什么用?
python基础篇:什么是装饰器?装饰器有什么用?
94 4
python基础篇:什么是装饰器?装饰器有什么用?
使用Go语言开发高性能服务的深度解析
【5月更文挑战第21天】本文深入探讨了使用Go语言开发高性能服务的技巧,强调了Go的并发性能、内存管理和网络编程优势。关键点包括:1) 利用goroutine和channel进行并发处理,通过goroutine池优化资源;2) 注意内存管理,减少不必要的分配和释放,使用pprof分析;3) 使用非阻塞I/O和连接池提升网络性能,结合HTTP/2和负载均衡技术;4) 通过性能分析、代码优化、缓存和压缩等手段进一步提升服务性能。掌握这些技术能帮助开发者构建更高效稳定的服务。
【消息中间件】你还不会在Docker下安装RocketMQ吗?
在学习消息中间件-RocketMQ之前,先来准备一下学习环境的搭建,下面分享一下Docker环境中安装RocketMQ和RocketMQ-Console。
干货 | Python调用百度地图API获取各点的经纬度信息(两种方式)
干货 | Python调用百度地图API获取各点的经纬度信息(两种方式)
2497 0
干货 | Python调用百度地图API获取各点的经纬度信息(两种方式)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问