How 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

## 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

A -> C

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

1. A -> B

2. A -> C

3. B -> C

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

## 1. A -> C

##2. A -> B

## 3. C -> B

##4. A -> C

## 5. B -> A

6. B -> C

7. A -> C

This completes the movement of 3 plates

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

Rule 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 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!