This approach differs from the novice's approach in that it looks at the last disk first and the first disk last. If you continue to follow this pattern you can visualize what the recursive algorithm is doing. Next, for n = 3, if ring 3 will be moved from A to B, where are rings 2 and 1? On peg C of course. If ring 4 will be moved from A to C, where are rings 3 and smaller? They can only be on peg B. Following this algorithm we look at n = 4. In the algorithm above the function Hanoi (n-1, A, C, B) is trying to move all those 4 other rings on to peg C, so ring 5 will be able to move from A to B. The question to ask yourself first is if I want to move the 5th ring from A to B, where are the other 4 rings? If the 5th ring occupies peg A and we want to move it to peg B, then the other 4 rings can only be on peg C. So, let's look at this algorithm for n = 5. ![]() I was taught in graduate school to never to be ashamed to think small. The first parameter of the function is the number of rings, second parameter represents the source peg, the third is the destination peg, and fourth is the spare peg. Here is the algorithm again with n representing the number of rings, and A, B, C representing the pegs. Lastly, it is funny how explaining a problem to a colleague, your wife/husband or even the dog (even it they not listening) can cement enlightenment.Īfter reading all these explanations I thought I'd weigh in with the method my professor used to explain the Towers of Hanoi recursive solution. The final number of moves for n discs is 2^n - 1 the move n disc to destination is halfway through the process. Then move the top disc to the source peg, make the next legal move(nittd).īest done by always holding the top disc with the same hand and always moving that hand in the same direction. Then move the top disc to the spare peg, make the next legal move(nittd). if odd, move the first disc to the destination peg, make the next legal move (not involving the top disc).Then move the top disc to the source peg, make the next legal move(nittd). Then move the top disc to the destination peg, make the next legal move(nittd). if even, move the first disc to the spare peg, make next legal move (not involving the top disc). ![]() ![]() Incidently, to solve the problem by hand is quite satisfying. The solution also conveys the power of proof by induction and a warm glow to all programmers who have wrestled with conventional control structures. However it is the displaying of the function parameters which is the solution to the problem and crucially understanding the double tree like structure of the calls. moving the remaining tower on the spare peg to the destination peg.moving the last disc to the destination peg.moving a smaller tower to the spare peg.Yes the problem is really in three parts: The magic occurs in the succesive rearrangment of the function parameters. ![]() In the Tower of Hanoi, the answer is not in the returned result per se, but in the observation of the returned result. However, this teaches the reader to use the results of the returned result in the next recursive call. After that, the remaining disc will be moved to the destination peg and afterwards the second recursion compeltes the moving of the entire tower, by moving the n − 1 tower from the temp peg to the destination peg, above disc n.Īlthough this is an old post, I think what one really needs to understand, is not the "move this to that" approach but that the answer involves using the side-effect of the recursion.Ī invaluable help to me was the "The Little Schemer" which teaches one to think and write recursive functions. The one before the writeln will move n − 1 discs onto the temporary peg, using the destination peg as temporary storage (the arguments in the recursive call are in different order). The recursion happens actually twice, there, once before the writeln, once after. The code in your post has three arguments, besides the number of discs: A source peg, a destination peg and a temporary peg on which discs can be stored in between (where every disc with size n − 1 fits). And that you have to move them first to another peg than where you want the full tower to appear. It's pretty clear that you first have to remove n − 1 discs to get access to the nth one. move n−1 discs from B to C so they sit on disc #n.Actually, the section from where you took that code offers an explanation as well:
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |