C language: recursive function to realize Hanoi Tower

If you are not familiar with recursion, you can learn about it in the previous articles .

Hanoi （Hanoi） What is it? ？

                                    

A simple Hanoi tower is shown in the figure above , There are three placement points , The placement must follow the rules of small up and large down , In turn 1 All the objects in the are placed in 3 in . For example, there is 4 A placer , If the A All the objects placed on the are moved to C On , The specific steps are ：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.

that ,C How does language realize the tower of Hanoi ？

The first step is to determine the starting position 、 Transfer location 、 Destination location , In the first place A It's the starting position ,B It's a transit location ,C Is the destination location , The function of these three positions will be changed all the time when moving the object block , To achieve the ultimate goal .

The basic idea of Hanoi tower is ：

The first stage ： take n-1 A block （ That is, except for the bottom block ） After a series of stacking （ Here we can use the recursive method to realize ）, Finally, put it on the transfer position , Then put the remaining blocks at the starting position on the destination position , Here's the picture ：

                   ——>                   

  The above series of stacking means ： With A Is the starting position ,C It is a transit location ,B For the purpose of location , It's equivalent to putting C Think of it as an intermediate repository , To help here n-1 Put a block in B Go inside .

The second stage ： And then you'll find out , After the change, the form of Hanoi tower is the same as before , If you put B As a starting position ,A It's a transit location ,C Is the destination location . You can always recurse according to the above method , Here's the picture ：

                ——>                         

And so on …… Finally, all the objects can be removed from A Moved to C.

See below for the specific code （ Note the following in the code ）：

//C Language implementation of Hanoi Tower 
#include <stdio.h>

void move(char p1, char p2)
{
	printf("%c->%c  ", p1, p2);
}

//n: Number   pos1: The starting position   pos2: Transfer location   pos3: Destination location 
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		move(pos1, pos3);
	}
	else
	{
		Hanoi(n - 1, pos1, pos3, pos2);
		move(pos1, pos3);
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}

int main()
{
	Hanoi(1, 'A', 'B', 'C');
	printf("\n");
	Hanoi(2, 'A', 'B', 'C');
	printf("\n");
	Hanoi(3, 'A', 'B', 'C');
	printf("\n");
	Hanoi(4, 'A', 'B', 'C');
	printf("\n");
	return 0;
}

Pay attention to point one ： In code n It's not worth much , Because the number of moves varies with n The increase of is exponential .

Pay attention to point two ：n by 1 It's almost time to reach the minimum unit （ That is, the bottom ）, There is no need to use recursion ;n For more than 1 The value of , Need to recurse to 1 To carry out .

Pay attention to three ： The first stage uses recursion to express the above n-1 Move layers all to B in ; The second stage uses recursion to express B Move all to C in .

In this way, the tower of Hanoi can be simply completed , This code is not the best approach , But it's easy to understand . Recursion is not used very much in practice , But you should also understand the code and write the basic code of recursive functions such as Hanoi tower .