Shulou(Shulou.com)05/31 Report--

This article mainly introduces "how to solve the tower of Hanoi problem in C++". In daily operation, I believe many people have doubts about how to solve the tower of Hanoi problem in C++. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the doubt of "how to solve the tower of Hanoi problem in C++!" Next, please follow the editor to study!

Openjudge6261 Hanoi Tower problem

Description

There is an intellectual toy with three poles on a copper plate, and the leftmost pole is connected with a tower composed of n discs from small to large from top to bottom. The aim is to move all the plates on the leftmost rod to the middle rod, provided that only one disk can be moved at a time, and the large plate is not allowed to be placed on top of the small one. This is the famous Tower of Hanoi problem.

Suppose the disc is numbered from small to large as 1, 2, 2, 3,...

Input

Enter as an integer followed by three single-character strings.

The integer is the number of plates, and the last three characters represent the number of the three poles.

Output

Output a record of moving the plate at each step. Move one line at a time.

Each movement is recorded in the form of, for example, a-> 3-> b, that is, the plate numbered 3 is moved from pole a to pole b.

Sample input

2 a b c

Sample output

A-> 1-> c

A-> 2-> b

C-> 1-> b

Tower of Hanoi problem

The algorithm for solving the Hanoi Tower problem is a classical divide-and-conquer algorithm, and the three most important steps of the divide-and-conquer algorithm:

Decompose: if we want to move the num plate from the original column l to the target column r through the transition column mid, then we can first move the upper (num-1) plate from the original column l to the transition column mid, then move the plate numbered num to the target column r, and finally move the (num-1) plate from the transition column mid to the target column r, and it is successful.

Solution: use recursion to solve the sub-problem and output. (boundary condition: when there is only one plate, both num = = 1, the direct output is fine.)

Merge: the result is returned recursively, and there is no need to merge.

In short, each time we regard the num plate as a whole and the remaining (num-1) plate as a whole, then move the two plates separately to make them reach the target position.

Finally, calculate the time complexity, which is a little difficult to calculate here.

Suppose you need step step (I) to move a plate from one post to another.

For a single tower, the program does the following:

Move the upper (n-1) plates to the transition column for step (n-1) times.

Move the nth plate to the target post for 1 times.

Move the (n-1) plates on the transition post to the target column for the number of times step (n-1).

Then you can get a recursive formula.

Step (n) = 2 * step (n-1) + 1

And then keep repeating it, and you'll get it.

Step (n) = 2 ^ n * step (0) + 2 ^ (n-1) + 2 ^ (n-2) +. + 2 ^ 1 + 2 ^ 0

And because 0 plates don't need to be moved at all, step (0) = 0

So step (n) = 2 ^ (n-1) + 2 ^ (n-2) +. + 2 ^ 1 + 2 ^ 0

Then it can be deduced from the formula of proportional series: step (n) = 2 ^ n ^-1

We found that the number of moves is 2 ^ n ^-1, which is actually the least number of moves for the Tower of Hanoi problem. Therefore, it is concluded that the time complexity of the algorithm for solving the Hanoi Tower problem is O (2 ^ n ^).

Code

# include # include using namespace std;int ntachar a, b, c mid / hanoi (num, l, mid, r) indicates the need to move num plates from column l through column mid to column r. Void hanoi (int num, char l, char mid, char r) {if (num = = 1) printf ("% c->% d->% c\ n", l, num, r); else {hanoi (num-1, l, r, mid); printf ("% c->% d->% c\ n", l, num, r); hanoi (num-1, mid, l, r);} int main () {scanf ("% d", & n) Cin > > a > > b > > c; hanoi (n, a, c, b); / / here because the title is to move all the plates from the left column to the middle column, from a to b. Return 0;} at this point, the study on "how to solve the Tower of Hanoi problem in C++" is over. I hope I can solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.