Hanoi Tower problem

---

Preface

Modern cognitive psychology is an experiment used to study the psychological characteristics of people's problem-solving process . The initial state of Hanoi Tower problem is A、B、C The three pillars , stay A There is a hole in the middle of the column, which overlaps from large to small and from bottom to top “ tower ” The same number of discs . The target state is to “ tower ” Move to C On the column ,B Column as transition . The rule is that only the top disc can be moved at a time , The big disc cannot be pressed on the small disc . It is required to explore the path from the initial state to the target state , Finally solve the problem , State of achievement . The subjects thought , While reporting out loud what you think . According to the oral report of the subjects , Analyze their thinking process .

One 、Hanoi What is the tower problem ？

Hanoi Tower problem is a classical experiment in problem solving . Give column 1、2、3, In the column 1 On , There is a series of discs , The size of the top-down disc is increasing , Form a pyramid . The subjects are required to put the column 1 All the disks of move to the column 3 Up , And finally in the column 3 It still forms a pyramid arrangement , The rule is that only one disc can be moved at a time , And the market cannot be pressed on the small market , You can use a cylinder 2. The minimum number of movements to complete Hanoi tower operation is 2-1 Time , among n Is the number of discs .

Two 、 Problem description

There are three needles on one board A、B、C.A The needle is covered with a needle 64 A disc of different sizes , According to the big one 、 The small ones are arranged in the order of , I want to put this 64 A disk from A The needle moves to C On the needle , Only one disc can be moved at a time , The movement process can be done with the help of B The needle . But at any time , Any disc on the needle must keep the big one down , Small in . Enter the number of disks to be moved from the keyboard , Give the process of moving .

3、 ... and 、 Algorithmic thought

When only one disc is moved , Direct the disc from A The needle moves to C The needle .
If the moving disk is n(n>1), It is divided into several steps ：

1. hold (n-1) A disk from A The needle moves to B The needle （ With the help of C The needle ）;
2. A The last disc on the needle moves to C The needle ;
3. B On the needle (n-1) A disk moves to C The needle （ With the help of A The needle ）.

Every time I do it , One less moving disc , Gradually decreasing , Finally, when n by 1 when , Complete the entire movement .

therefore , To solve the tower of Hanoi problem, a recursive function can be designed , Using recursion to realize the whole moving process of the disk , The problem solving process is a simulation of actual operation .

Four 、 Solutions

There are four common strategies to solve the Hanoi Tower problem ：

1. Loop sub goal , Also known as target recursion strategy ： The idea is to move the largest pyramid to the column 3, First move the second largest pyramid to the column 2; And to move the next largest pyramid to the column 2, It is necessary to first move the pyramid one layer smaller than it to the column 3;… By analogy , Until you only need to move the top plate . This strategy is similar to computer recursion , It is an internally directed strategy , Subjects do not have to look at specific stimuli , Just keep your internal goals in mind , Then step by step loop execution , Until the problem is solved .
2. Perceptual strategies ： This strategy is the strategy of stimulating and guiding , According to the relationship between the situation and the goal , Remove the biggest obstacle at present , So as to achieve the goal step by step .
3. Mode strategy ： It is also the strategy of internal guidance , But it doesn't involve the goal , But to act according to certain rules . The general rule for solving the river tower is , When the total number of discs is odd , The smallest disc press 1->3->2->1->3->2 Move in order , When the total number is even , Press 1->2->3->1->2->3 Move in order .
4. Mechanical memory strategies ： This strategy is to memorize a series of steps to do the right thing , But you can't innovate , Not transferable .

5、 ... and 、 Code implementation

Here I take the first solution as an example to code

Sample code ：

#include<iostream>

using namespace std;

int m=0;      // Count the movement  
void move(char A,int n,char C)       // Moving operation  
{
    
	cout<<" The first "<<++m<<" Step ,"<<" Will be numbered as "<<n<<" The disc of "<<A<<" Move the first column to the "<<C<<" On the pillars "<<endl; 
}

void hanoi(int n,char A,char B,char C)   // Put the tower A Upper n A disc is moved according to the rules C On  
{
    
	if(n==1)
	  move(A,1,C);
	else
	{
    
		hanoi(n-1,A,C,B);     // take A The above number is 1 to n-1 Move your disc to B,C As an auxiliary tower 
		move(A,n,C);         // Will be numbered as n The disc from A Move to C
		hanoi(n-1,B,A,C);     // take B The above number is 1 to n-1 Move your disc to C,A As an auxiliary tower  
	}
}

int main()
{
    
	int n;
	char a,b,c;
	a='1';
	b='2';
	c='3';
	cout<<" Please enter the number of discs on the initial first column ："<<endl;
	cin>>n;
	cout<<" The process of moving all the discs on the first column to the third column is ："<<endl;
	hanoi(n,a,b,c);
	return 0;
 }