preface

The concept is introduced

1. Origin of hannotta problem

  • Hannott tower comes from a story in Indian legend. When God created the world, he made three diamond pillars. On one pillar, 64 gold disks were stacked from top to bottom.
  • God commanded the Brahmin to rearrange the disks on another pillar, starting from the bottom, in order of size. And provisions, in the small disc can not enlarge the disc, between the three pillars can only move a disc, can only move at the top of the disc.
  • It was prophesied that when this was done the universe would be destroyed in a flash. It is also believed that brahmins are still moving the disc all the time.
  • Of course, this legend is not credible, and today the Tower of Hanover exists more as a toy

2. What is the Hannotta problem?

  • In A word, the disk on pillar A in the figure below is moved to pillar C intact by certain rules (described in the section “Origin of the Hannott Tower Problem”)

The principle of interpretation

  • Let’s take the number of disks on pillar A N=4 as an example to explain the principle of hannott tower implementation
  • In the initial state, the disks on pillars A,B and C are shown in the figure below

  1. For the first step, we use the top 3 plates of pillar A as A “whole” (how?). Pillar C moves to pillar B, and the effect is shown below

2. In the second step, we move the bottom plate of pillar A to pillar C, and the effect is shown in the picture below3. In the third step, we use the three plates of Pillar B as a “whole” (similarly, how to use it?) When pillar A moves to pillar C, the effect is shown below4. After the above 3 steps, the 4-layer Hannotta problem is reduced to the 3-layer hannotta problem (the first step is treated as a whole of 3 plates). 5. In the fourth step, we move the two plates on the top of pillar A to pillar B as A “whole” with the help of pillar C, and the effect is shown in the picture below6. In the fifth step, we move the bottom plate of pillar A to pillar C, and the effect is shown in the picture below7. Step 6, we use the two plates of Pillar B as a “whole” (similarly, how to use it?). When pillar A moves to pillar C, the effect is shown below8. After the above 3 steps, the 3-layer Hannotta problem is reduced to the 2-layer hannotta problem (the first step is treated as a whole of 2 plates). 9. The 2-tier Hannott tower problem is much easier for you to solve than it is for you. I will not repeat it here. 10. Therefore, through the above steps, we can easily find that the implementation of Hannotta algorithm can be divided into three steps: * Move n-1 plates from A to B with the help of C; * Move the NTH plate from A to C; * Move n-1 plates from B to C with the help of A;

Results show

For more algorithm learning, please pay attention to my public number

instructions

  • In the public number to reply to the “algorithm source” to obtain the source code of ten classic algorithms
  • Reply “Algorithm books” in the public account to get the classic introduction algorithm books
  • Reply “data structure” in the public number to obtain data structure related source code