Tower of Hanoi classic recursion problem (C language implementation)

Hanoi —— Classical recursion problem （c Language implementation ）

The problem background

The tower of Hanoi problem is a classic one . Hanoi （Hanoi Tower）, Also known as the river tower , From an old 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 , anytime , You can't zoom in on a small disk , And you can only move one disc at a time between the three pillars . Ask how to operate ？

Problem analysis

Ideas ：
1. The language used ：C Language
2. The compiler used ：vs2019
3. Reference books ： Tanhaoqiang Fourth Edition
4. Main knowledge used ： Recursion of a function
5. The idea of code implementation is mainly divided into three steps ：
Suppose a total of... Needs to be moved n null
1. take A On the column n-1 With the help of C The column moves to B column
2. take A The last plate left on the column moves to C column
3. take B On the column n-1 With the help of A The column moves to C column

Code implementation

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

void move(int x, int y)
{
    
	printf("%c->%c\n", x, y);
}
void hanoi(int n, char a, char b, char c)
{
    
	if (n == 1)
	{
    
		move(a, c);
	}
	else
	{
    
		hanoi(n - 1, a, c, b);// take A On the seat n-1 With the help of C The seat moves to B seat 
		move(a, c);// take A The last plate on the seat moves to C seat 
		hanoi(n - 1, b, a, c);// take B On the seat n-1 With the help of A The seat moves to C seat 
	} 
}
//move Real participation in hanoi The formal parameters in the function correspond to , and hanoi Formal parameters in function a,b,c The corresponding value is also changing regularly 
int main()
{
    
	int n = 0;
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	return 0;
}

Running results

3
A->C
A->B
C->B
A->C
B->A
B->C
A->C

D:\c code\ Small question bank \ The hanotta problem \Debug\ The hanotta problem .exe ( process  13928) Exited , The code is  0.
 Press any key to close this window . . .

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

D:\c code\ Small question bank \ The hanotta problem \Debug\ The hanotta problem .exe ( process  19616) Exited , The code is  0.
 Press any key to close this window . . .

The code analysis

The illustration

The core algorithm

if (n == 1)
	{
    
		move(a, c);
	}
else
	{
    
		hanoi(n - 1, a, c, b);// take A On the seat n-1 With the help of C The seat moves to B seat 
		move(a, c);// take A The last plate on the seat moves to C seat 
		hanoi(n - 1, b, a, c);// take B On the seat n-1 With the help of A The seat moves to C seat 
    } 

The judgment condition is n Is it 1, When n=1 End of time , Re pass move Function to print the required steps , The recursive process is really hard to describe , I can only understand it by myself

Personal research

1. You'll find that n The number of steps required for a plate is 2 Of n Power of minus one , And the middle step is always A–>C
2. Why is the first step always A–>C, And even hours , The first step is always A–>B？
explain ：hanoi(n - 1, a, c, b) Arguments to functions a,b and c Not always corresponding A disc ,B Plate and C Disk and after passing it to the formal parameter abc The corresponding value will change , But it is changing regularly , Why do you want to know this ? Because of this hanoi The value corresponding to the formal parameter of the function will affect move Function printing . Rules are formal parameters abc The corresponding value is ACB,ABC Cycle change , Plus the first call hanoi Function parameter abc Corresponding ABC, This explains why the first step is always A–>C, And even hours , The first step is always A–>B

experience

So hard , It took me a whole afternoon to understand , I also read the explanation in the book , Read other people's explanations , The above analysis diagram is copied （hhh）, Just a few examples , Implement the code again and again, and then understand , Find out the rules . Recursive problems are abstract , It's hard to imagine the running result , You can do some simple recursive problems to understand , Take your time , Have a headache , Ha ha ha

If there is a mistake , Also please correct me , thank you ！