Explanation of hannotta problem

The article directories

• • 1. Source and application of Hannota
  • 2. Hanover Tower rules
  • 3. Hannotta algorithm analysis
  • 4. C language code

1. Source and application of Hannota

Legend has it that in ancient Indian temples, there was a game called Hanoi. The game is played on A copper plate device with three rods (numbered A, B and C), and 64 gold disks are placed from top to bottom on A rod (as shown below).

The goal of the game: move all the gold disks on rod A to rod C, and still keep the original order of stacking. Operation rule: only one plate can be moved at A time, and in the process of moving, the big plate should always be kept on the bottom of the three rods, and the small plate should always be on the top. The plate can be placed on any of the rods A, B and C during the operation.



\

2. Hanover Tower rules

3. Hannotta algorithm analysis

Algorithm analysis: n is the number of disks, A,B,C is the pillar given when n=1, just move the plate A – > C can move (A,C); When n > 1,

For the first move, the first N -1 on pillar A is moved to pillar B; (figure 1)



hanoi(n-1,A,C,B);

The second move directly moves the last one on pillar A to pillar C; (figure 2)



move(A,C);









For the third move, move n-1 columns from pillar B through pillar A to pillar C. (figure 3)



hanoi(n-1,B,A,C);











Algorithm overview:

















Hanoi function













The implementation of move function// Print the moving trace:



\

void move(char c1, char c2)  // The move function prints the path of the move
{
	printf("%c-->%c\n", c1, c2);	
}
Copy the code

\

4. C language code

#include  <stdio.h>

// Hannotta problem

void move(char c1, char c2)  // The move function prints the path of the move
{
	printf("%c-->%c\n", c1, c2);	
}

void hanoi(int n, char x, char y, char z)
{
	if (n == 1)   // Recursive cutoff conditions
	    move(x, z);
	else
	{
		hanoi(n - 1, x, z, y);  // Move n-1 plates from pillar X to pillar Y with the help of pillar Zmove(x, z); Move the remaining disk on pillar X to pillar Z1, y, x, z);  // Move n-1 disk from y column to Z column by means of X column}}int main(a)
{
	int n = 0;
	printf("Please enter the initial number of disks:");
	scanf("%d",&n);
	hanoi(n, 'A'.'B'.'C');
	return 0;
}
Copy the code