Description
Background
Charlie Darkbrown sits in another one of those boring Computer Science lessons: At the moment the teacher just explains the standard Tower of Hanoi problem, which bores Charlie to death!
The teacher points to the blackboard (Fig. 4) and says: “So here is the problem:
- There are three towers: A, B and C.
- There are n disks. The number n is constant while working the puzzle.
- All disks are different in size.
- The disks are initially stacked on tower A increasing in size from the top to the bottom.
- The goal of the puzzle is to transfer all of the disks from tower A to tower C.
- One disk at a time can be moved from the top of a tower either to an empty tower or to a tower with a larger disk on the top.
So your task is to write a program that calculates the smallest number of disk moves necessary to move all the disks from tower A to C.”
Charlie: “This is incredibly boring-everybody knows that this can be solved using a simple recursion. I deny to code something as simple as this!”
The teacher sighs: “Well, Charlie, let’s think about something for you to do: For you there is a fourth tower D. Calculate the smallest number of disk moves to move all the disks from tower A to tower D using all four towers. “
Charlie looks irritated: “Urgh. . . Well, I don’t know an optimal algorithm for four towers. . . “
background:
Charlie Duck Brown is sitting in another boring computer science class: now the teacher is just explaining the standard Tower of Hanoi problem, and it’s annoying Charlie to death! The teacher points to the blackboard (Figure 4) and says: “Here’s the problem: There are three towers: A, B and C. There are n disks. The number n is a constant during the puzzle. All the disks are different sizes. The disks are initially stacked On Tower A, the size gradually increases from top to bottom. The goal of this puzzle is to transfer all the disks from Tower A to Tower C. You can move one disk at a time from the top of the tower to an empty tower or a tower with a larger top. A tower of big disks. So your task is to write a program that calculates the minimum number of disk moves required to move all the disks from Tower A to Tower C.” Charlie: “This is so boring-everyone knows this works Solve it with a simple recursion. I refuse to write such a simple code!” The teacher sighed: “Okay, Charlie, let’s think about what you have to do: For you, there is a fourth tower. Use all Four towers, calculate the minimum number of disk moves required to move all the disks from tower A to tower D.” Charlie looked angry: “Uh… Okay, I don’t know about the four towers. The best algorithm…”
Problem
So the real problem is that problem solving does not belong to the things Charlie is good at. Actually, the only thing Charlie is really good at is “sitting next to someone who can do the job”. And now guess what – exactly! It is you who is sitting next to Charlie, and he is already glaring at you.
Luckily, you know that the following algorithm works for n <= 12: At first k >= 1 disks on tower A are fixed and the remaining n-k disks are moved from tower A to tower B using the algorithm for four towers.Then the remaining k disks from tower A are moved to tower D using the algorithm for three towers. At last the n – k disks from tower B are moved to tower D again using the algorithm for four towers (and thereby not moving any of the k disks already on tower D). Do this for all k 2 ∈{1, …. , n} and find the k with the minimal number of moves.
So for n = 3 and k = 2 you would first move 1 (3-2) disk from tower A to tower B using the algorithm for four towers (one move). Then you would move the remaining two disks from tower A to tower D using the algorithm for three towers (three moves). And the last step would be to move the disk from tower B to tower D using again the algorithm for four towers (another move). Thus the solution for n = 3 and k = 2 is 5 moves. To be sure that this really is the best solution for n = 3 you need to check the other possible values 1 and 3 for k. (But, by the way, 5 is optimal. . . )
Problem So the real problem is that problem solving is not something Charlie is good at. In fact, the only thing Charlie is good at is “sitting next to someone who can do the job.” Now guess what! Sitting next to Charlie was you, and he was already glaring at you. Fortunately, you know that the following algorithm works for n <= 12: First, k >= 1 disks on tower A are fixed, and the remaining n-k disks are moved from tower A to tower B using the algorithm for 4 towers. The remaining k disks from Tower A are then moved to Tower D using the three-tower algorithm. Finally, using the algorithm for four towers, move the n-k disks from tower B to tower D again (so not moving any of the k disks that are already on tower D). Do this for all k2∈{1,…,n} and find the k with the minimum number of moves. So, for n = 3 and k = 2, you first move 1 (3-2) disks from tower A to tower B using the algorithm of four towers (one move). You would then move the remaining two disks from tower A to tower D using an algorithm of three towers (three moves). The final step is to move the disk from Tower B to Tower D, again using the four-tower algorithm (another move). Therefore, the solution for n = 3 and k = 2 is 5 steps. To make sure this is indeed the best solution for n = 3, you need to check other possible values of 1 and k. (But, by the way, 5 is optimal…)
Input
There is No input.
no input
Output
For each n (1 <= n <= 12) print a single line containing the minimum number of moves to solve the problem for four towers and n disks.
For each n (1 < = n < = 12) print a line containing the minimum number of moves needed to solve the problem of four towers and n disks.
Sample input
No input.
no input
Sample output
REFER TO OUTPUT.
Reference output
Source
TUD Programming Contest 2002, Darmstadt, Germany
Analysis
You can answer the questions and listen to a story, although the story is boring
Don’t even think about this kind of question, recursion! Recursion! Recursion!
In the classic Tower of Hanoi problem with n plates and three towers, let d[n] represent the minimum number of steps to solve the n plates and three towers problem, d[n]=2*d[n-1] + 1;
In the regression ontology, let F[n] represent the minimum number of steps to solve the problem of n plates and 4 towers, there is F[n]=min{2*F[i] + d[n-i]}(1<=i Get it done directly and easily Give it a like and follow itCode
#include <cstdio>
#include <cstring>
const int maxn = 15;
int d[maxn], f[maxn];
int main() {
for (int i = 1; i <= 12; + + i) d[i] = 2 * d[i - 1] + 1;
memset(f, 0x3f, sizeof(f));
f[1] = 1;
for (int i = 2; i <= 12; + + i)
for (int j = 1; j < i; + + j)
if (2 * f[j] + d[i - j] < f[i]) f[i] = 2 * f[j] + d[i - j];
for (int i = 1; i <= 12; + + i) printf("%d\
", f[i]);
return 0;
}