One 、 The source of the problem

It's said that in the ancient temple of India , There is one called the Hanoi Tower (Hanoi) The game of . The game is on a copper device , There are three rods ( Number A、B、C), stay A From the bottom up 、 Place in order from large to small 64 A gold plate ( Pictured 1). The goal of the game ： hold A All the gold plates on the pole are moved to C On the pole , And still keep the original order . Operating rules ： Only one plate can be moved at a time , And keep the big plate down all the time during the moving process , Small in , The plate can be placed during the operation A、B、C On any pole .

Two 、 The solution to the problem

analysis ： For such a question , No one can write every step of moving the plate directly , But we can use the following methods to solve . Set the number of moving plates to n, To put this n A plate from A The rod moves to C rod , You can do the following three steps ：

(1) With C Disk as an intermediary , from A Rod will 1 to n-1 Disk No. moved to B rod ;

(2) take A The remaining third in the rod n Disk No. moved to C rod ;

(3) With A The rod is the intermediary ; from B Rod will 1 to n-1 Disk No. moved to C rod .

         In practice , Only the second step can be done directly , And first 、 Three steps have become a new problem of mobile . The essence of the above operation is to move n The problem of a plate turns into moving n-1 A plate , That one 、 Three steps to solve ？ in fact , The above method sets the number of plates as n, n Can be any number , The same applies to mobile phones n-1 A plate . therefore , According to the above law , To solve n -1 A plate from A Move lever to B rod ( First step ) Or from B Move lever to C rod ( The third step ) problem . Now? , The problem is solved by moving n The operation of a plate is transformed into moving n-2 The operation of a plate . According to this principle , Layer by layer recursion , You can turn the original problem into a mobile solution n -2、n -3… … 3、2, Until you move 1 Operation of a disk , The operation of moving a disk can be completed directly . thus , The tower of Hanoi problem was solved . And this is complicated and simplified , A method of solving complex problems with simple problems and known operations , It's recursion .

3、 ... and 、 The steps of Hanoi Tower problem （ Divided into two steps ）

First step ：

        hold  n-1 A plate   From tower 1 Move to the tower 2

        The first n A plate     From tower 1 Move to the tower 3

The second step ：        

        hold n-1 A plate   From tower 2 Move to the tower 3

Four 、 Code implementation

#include <stdio.h>

void Hanoi(int n, char* left, char* mid, char* right,int* p) {
	if (n == 1) {
		printf("%s   Move to   %s\n", left, right);
		(*p) += 1;
	 }
	else {
		han_nuo(n-1, left, right, mid, p);
		printf("%s   Move to   %s\n", left, right);
		(*p)++;
		han_nuo(n-1, mid, left, right, p);
	}
}


int main() {
	int n = 0;
	int count = 0;
	char arr[][5] = { " TA Yi "," Tower II "," Tower three " };
	printf(" Please enter the number of floors of Hanoi tower ：");
	scanf("%d", &n);
	Hanoi(n,arr[0], arr[1], arr[2], &count);
	printf(" It needs to be moved altogether  %d  Time \n", count);

	return 0;
}