[C language] recursively explain the tower of Hanoi problem

Preface

Hanoi , It's a puzzle toy originated from an ancient Indian legend . Vatican made three diamond pillars when he created the world , Stack on a column from bottom to top in order of size 64 A golden disk . Brahman ordered Brahman to rearrange the disc from below on another pillar in order of size . And stipulate , You can't enlarge a disc on a small disc , Only one disc can be moved between the three pillars at a time . When put 64 When the disc moves from the first stone pillar to the third stone pillar , The world will be destroyed .

And how long does it take for Brahmans to move the disc ？ It is difficult to calculate by ordinary methods .

Today, we will use the idea of recursion to calculate the number of movements of the tower of Hanoi and the moving steps of the tower of Hanoi ！

Hanoi Tower mobile diagram

The law of Hanoi Tower movement is that only one disc can be moved at a time , And the small market should be above the large market , Suppose that A Column has n Disc , Let's put n-1 A disk from A The column moves to B column , And then put the n A disk moves to C column , Finally, put n-1 A disk moves to C column .

Take the third-order Hanoi tower as an example ：

The number of Hanoi Tower moves

Use exhaustive methods , Calculate the number of movements of Hanoi Tower ：

Order	frequency	law
1	1	2^1-1
2	3	2^2-1
3	7	2^3-1
4	15	2^4-1
…	…	2^n-1

about n The number of times the tower of Hanoi moves ：

• step 1 The number of steps involved is n-1 The number of times a disc needs to move , We can regard its steps as f(n-1).
• step 2 The number of steps involved is 1.
• step 3 The number of steps and steps involved 1 be similar , We also regard its steps as f(n-1).

Then observe the number of movements of Hanoi Tower in the table , For the first-order Hanoi Tower, the number of moves is 1, For other orders, it is the number of Hanoi Tower moves in the previous order + 1 + The number of moves of Hanoi Tower in the previous stage .

It is not difficult to get a recursive expression ：f(n-1) + 1 + f(n-1) = 2 * f(n - 1) + 1

Moving steps conform to the idea of recursion , Code display ：

#include<stdio.h>
int hanoi_step(int n)
{
    
	if(n<=1)
		return 1;
	else
		return 2*hanoi_step(n-1)+1;
}
int main()
{
    
	int n = 0;
	scanf("%d",&n);
	int ret = hanoi_step(n);
	printf("%d\n",ret);
	return 0;
}

Running results ：

Printing of Hanoi Tower

Printing here refers to the steps of printing the movement of Hanoi Tower .

We can try to write 1-4 The moving steps of step Hanoi Tower ：

Order	step
1	A->C
2	A->B,A->C,B->C
3	A->C,A->B,C->B,A->C,B->A,B->C,A->C
4	A->B,A->C,B->C,A->B,C->A,C->B,A->B,A->C,B->C,B->A,C->A,B->C,A->B,A->C,B->C

We observe the moving steps , When only one disc is found, the moving steps are A->C; Two discs , by A->B,A->C,B->C.

So for n What about the tower of Hanoi , We deduce it ：

• hold n-1 A disk from A Move to B
• The first n A disk from A Move to C
• hold n-1 A disk from B Move to C

that n-1 How to make a disc from A Move to B Well ？

• hold n-2 A disk from A Move to C
• The first n-1 A disk from A Move to B
• hold n-2 A disk from C Move to B

alike , For the n-1 A disk from B Move to C, It can also be inferred that ：

• hold n-2 A disk from B Move to A
• The first n-1 A disk from B Move to C
• hold n-2 A disk from A Move to C

Through these deductions, we find , The movement of Hanoi tower can be expanded recursively , Then the above deduction steps , We can use it as a recursive step .

Ideas ： Definition A,B,C Three characters , Express A,B,C Three columns , Definition n Is the order , that n-1 That is, in the move step , Number of discs to be moved .
For the first-order tower of Hanoi , Just move it , For other orders , You need to expand recursively , by n The moving steps of step Hanoi Tower .

#include<stdio.h>
void hanoi_move(int n,char A,char B,char C)
{
    
	if(1==n)
	{
    
		printf("%c->%c\n",A,C);
	}
	else
	{
    
		hanoi_move(n-1,A,C,B);// take n-1 A disk from A Move to B
		printf("%c->%c\n",A,C);// Will be the first n A disk from A The column moves to C column 
		hanoi_move(n-1,B,A,C);// take n-1 A disk from B The column moves to C column 
	}
}
int main()
{
    
	int n = 0;
	scanf("%d",&n);
	hanoi_move(n,'A','B','C');
	return 0;
}

It may not be intuitive just through code , We take the third-order Hanoi tower as an example , Observe how recursion unfolds ：

Running results ：

Conclusion

Understand the moving steps and process of Hanoi Tower , We can also 64 Make an estimate of the time it takes to move the Golden Disc , Think of each move as a second , Then the time is ：2 ^ 64 - 1 = 18,446,744,073,709,551,615 second , Convert adult numbers , about 5800 In one hundred million, .

At this pace , At that time, it is also possible to destroy the world , It's just pathetic “ Tragic Brahman ” You need to move these discs (doge).

That's all C Language recursion solves all the contents of Hanoi Tower , If you feel anduin If it's well written , One click and three links, please ！

I am a anduin, a C Language beginners , See you next time ！