Shulou(Shulou.com)06/01 Report--

This article will explain in detail how Java analyzes the problem of the Tower of Hanoi. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

I. the source of the problem of the Tower of Hanoi

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

Second, problem analysis starts with simple questions.

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

A plate.

A-> C

In the case of only one plate, we can directly move the plate from pillar A to pillar C.

Need to move once.

Two plates.

When there are two plates, we can also do this in the following ways:

A-> BA-> CB-> C

Need to move 3 times

1. A-> B

2. A-> C

3. B > C

Three plates

When there are three plates, move as follows:

A-> CA-> BC-> BA-> CB-> AB-> CA-> C.

It needs to be moved 7 times.

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 three plates.

When there are four plates, the problem is already very complicated.

Law derivation

1 plate moved 1 time

2 plates moved 3 times

3 plates moved 7 times

……

N plates moved 2 ^ N-1 times

Then 64 plates need to be moved 2 ^ 64-1 times.

Third, solve the problem

We can solve this problem by recursion and get the right way to move.

How do I move if there are N plates?

Overall thinking

We can first move the N-1 plate from the A column to the B column with the help of the C column, then move the remaining plate from the A column to the C column, and then move the N 1 plate on the B column to the C column with the help of the A pillar. The movement of all the columns is completed (the specific process of moving in the middle will not be discussed for the time being)

Upper code

Public static void hanoi (int num, String src, String help, String dest) {if (num = = 1) {/ / directly move System.out.print (src + "- >" + dest + "") when there is only one plate; / / move a plate from the source post to the target post} else {hanoi (num-1, src, dest, help) / move n-1 plates from the source column to the auxiliary column System.out.print (src + "- >" + dest + "") with the help of the target column; / / move a plate from the source column to the target column hanoi (num-1, help, src, dest) / / move n-1 plates on the auxiliary post to the target column with the help of the source column}} public static void main (String [] args) {hanoi (3, "A", "B", "C");}

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

This is a two-way recursion.

Running result:

This successfully completed the movement of the plate.

Can the Brahmin accomplish the task of Brahma? how long will it take to move 64 plates?

Here we assume that Brahmin people are so smart that they can directly know the correct way to move without thinking. It takes a second to move a plate, moving it all the time.

The 2 ^ 64-1 second is converted to about 5849 4241 7355 (584.942 billion years), while the Earth has existed for only 4.5 billion years, and the life expectancy of the solar system is said to be tens of billions of years. 584.942 billion years have passed, not to mention the solar system and the Milky way, at least all life on Earth, including the Vatican Pagoda and temples, has long gone up in smoke.

Related prophecy

It is predicted that the universe will be destroyed by lightning in an instant when this is done. Some people also believe that the Brahmin is still moving the disc all the time.

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

The core frequency of my computer is 2.90GHz, that is, 2.9 billion operations per second, so it takes about 201 years to move 2 ^ 64-1.

This is the end of the article on "how to analyze the Tower of Hanoi by Java". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.