search
HomeJavajavaTutorialHow to analyze the Tower of Hanoi problem using Java

1. Source of the Tower of Hanoi problem

The Tower of Hanoi, also known as the Tower of Hanoi, is an educational toy originating from ancient Indian legends. When Brahma created the world, he made three diamond pillars. On one pillar, 64 gold discs were stacked in order of size from bottom to top. Brahma ordered the Brahmin to rearrange the disks on another pillar in order of size from the bottom. And it is stipulated that the disk cannot be enlarged on the small disk, and only one disk can be moved between the three pillars at a time

How to analyze the Tower of Hanoi problem using Java

## 2. Problem Analysis

Start with a simple question

It may be difficult to think about 64 plates directly. We can start with 1 plate, as shown below:

One plate

How to analyze the Tower of Hanoi problem using Java

A -> C

How to analyze the Tower of Hanoi problem using Java

If there is only one plate, we can directly move the plate on pillar A to pillar C

Need to move once

Two plates

When there are two plates, we can also achieve it in the following way:

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

Needs to move 3 times

How to analyze the Tower of Hanoi problem using Java

1. A -> B

How to analyze the Tower of Hanoi problem using Java

2. A -> C

How to analyze the Tower of Hanoi problem using Java

3. B -> C

How to analyze the Tower of Hanoi problem using Java

Three plates

When there are three plates, the moving steps are as follows:

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

Needs to be moved 7 times in total

How to analyze the Tower of Hanoi problem using Java## 1. A -> C

##2. A -> BHow to analyze the Tower of Hanoi problem using Java

## 3. C -> B

How to analyze the Tower of Hanoi problem using Java

##4. A -> C

How to analyze the Tower of Hanoi problem using Java

## 5. B -> A

How to analyze the Tower of Hanoi problem using Java

6. B -> C

How to analyze the Tower of Hanoi problem using Java

7. A -> C

How to analyze the Tower of Hanoi problem using Java

This completes the movement of 3 plates

When there are 4 plates, This problem is actually very complicated.

How to analyze the Tower of Hanoi problem using JavaRule derivation

1 plate Move 1 time

2 plates Move 3 times

3 plates Move 7 times

......

N plates move 2^N - 1 time

Then 64 plates need to be moved 2^64 - 1 time

3. Solve the problem

We can solve this problem through recursion and obtain the correct way of moving

How to move if there are N plates?

Overall idea

We can first move N - 1 plates from column A to column B with the help of column C, then move the remaining plate from column A to column C, and then move N - 1 plates on pillar B are moved to pillar C with the help of pillar A, thus completing the movement of all pillars (the specific moving process in the middle will not be discussed for now)

上码

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");
}

this paragraph In the code, src is the source pillar, help is the auxiliary pillar, and dest is the target pillar.

This is a two-way recursion.

Running results:

This successfully completed the movement of the plates

4. Can Brahman complete the task of Brahma?

How to analyze the Tower of Hanoi problem using JavaHow long does it take to move 64 plates

Here we assume Brahmins are very smart and can directly know the correct way to move without thinking. It takes one second to move a plate, and they keep moving

Converting 2^64 - 1 second into years is about 5849 4241 7355 years (584.942 billion years). The earth has only existed for 4.5 billion years, and the expected lifespan of the solar system is said to be tens of billions of years. It has really been 584.942 billion years. Not to mention the solar system and the Milky Way, at least all life on the earth, including the Vatican Towers, temples, etc., have long been wiped out.

Related prophecies

There is a prophecy that when this thing is completed, the universe will be destroyed in a flash. Some people also believe that Brahmins are still moving the disks all the time.

How long does it take for a computer to move 64 plates?

The core frequency of my computer is 2.90GHz, which is 2.9 billion operations per second, so the time required to move 2^64 - 1 time is about 201 years

The above is the detailed content of How to analyze the Tower of Hanoi problem using Java. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:亿速云. If there is any infringement, please contact admin@php.cn delete
带你搞懂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的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

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

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

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

java中封装是什么java中封装是什么May 16, 2019 pm 06:08 PM

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

归纳整理JAVA装饰器模式(实例详解)归纳整理JAVA装饰器模式(实例详解)May 05, 2022 pm 06:48 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

mPDF

mPDF

mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),