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.
#Hanoi towers golang code
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).
#Hanoi towers golang full
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.
0 kommentar(er)
