OJ_Tower of Hanoi

I still remember the day when I was sitting in the classroom of Mr.Wang(Wang Hexing is a handsome teacher)listening him to talking about the question–Tower of Hanoi, and I still remember the confusion in my little head.


Just as the saying goes: The man who comes out to play is always have to pay back. I finally met it on NEUQ_oj.

I think it’s time for me to know what the Tower of Hanoi is and find out how to solve it.

The question:

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

Analysis

It’s obviously that we should use the recursive function, but the question is ‘How’?

First, let’s find some laws in the question.Look at the pictures:

• The number of discs is one
  
  

---

• The number of discs is two

In this part, we use the pillar B as a transformer station, what? transformer station? Don’t worry, We will explain the usage of it.

---

• The number of discs is three

First we should know our target. We want to move the all pillars to pillar C. It’s obvious that it is impossible to make it at once. So we should find a transformer station. We can move the green one and blue one to pillar B.

So we can use the way in the situation of two discs to move green and blue to B, and then move the red one to C

The last thing we should do is to use the same way of situation of two discs and think pillar A as a transfer station

---

Code

We have analyze the basic idea of Hanoi, so it is time for us to explore the way to achieve it in code.

As I have said on the begin of the passage, we should use the recursive fuction, because it’s the simplest way to solve the question.

the parameter is four:

• the number of discs
• the pillar that the discs you want to move exist.
• the transfer station
• the target pillar at every step

void hanoi(int n, char A, char B, char C){
    if(n == 1){
        printf("Move sheet %d from %c to %c\n",n,A,C);
    }else{
        	//as we can see, if we want get the result of n,
		//we should move n - 1 first, so here we need to
		//use the way of recursion
		
		//here we need to move the n - 1 smaller discs from 
		//A to B
		hanoi(n-1, A,C,B);

		//here we move the left biggest one from A to C
		printf("Move sheet %d from %c to %c\n",n,A,C);

		//here we move the n - 1 samller discs from B to C
		hanoi(n-1, B, A, C);
    }
}

Conclusion

If there is any error, please contract with me and teach me how to correct it or I can try my best to correct it myself. I am just a vegetable chicken.

Please bear with me.
o((⊙﹏⊙))o.

/*
*      
*          ┌─┐       ┌─┐
*       ┌──┘ ┴───────┘ ┴──┐
*       │                 │
*       │       ───       │
*       │  ─┬┘       └┬─  │
*       │                 │
*       │       ─┴─       │
*       │                 │
*       └───┐         ┌───┘
*           │         │
*           │         │
*           │         │
*           │         └──────────────┐
*           │                        │
*           │                        ├─┐
*           │                        ┌─┘    
*           │                        │
*           └─┐  ┐  ┌───────┬──┐  ┌──┘         
*             │ ─┤ ─┤       │ ─┤ ─┤         
*             └──┴──┘       └──┴──┘ 
*                 神兽保佑 
*                 代码无BUG! 
*/