搜索
首页Javajava教程Java如何分析汉诺塔问题

一、汉诺塔问题来源

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

Java如何分析汉诺塔问题

二、问题分析

从简单问题开始

直接拿64个盘子来想,可能会比较难,我们可以先从1个盘子开始看,如下图:

一个盘子

Java如何分析汉诺塔问题

A -> C 

Java如何分析汉诺塔问题

只有一个盘子情况下,我们可以直接将 A 柱子上面的盘子移到 C 柱子上

需要移动一次

两个盘子

当有两个盘子时,我们也可以通过下面方式实现:

A -> B     A->C     B->C

需要移动3次

Java如何分析汉诺塔问题

1.  A -> B

Java如何分析汉诺塔问题

2.  A -> C

Java如何分析汉诺塔问题

 3.  B -> C

Java如何分析汉诺塔问题

 三个盘子

 当有三个盘子时,移动步骤如下:

A -> C     A -> B     C -> B     A -> C     B -> A     B -> C     A -> C

共需要移动7次 

Java如何分析汉诺塔问题

 1.  A -> C

Java如何分析汉诺塔问题

2.  A -> B

Java如何分析汉诺塔问题

 3.  C -> B

Java如何分析汉诺塔问题

4.  A -> C

Java如何分析汉诺塔问题

 5.  B -> A

Java如何分析汉诺塔问题

 6.  B -> C

Java如何分析汉诺塔问题

 7.  A -> C

Java如何分析汉诺塔问题

这就完成了3个盘子的移动

当有 4 个盘子时,这个问题其实就已经很复杂了

规律推导

1个盘子      移动1次

2个盘子      移动3次

3个盘子      移动7次

……

N 个盘子    移动 2^N - 1 次

那么64个盘子就是需要移动 2^64 - 1 次

三、解决问题

我们可以通过递归来解决这个问题,获得正确的移动方式

如果有N个盘子该怎么移动呢?

整体思路

我们可以先将 N - 1 个盘子从 A 柱借助 C 柱移动到 B 柱,再将 A 柱剩下的一个盘子移动到 C柱,然后将 B 柱上的 N - 1 个盘子借助 A 柱移动到 C 柱,就完成了所有柱子的移动(中间具体移动过程暂不讨论)

上代码

public static void hanoi(int num, String src, String help, String dest) {
    if (num == 1) {     // 只有一个盘子的时候直接移动
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
    } else {
        hanoi(num - 1, src, dest, help);   // 将n - 1个盘子从源柱子借助目标柱子挪到辅助柱子
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
        hanoi(num - 1, help, src, dest);  // 将辅助柱子上n - 1个盘子借助源柱子挪到目标柱子
    }
}
public static void main(String[] args) {
    hanoi(3, "A", "B", "C");
}

这段代码中 src 是源柱子,help是辅助柱子,dest 是目标柱子

这是一个二路递归

运行结果:

Java如何分析汉诺塔问题

 这就成功完成了盘子的移动

四、婆罗门能否完成大梵天的任务

移动 64 个盘子需要多长时间

在这里我们假设婆罗门的人都非常聪明,不需要思考就直接能知道正确的移动方法,移动一个盘子需要一秒钟,一直不停的移

将2^64 - 1秒换算为年约为5849 4241 7355年(5849.42亿年),而地球存在至今不过45亿年,太阳系的预期寿命据说也就是数百亿年。真的过了5849.42亿年,不说太阳系和银河系,至少地球上的一切生命,连同梵塔、庙宇等,都早已经灰飞烟灭。

相关预言

有预言说,这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘

计算机移动64个盘子需要多长时间 ?

我的电脑核心频率为2.90GHz,也就是每秒钟运算 29 亿次,那么移动 2^64 - 1次需要的时间约为201年

以上是Java如何分析汉诺塔问题的详细内容。更多信息请关注PHP中文网其他相关文章!

声明
本文转载于:亿速云。如有侵权,请联系admin@php.cn删除
带你搞懂Java结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

Java数据结构之AVL树详解Java数据结构之AVL树详解Jun 01, 2022 am 11:39 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于平衡二叉树(AVL树)的相关知识,AVL树本质上是带了平衡功能的二叉查找树,下面一起来看一下,希望对大家有帮助。

一文掌握Java8新特性Stream流的概念和使用一文掌握Java8新特性Stream流的概念和使用Jun 23, 2022 pm 12:03 PM

本篇文章给大家带来了关于Java的相关知识,其中主要整理了Stream流的概念和使用的相关问题,包括了Stream流的概念、Stream流的获取、Stream流的常用方法等等内容,下面一起来看一下,希望对大家有帮助。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前By尊渡假赌尊渡假赌尊渡假赌

热工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Dreamweaver Mac版

Dreamweaver Mac版

视觉化网页开发工具

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )专业的PHP集成开发工具

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

功能强大的PHP集成开发环境

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用