Shulou(Shulou.com)06/01 Report--

Today, the editor will share with you the relevant knowledge points about how the c language circulates plus arrays to realize the tower of Hanoi. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Brief introduction

The tower of Hanoi problem is a problem that will be encountered when learning data structures and algorithms. I believe that the readers of this article should have a basic understanding of the tower of Hanoi problem. In theory, all recursion can be changed into loops, and the conventional approach is with the help of stacks. but when I think that it can also be realized with a cyclic plus array, so there is this article, the implementation statement, the algorithm at the end of this article is not efficient. It is much worse than directly using recursive implementation, and students who pursue the efficiency of the algorithm do not have to look at this.

Topic: suppose there are three columns, which are A, B and C, respectively, there are n hollow disks on the A column, and the serial number from top to bottom is 1. N. It is required that the n disks in column A be moved to the C column, and the plates with large serial numbers must be under the smaller ones.

Idea: if only one disc needs to be moved, move directly from column A to column C. if there are n disks (n > 1) that need to be moved, you need to first move a disc from column A to column B, then move the nth disc from column A to column C, and finally move the original disc from column B to column C.

For example:

Moving a disk from column A to column C takes only one step:

1. Move disk 1 from A to C.

Moving 2 discs from column A to column C takes three steps:

1. Move disk 1 from A to B.

two。 Move disc 2 from A to C.

3. Move disk 1 from B to C.

Moving 3 discs from column A to column C takes 7 steps:

1. Move disk 1 from A to C.

two。 Move disk 2 from A to B.

3. Move disk 1 from C to B.

4. Move disc 3 from A to C.

5. Move disk 1 from B to A.

6. Move disc 2 from B to C.

7. Move disk 1 from A to C.

Recursive Hanoi Tower solution (c language)

You can see that the time complexity of the following recursive algorithm is O (2 ^ n), because there are 2 ^ n-2 recursive calls and 1 native printf;, and the space complexity is O (n), because at most n function call information is saved at the same time in the runtime stack.

# include # include # include void towers (int n, char from, char to, char aux); int main () {towers (3,'A,'C,'B'); return 0;} void showMove (int order, char from, char to) {printf ("move disk% d from% c to% c\ n", order, from, to) } void towers (int n, char from, char to, char aux) {if (naughty room1) {showMove (n, from, to); return;} towers (nMuth1, from, aux, to); showMove (n, from, to); towers (nMuth1, aux, to, from);}

To explain the meaning of the parameters in the code, void towers (int n, char from, char to, char aux) means to move n disks from the from column to the to column, and the aux column can be borrowed in the middle.

Analyze the above recursive execution process:

We already know that the step to move a disk from from to to is showMove (1, from, to).

The step of moving two disks from from to to is to move the first one from from to aux, then the second from from to to, and finally move the first one from aux to to according to the operation of moving one disc.

Similarly, the step of moving three disks from from to to is to move the first two disks from from to aux, then the third disc from from to to, and finally move the two discs from aux to to according to the operation of moving two disks.

Therefore, the step of moving the operation of n disks from from to to is to first move the first NMuq disc from from to aux, then the nth disc from from to to, and finally move the nMub disc from aux to to according to the operation of moving NMAE 1 disc.

Therefore, we can record the step of moving 1 disc to get the step of moving 2 disks, and the step of moving 3 disks by moving 2 discs. Finally, the step of moving n disks is obtained. After analysis, we can know that there are a total of 2 ^ n-1 steps to move n discs.

Loop realization of the Tower of Hanoi problem (c language)

In order to make the code easier to understand, comments are written here, some variable names are modified, and the step set is uniformly saved in an array before being output.

We can see that the time complexity of this algorithm is still O (2 ^ n). A total of 2 ^ (n ^ 1)-1 setMoveAction statements and 2 ^ n-1 times, printf statements are more complicated than directly using recursion, and the space complexity is also O (2 ^ n). It is a useless algorithm, just writing casually.

# include # include # include void towers (int n, char from, char to, char aux); int main () {towers (3,'A','C,'B'); return 0;} void showMove (int order, char from, char to) {printf ("move disk% d from% c to% c\ n", order, from, to);} typedef struct {int order; char from; char to;} MoveAction Void setMoveAction (MoveAction * p, int order, char from, char to) {p-> order = order; p-> from = from; p-> to = to;} char compare_map (char c, char left, char right) {if (c = = left) {return right;} else if (c = = right) {return left;} return c;} void towers (int n, char from, char to, char aux) {MoveAction * actions, action Int I, k, size; char f, t; actions = (MoveAction *) calloc (pow (2, n-1)-1, sizeof (MoveAction)); setMoveAction (& actions [0], 1, from, to); size = 1; for (I = 2; I

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.