Brief introduction of Hannotta

Recently when I was looking at data structure and algorithm, I encountered a very interesting problem — Hannotta problem.

Here’s how Baidu Baike defines hannotta’s rules:

The problem with the Tower of Hannot (also known as the Tower of Hanoi) is a puzzle toy from an old Indian legend. Mahama made three diamond pillars when he created the world, and on one pillar were stacked 64 gold disks in ascending order of size. Mahama ordered the Brahmin to rearrange the disks on another pillar, starting from below, in order of size. It is also stipulated that the disk cannot be enlarged on the small disk and that only one disk can be moved at a time between the three columns.

Uh, okay, it’s a little long winded. In short, move the plates one at a time between the three pillars, and make sure that the top plate is smaller than the bottom plate at each step, so that all the plates are moved from the leftmost pillar to the rightmost pillar.

I found a little game that I could play and experience the process. Trust me, you won’t get past level five! Hey hey, but play again come to see, I am how to give you to do game guide (cheating).

Address: www.4399.com/flash/10950…

I’m sure a lot of kids struggle with this problem when they learn recursion. Don’t worry, you are not alone, I saw this for the first time also confused, what the hell, so complicated. Now I’m going to show you the whole process, graphically, to help you understand the idea of solving this problem recursively.

Diagram of Hannott’s Tower

We went from simple to complex step by step. For convenience, I’ll call the pillars A, B, and C from left to right. The numbers on the plate increase from top to bottom.

A plate

When there’s only one plate, it’s easier. As shown in the figure, it only takes one step to move the first plate directly from A to C.

The two plates

When two plates, it is also relatively simple, as shown in the picture below, which can be completed with the help of pillar B.

This process can be expressed as:

I'm going to move the first plate from A to B and the second plate from A to C and the first plate from B to CCopy the code

Three plate

Three plates, it’s a little bit more complicated, but we can usually figure it out in our head.

Let's move the first plate from A to C let's move the second plate from A to B let's move the first plate from C to B let's move the third plate from A to A let's move the first plate from A to CCopy the code

N the plate

Dang dang dang, now to the fourth level, I believe that some friends have begun to feel difficult, through the calculation is not easy. If you can’t figure it out, we’ll use a computer to figure it out for us.

In fact, from the previous three examples, we can see that the plate movement is regular.

Have you noticed carefully that in every step of the plate movement, there is always A step, is the biggest plate below, from A to C. For example, two plates, the second plate moves from A to C, and three plates, the third plate moves from A to C.

Observe carefully, take the three plates as an example, move the third plate from A to C. In fact, the first and second plates are already placed in order, that is, they are placed together on pillar B in the middle.

Therefore, we can abstract this action out and see the plates as a whole, except for the bottom plate. In this case, the whole process is no different than two plates moving. There are only three steps. I’ll take four plates. Watch the following animation,

The whole process can be expressed as:

Move plates 1,2, and 3 as A whole from A to B (thought to be moved by pillar C), move the 4th plate from A to C (without additional pillar), and move plates 1,2, and 3 as A whole from B to C (with pillar A).Copy the code

But that’s just how we abstract it out. We’re not allowed to move as a whole.

Well, if I split 1,2, and 3, it’s just three plates moving. It’s perfectly possible to view 1,2 as a whole and move together, and 3 as a single move, also in three steps. And then you break it down again until you have the last plate, and you’re done.

So, as you can see, this process of breaking it down is a process of recursion. And every time I recurse, I can view the first plate up to the n-first plate as a whole. Each recursion is a three-step move from the current column to the target column with the help of another column. Look at the code,

public class HanioTest { public static void main(String[] args) { int n = 4; char a = 'A',b = 'B',c = 'C'; hanio(n,a,b,c); } /** ** @param n Total plates to move * @param a plate to move * @param b to move * @param c to move to the target column */ public static void Hanio (int n,char a, char b, char c){if(n == 1){move(n,a,c); }else{// three steps, pay attention to the position of a, B,c changes //1. Take n-1 plates as A whole and move them from A to B by C hanio(n-1, A, C, B); Move (n, A, C); // move(n, A, C); //3. Then move the whole plate from B to C hanio(n-1, B, A, C) with help of A; }} public static void move(int n, char a, char b){system.out.println (" + n + +"); }}Copy the code

If you are smart, you can check that the code execution is consistent with your movement if you have completed the fourth level of the game.

Fifth, if YOU can work it out in your head without the help of the program, I can only say that YOU are too good, I am convinced by YOU, I admire YOU.

What about level six and level seven?

conclusion

Going back to the beginning, Baidu Baike said it was going to move 64 gold disks, OMG, if anyone could figure that out manually, that would be really amazing (but who would be so boring, haha).

If you’re interested, try running 64 slices through the program. I’m guessing even if you have a good machine, it will take a long time…

Tips: It’s not my fault the machine blew up

If this article is useful to you, please like it, comment on it, and retweet it.

Learning is boring and interesting. I am “Misty rain sky”, welcome to pay attention to, can be the first time to receive the article push.