C++ Hannot tower question points summary

The Hannott problem is one of the tasks commonly used in psychological experimental research. Of course we are computer students, so we try to solve it with a computer.

sample

openjudge6261 tower of hannot problem

describe

There is an intellectual toy that has three poles on a piece of copper. The left-most pole is followed from top to bottom by a tower of n discs. The aim is to move all the plates on the leftmost bar to the middle bar, provided that only one plate can be moved at a time, and the large plate is not allowed to be placed on the top of the small plate. This is known as the Tower of Hannock problem.

Suppose the disks are numbered 1,2,3 from small to large...

The input

Enter 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.

The output

Output a record of moving the plate for each step. Move 1 row at a time.

Each movement is recorded as for example a- > 3- > The FORM of the b is to move the plate number 3 from the a to the b.

The sample input

[

2 a b c

]

Sample output

[

a- > 1- > c
a- > 2- > b
c- > 1- > b

]

The Tower of Hannock question

The solving algorithm of Hannott Tower problem is a classic divide and conquer algorithm, and the most important three steps of divide and conquer algorithm are:

Decomposition: if we're gonna num plate from the original post l move to the target by transition pillars mid pillars r, so we can put the above (num - 1) plate transition from the original post l moved to post mid, then put the number on this plate to the target columns r num, and then the transition (num - 1) plate from pillar mid moved to the goal post r, was successful.
Solve: Recursively solve subproblems separately and output. (Boundary condition: when there is only 1 plate num == 1, the direct output is fine).
Merge: Recursion returns the result, no more merging.

In short, each time we view the num plate as a whole, the remaining (num-1) plate as a whole, and then move the two parts to reach the target position.

Finally, let's figure out the time complexity, which is a little bit more difficult here.

Suppose i moving plates from one post to another requires step(i) steps

For a single tower, the program does the following:

Move the above (n-1) plates to the transition post for the number of times step(n-1). Move the n dish to the target column 1 times. Move the plates from the transition column (n-1) to the target column for a number of times (n-1).

And you get a recurrence

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

And then you keep recursing, and you get

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

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

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

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 Hannot problem. Therefore, the time complexity of the algorithm is O(2^n^).

code

# include <cstdio>
# include <iostream> 
# include <cmath>
# include <cstring>
# include <algorithm>

using namespace std;

int n;
char a, b, c;

// hanoi(num, l, mid, r) Indicates the need for num A plate from the post l Through the post mid Move 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 they're moving all of the plates from the left pillar to the middle pillar, so from a to b . 
  return 0;
}

Is this site to organize all the relevant knowledge points, thank you for your study and this site support.