Java programming uses stack to solve the code example of Hanoi Tower problem (non recursive)

[title]

The tower of Hanoi is a classic problem. Here is a modification of the rules of the game: now the restrictions cannot be moved directly from the leftmost tower to the rightmost tower, nor from the rightmost tower to the leftmost tower, but must pass through the middle. When the tower has n layers, print the optimal moving process and the optimal total moving steps.

[answer]

In the previous article, we used the recursive method to solve this problem. Here we use the stack to simulate the three towers of Hanoi Tower, that is, we don't need the recursive method

The principle is as follows: the modified Hanoi Tower problem cannot make any tower move directly from left to right, nor from right to left, but through the middle, that is, there are only four actions that can be done: left - > middle, middle - > left, middle - > right, right - > middle

Using a stack to simulate the movement of Hanoi tower is actually to pop up the top element of a stack and press it into another stack as the top of another stack. It's easy to understand this. There are two principles for this problem:

I: the principle of small pressing large, that is, the element value to be pressed cannot be greater than the element value at the top of the stack to be pressed, which is also the basic rule of Hanoi tower

Second: the principle of adjacent irreversibility, that is, if my previous operation is left - > middle, then the next operation must not be middle - > left, otherwise it is equivalent to moving over and back

With these two principles, two very useful conclusions can be derived:

1. The first action of the game must be L - > M

2. At any time in the process of stepping out of the minimum number of steps, only one of the four actions does not violate the principle of small pressing large and adjacent irreversibility, and the other three actions must violate

[code implementation]

summary

The above is the code example of Java programming using stack to solve Hanoi Tower problem (non recursive) all the contents, I hope to help you. Interested friends can refer to: detailed examples of calculating the approximate value of PI by Java Monte Carlo algorithm, running out of the maze of Java genetic algorithm, four examples of mixed operation code implemented in Java, etc. you can leave a message at any time. Welcome to exchange and discuss.