s3a
  • s3a
(Tower of Hanoi algorithm) For this algorithm: Tower(n,start, finish, other) if n>0 then Tower(n-1, start, other, finish) println(‘move from ’ + start + ‘ to ’ + finish ) Tower(n-1, 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.)
Computer Science
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
jagatuba
  • jagatuba
Recursion 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 h-1 disks are on peg B. Hence, first all h-1 smaller disks must go from A to B. Subsequently move the largest disk and finally move the h-1 smaller disks from peg B to peg C. The presence of the largest disk does not impede any move of the h-1 smaller disks and can temporarily be ignored. Now the problem is reduced to moving h-1 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 h-1 problem to h-2, h-3, 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 h-1 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 h-1 smaller disks from peg A to peg B. Step 2: Now the largest disk, i.e. disk h-1 can be moved from peg A to peg C. Step 3: If h>1 then again use this procedure to move the h-1 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 _{h-1}\]moves, and step 2 takes one move, giving \[T _{h} = 2T _{h-1} + 1\](sorry, I've already forgotten how to make LaTeX print the equations on one line)

Looking for something else?

Not the answer you are looking for? Search for more explanations.