A community for students.
Here's the question you clicked on:
 0 viewing
s3a
 4 years ago
(Tower of Hanoi algorithm)
For this algorithm:
Tower(n,start, finish, other)
if n>0 then
Tower(n1, start, other, finish)
println(‘move from ’ + start + ‘ to ’ + finish )
Tower(n1, other, finish, start)
end if
Could someone explain to me how it works and give an example because I am especially confused by the fact that there are two recursive calls in the method? (I played the game online on purpose so I know how to play.)
s3a
 4 years ago
(Tower of Hanoi algorithm) For this algorithm: Tower(n,start, finish, other) if n>0 then Tower(n1, start, other, finish) println(‘move from ’ + start + ‘ to ’ + finish ) Tower(n1, other, finish, start) end if Could someone explain to me how it works and give an example because I am especially confused by the fact that there are two recursive calls in the method? (I played the game online on purpose so I know how to play.)

This Question is Closed

jagatuba
 4 years ago
Best ResponseYou've already chosen the best response.1Recursion is used because the steps in moving the disks from point A to point C is determined by the size of the disk being moved. Therefore, as each disk is moved the algorithm can be reused to determine where to move it. This is probably as simply as it can be stated. Perhaps someone else can explain it more plainly, but if you want a more detailed explanation, I found the one provided in Wikipedia to be pretty good: As in many mathematical puzzles, finding a solution is made easier by solving a slightly more general problem: how to move a tower of h (h=height) disks from a starting peg A (f=from) onto a destination peg C (t=to), B being the remaining third peg and assuming t≠f. First, observe that the problem is symmetric for permutations of the names of the pegs (symmetric group S3). If a solution is known moving from peg A to peg C, then, by renaming the pegs, the same solution can be used for every other choice of starting and destination peg. If there is only one disk (or even none at all), the problem is trivial. If h=1, then simply move the disk from peg A to peg C. If h>1, then somewhere along the sequence of moves, the largest disk must be moved from peg A to another peg, preferably to peg C. The only situation that allows this move is when all smaller h1 disks are on peg B. Hence, first all h1 smaller disks must go from A to B. Subsequently move the largest disk and finally move the h1 smaller disks from peg B to peg C. The presence of the largest disk does not impede any move of the h1 smaller disks and can temporarily be ignored. Now the problem is reduced to moving h1 disks from one peg to another one, first from A to B and subsequently from B to C, but the same method can be used both times by renaming the pegs. The same strategy can be used to reduce the h1 problem to h2, h3, and so on until only one disk is left. This is called recursion. This algorithm can be schematized as follows. Identify the disks in order of increasing size by the natural numbers from 0 up to but not including h. Hence disk 0 is the smallest one and disk h1 the largest one. The following is a procedure for moving a tower of h disks from a peg A onto a peg C, with B being the remaining third peg: Step 1: If h>1 then first use this procedure to move the h1 smaller disks from peg A to peg B. Step 2: Now the largest disk, i.e. disk h1 can be moved from peg A to peg C. Step 3: If h>1 then again use this procedure to move the h1 smaller disks from peg B to peg C. By means of mathematical induction, it is easily proven that the above procedure requires the minimal number of moves possible, and that the produced solution is the only one with this minimal number of moves. Using recurrence relations, the exact number of moves that this solution requires can be calculated by: \[2^{h}1\]This result is obtained by noting that steps 1 and 3 take \[T _{h1}\]moves, and step 2 takes one move, giving \[T _{h} = 2T _{h1} + 1\](sorry, I've already forgotten how to make LaTeX print the equations on one line)
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.